A245559 -id:A245559 - cp's OEIS frontend

A047996 Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 4, 3, 1, 1, 1, 1, 3, 5, 5, 3, 1, 1, 1, 1, 4, 7, 10, 7, 4, 1, 1, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 1, 1, 5, 12, 22, 26, 22, 12, 5, 1, 1, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 1, 1, 6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, 1, 1, 6, 22

Offset: 0

N. J. A. Sloane

Equivalently, T(n,k) = number of necklaces with k black beads and n-k white beads (binary necklaces of weight k).
The same sequence arises if we take the table U(n,k) = number of necklaces with n black beads and k white beads and read it by antidiagonals (cf. A241926). - Franklin T. Adams-Watters, May 02 2014
U(n,k) is also equal to the number of ways to express 0 as a sum of k elements in Z/nZ. - Jens Voß, Franklin T. Adams-Watters, N. J. A. Sloane, Apr 30 2014 - May 05 2014. See link ("A Note on Modular Partitions and Necklaces") for proof.
The generating function for column k is given by the substitution x_j -> x^j/(1-x^j) in the cycle index of the Symmetric Group of order k. - R. J. Mathar, Nov 15 2018
From Petros Hadjicostas, Jul 12 2019: (Start)
Regarding the comments above by Voss, Adams-Watters, and Sloane, note that Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} A054535(d, v) * binomial((n + k)/d, k/d) = S(k, n, v).
This result was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 0) = A241926(n, k) = U(n, k) = T(n + k, k) (where T(n, k) is the current array). Also, S(n, k, 1) = A245558(n, k). See also Panyushev (2011) for more general results and for generating functions.
Finally, note that A054535(d, v) = c_d(v) = Sum_{s | gcd(d,v)} s*Moebius(d/s). These are the Ramanujan sums, which equal also the von Sterneck function c_d(v) = phi(d) * Moebius(d/gcd(d, v))/phi(d/gcd(d, v)). We have A054535(d, v) = A054534(v, d).
It would be interesting to see whether there is a proof of the results by Fredman (1975), Elashvili et al. (1999), and Panyushev (2011) for a general v using Molien series as it is done by Sloane (2014) for the case v = 0 (in which case, A054535(d, 0) = phi(d)). (Even though the columns of array A054535(d, v) start at v = 1, we may start the array at column v = 0 as well.)
(End)
U(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - Álvar Ibeas, Sep 21 2021

			Triangle starts:
[ 0]  1,
[ 1]  1,  1,
[ 2]  1,  1,  1,
[ 3]  1,  1,  1,  1,
[ 4]  1,  1,  2,  1,  1,
[ 5]  1,  1,  2,  2,  1,  1,
[ 6]  1,  1,  3,  4,  3,  1,  1,
[ 7]  1,  1,  3,  5,  5,  3,  1,  1,
[ 8]  1,  1,  4,  7, 10,  7,  4,  1,  1,
[ 9]  1,  1,  4, 10, 14, 14, 10,  4,  1,  1,
[10]  1,  1,  5, 12, 22, 26, 22, 12,  5,  1, 1,
[11]  1,  1,  5, 15, 30, 42, 42, 30, 15,  5, 1, 1,
[12]  1,  1,  6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, ...

N. G. de Bruijn, Polya's theory of counting, in: Applied Combinatorial Mathematics (E. F. Beckenbach, ed.), John Wiley and Sons, New York, 1964, pp. 144-184 (implies g.f. for this triangle).
Richard Stanley, Enumerative Combinatorics, 2nd. ed., Vol 1, Chapter I, Problem 105, pp. 122 and 168, discusses the number of subsets of Z/nZ that add to 0. - N. J. A. Sloane, May 06 2014
J. Voß, Posting to Sequence Fans Mailing List, April 30, 2014.
H. S. Wilf, personal communication to N. J. A. Sloane, Nov., 1990.
See A000031 for many additional references and links.

Seiichi Manyama, Rows n=0..139 of triangle, flattened (Rows 0..50 from T. D. Noe)
Ethan Akin and Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985), 237-250.
J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982), 483-486, Theorem 5.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Elashvili and M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006)
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Harold Fredricksen, An algorithm for generating necklaces of beads in two colors, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, 181-188.
D. E. Knuth, Computer science and its relation to mathematics, Amer. Math. Monthly, 81 (1974), 323-343.
D. E. Knuth, H. Wilf, C. L. Mallows, and D. Klarner, Correspondence, 1994
Petr Lisonek, Computer-assisted Studies in Algebraic Combinatorics, Thesis, University of Linz (Austria) Sep. 1994, pp. 72-73.
D. I. Panyushev, Fredman's reciprocity, invariants of abelian groups, and the permanent of the Cayley table, J. Algebraic Combin. 33 (2011), 111-125.
Mónica A. Reyes, Cristina Dalfó, Miguel Àngel Fiol, and Arnau Messegué, A general method to find the spectrum and eigenspaces of the k-token of a cycle, and 2-token through continuous fractions, arXiv:2403.20148 [math.CO], 2024. See p. 5.
Frank Ruskey, Generate Necklaces, Lyndon words, and relatives, The Combinatorial Object Server.
Frank Ruskey and Joe Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
N. J. A. Sloane, A Note on Modular Partitions and Necklaces, 2014.
Pantelimon Stănică and Subhamoy Maitra, Rotation symmetric boolean functions - count and cryptographic properties, Disc. Appl. Math. 156 (2008) 1567-1580, g_{n,w} Theorem 9.
Wikipedia, Necklaces Animation [Broken link?]
Wolfram Research, Necklaces Applet.
Index entries for sequences related to necklaces

Row sums: A000031. Columns 0-12: A000012, A000012, A004526, A007997(n+5), A008610, A008646, A032191-A032197.
Cf. A051168, A052307, A052311-A052313.
See A037306 and A241926 for essentially identical triangles.
See A245558, A245559 for a closely related array.

A047996 := proc(n,k) local C,d; if k= 0 then return 1; end if; C := 0 ; for d in numtheory[divisors](igcd(n,k)) do C := C+numtheory[phi](d)*binomial(n/d,k/d) ; end do: C/n ; end proc:
seq(seq(A047996(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Apr 14 2011

t[n_, k_] := Total[EulerPhi[#]*Binomial[n/#, k/#] & /@ Divisors[GCD[n, k]]]/n; t[0, 0] = 1; Flatten[Table[t[n, k], {n, 0, 13}, {k, 0, n}]] (* Jean-François Alcover, Jul 19 2011, after given formula *)

p(n) = if(n<=0, n==0, 1/n * sum(i=0,n-1, (x^(n/gcd(i,n))+1)^gcd(i,n) ));
for (n=0,17, print(Vec(p(n)))); /* print triangle */
/* Joerg Arndt, Sep 28 2012 */

T(n,k) = if(n<=0, n==0, 1/n * sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d,k/d) ) );
/* print triangle: */
{ for (n=0, 17, for (k=0, n, print1(T(n,k),", "); ); print(); ); }
/* Joerg Arndt, Oct 21 2012 */

T(n, k) = (1/n) * Sum_{d | (n, k)} phi(d)*binomial(n/d, k/d).
T(2*n,n) = A003239(n); T(2*n+1,n) = A000108(n). - Philippe Deléham, Jul 25 2006
G.f. for row n (n>=1):  (1/n) * Sum_{i=0..n-1} ( x^(n/gcd(i,n)) + 1 )^gcd(i,n). - Joerg Arndt, Sep 28 2012
G.f.: Sum_{n, k >= 0} T(n, k)*x^n*y^k = 1 - Sum_{s>=1} (phi(s)/s)*log(1-x^s*(1+y^s)). - Petros Hadjicostas, Oct 26 2017
Product_{d >= 1} (1 - x^d - y^d) = Product_{i,j >= 0} (1 - x^i*y^j)^T(i+j, j), where not both i and j are zero. (It follows from Somos' infinite product for array A051168.) - Petros Hadjicostas, Jul 12 2019

Name edited by Petros Hadjicostas, Nov 16 2017

A185700 The number of periods in a reshuffling operation for compositions of n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 7, 8, 7, 3, 1, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1

Offset: 1

Paul Weisenhorn, Feb 10 2011

n has 2^(n-1) compositions. For each composition remove the largest part and redistribute it by adding 1 to subsequently smaller parts (creating 1's if needed) to get a new composition of n. (This is reversing the operation in A188160.) Repeat. Eventually this sequence of compositions will cycle. We are interested in the length of the period.
Let the indices k and j be uniquely associated with n using the triangular numbers T=A000217: T(k-1) < n <= T(k) and n = T(k-1) + j with 0 < j <= k.
a(n) with T(k-1) < n <= T(k) is the number of periods with length k for 1 < k.
If k is prime then all periods of the numbers T(k-1) < n < T(k) have length k.
If k is not prime, then the length of the periods is k or a divisor of k.
n = T(k-1) + j has binomial(k,j) partitions in its periods with 0 < j < k.
n = T(k-1) + j has c(n) = Sum_{d|gcd(k,j)} (phi(d)*binomial(k/d,j/d))/k periods of length k or a divisor of k as tabulated in A047996; phi is Euler's totient function. If k is prime then a(n)=c(n) gives the number of periods with length k. If k is not prime, subtract all periods of length < k from c(n).
Obtained from A092964 by adding an initial column of 1's and appending a 1 and 0 to each row. Obtained from A051168 by reading the array downwards along antidiagonals. - R. J. Mathar, Apr 14 2011
As a regular triangle, T(n,k) is the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and length k. Row sums are A059966. - Gus Wiseman, Dec 19 2017

			For k=5: T(4)=10 < n < T(5)=15 and all periods are of length 5:
a(11)=1 period: [(4+3+2+1+1), (4+3+2+2), (4+3+3+1), (4+4+2+1), (5+3+2+1)];
a(12)=2 periods: [(4+3+2+2+1), (4+3+3+2), (4+4+3+1), (5+4+2+1), (5+3+2+1+1)]; and [(4+4+2+2), (5+3+3+1), (4+4+2+1+1), (5+3+2+2), (4+3+3+1+1)];
a(13)=2 periods: [(4+4+2+2+1), (5+3+3+2), (4+4+3+1+1), (5+4+2+2), (5+3+3+1+1)]; and [(5+4+3+1), (5+4+2+1+1), (5+3+2+2+1), (4+3+3+2+1), (4+4+3+2)];
a(14)=1 period: [(5+4+3+2), (5+4+3+1+1), (5+4+2+2+1), (5+3+3+2+1), (4+4+3+2+1)].
For k=16; j=8; n=T(k-1)+j=128; 1<q|(16,8) --> {2,4,8} a(128) = c(128) - a(T(7)+4) - a(T(3)+2) - a(T(1)+1) =  810 - 8 - 1 - 1 = 800.
  (binomial(16,8)-8*a(T(7)+4)-4*a(T(3)+2)-2*a(T(1)+1))/16 = (12870-64-4-2)/16 = 800 = a(128).
Triangular view, with a(n) distributed in rows k=1,2,3.. according to T(k-1)< n <= T(k):
1;     k=1, n=1
1, 0;    k=2, n=2..3
1, 1,  0;    k=3, n=4..6
1, 1,  1,  0;    k=4, n=7..10
1, 2,  2,  1,   0;    k=5, n=11..15
1, 2,  3,  2,   1,   0;    k=6, n=16..21
1, 3,  5,  5,   3,   1,   0;
1, 3,  7,  8,   7,   3,   1,   0;
1, 4,  9, 14,  14,   9,   4,   1,   0;
1, 4, 12, 20,  25,  20,  12,   4,   1,  0;
1, 5, 15, 30,  42,  42,  30,  15,   5,  1,  0;
1, 5, 18, 40,  66,  75,  66,  40,  18,  5,  1, 0;
1, 6, 22, 55,  99, 132, 132,  99,  55, 22,  6, 1, 0;
1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1, 0;

R. Baumann, Computer-Knobelei, LOGIN (1987), 483-486 (in German).

Ethan Akin, Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250
J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982) 483-486

Cf. A000740, A001037, A008965, A051168, A059966, A060223, A245558, A294859, A296302, A296373, A092964, A245559, A245558.

A000217 := proc(n) n*(n+1)/2 ; end proc:
A185700 := proc(n) local k,j,a,q; k := ceil( (-1+sqrt(1+8*n))/2 ) ; j := n-A000217(k-1) ; if n = 1 then return 1; elif j = k then return 0 ; end if; a := binomial(k,j) ; if not isprime(k) then for q in numtheory[divisors]( igcd(k,j)) minus {1} do a := a- procname(j/q+A000217(k/q-1))*k/q ; end do: end if; a/k ; end proc:
seq(A185700(n),n=1..80) ; # R. J. Mathar, Jun 11 2011

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length@Select[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]===k&],LyndonQ],{n,10},{k,n}] (* Gus Wiseman, Dec 19 2017 *)

a(T(k))=0 with k > 1. a(1)=1.
If k is a prime number and n = T(k-1) + j with 0 < j < k, then a(n) = binomial(k,j)/k.
If k is not prime, subtract the sum of partitions in all periods of n with length < k from the term binomial(k,j). The difference divided by k gives the number of periods for n=T(k-1)+j: a(n)=( binomial(k,j) -sum {a(T(k/q-1)+j/q) *k/q })/k summed over all 1 < q|gcd(k,j).
If k is not prime, subtract the sum of all periods of n with length < k from the term c(n) = sum{ phi(d)*binomial(k/d,j/d) }/k summed over d|gcd(k,j), namely
  a(n) = c(n)-sum{a(T(k/q-1)+j))} summed over all 1 < q|gcd(k,j).

I have added a comment and deleted a Jun 11 2011 question from R. J. Mathar. - Paul Weisenhorn, Jan 08 2017

A037306 Triangle T(n,k) read by rows: the number of compositions of n into k parts, modulo cyclic shifts.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 4, 3, 1, 1, 1, 3, 5, 5, 3, 1, 1, 1, 4, 7, 10, 7, 4, 1, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 1, 5, 12, 22, 26, 22, 12, 5, 1, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 1, 6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1

Offset: 1

Jens Voß, Jun 30 2001

Triangle obtained from A047996 by dropping the first column (k=0), and row (n=0).
T(n, k) = number of different ways the number n can be expressed as ordered sums of k positive integers, counting only once those ordered sums that can be transformed into each other by a cyclic permutation.
These might be described as cyclic compositions, or more loosely as cyclic partitions. - N. J. A. Sloane, Sep 05 2012

			Triangle begins
  1;
  1,  1;
  1,  1,  1;
  1,  2,  1,  1;
  1,  2,  2,  1,  1;
  1,  3,  4,  3,  1,  1;
  1,  3,  5,  5,  3,  1,  1;
  1,  4,  7, 10,  7,  4,  1,  1;
  1,  4, 10, 14, 14, 10,  4,  1,  1;
  1,  5, 12, 22, 26, 22, 12,  5,  1,  1;
  1,  5, 15, 30, 42, 42, 30, 15,  5,  1,  1;
T(6,3) = 4, since there are 4 essentially different ways 1+1+4, 1+2+3, 1+3+2 and 2+2+2 of expressing 6 as a sum of 3 summands (all others can be obtained by cyclically permuting the summands in one of the above sums).

N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
Ethan Akin and Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250.
R. Baumann, Computer-Knobelei, , LOGIN, 163/164 (2010), 141-142 (in German).
R. Bekes, J. Pedersen and B. Shao, Mad tea party cyclic partitions, College Math. J., 43 (2012), 24-36.
A. Elashvili and M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006)
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173-188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
Arnold Knopfmacher and Neville Robbins, Some Properties of Cyclic Compositions, Fibonacci Quart. 48 (2010), no. 3, 249-255.
D. M. Y. Sommerville, On Certain Periodic Properties of Cyclic Compositions of Numbers, Proc. London Math. Soc., s2-7, No. 1 (1909), 263-313.
R. Razen, J. Seberry, and K. Wehrhahn, Ordered partitions and codes generated by circulant matrices, J. Combin. Theory Ser. A, 27 (1979), 333-341.
D. Wasserman, Proof of the symmetry [Broken link]
D. Wasserman, Proof of the symmetry [Cached copy]

A047996 and A241926 are essentially identical to this entry.
Cf. A008965 (row sums), A000010, A007318, A027750, A215251, A004526 (column 2), A007997 (column 3), A008610 (column 4), A008646 (column 5), A032191 (column 6).
See A245558, A245559 for a closely related array.
See A052307 for compositions modulo cyclic shifts and reversal.

a037306 n k = div (sum $ map f $ a027750_row $ gcd n k) n where
   f d = a000010 d * a007318' (div n d) (div k d)
a037306_row n = map (a037306 n) [1..n]
a037306_tabl = map a037306_row [1..]
-- Reinhard Zumkeller, Feb 06 2014

A037306 := proc(n,k) local a,d; a := 0; for d in numtheory[divisors]( igcd(n,k)) do a := a+numtheory[phi](d)*binomial(n/d,k/d); end do: a/n; end proc:
seq(seq(A037306(n,k), k=1..n), n=1..20); # R. J. Mathar, Jun 11 2011

t[n_, k_] := Total[EulerPhi[#]*Binomial[n/#, k/#] & /@ Divisors[GCD[n, k]]]/n; Flatten[Table[t[n, k], {n, 13}, {k, n}]] (* Jean-François Alcover, Sep 08 2011, after formula *)
nn=15;f[list_]:=Select[list,#>0&];Map[f,Transpose[Table[Drop[CoefficientList[Series[CycleIndex[CyclicGroup[n],s]/.Table[s[i]->x^i/(1-x^i),{i,1,n}],{x,0,nn}],x],1],{n,1,nn}]]]//Grid  (* Geoffrey Critzer, Oct 30 2012 *)

T(n, k) = sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d, k/d))/n; \\ Michel Marcus, Feb 10 2016

T(n,k) = (Sum_{d|gcd(n,k)} phi(d)*binomial(n/d,k/d))/n, where phi = A000010 = Euler's totient function. Also T(n,k) = A047996(n,k). - Paul Weisenhorn, Apr 06 2011

More terms from David Wasserman, Mar 11 2002

Comments, reference, example from Paul Weisenhorn, Dec 18 2010

A241926 Table read by antidiagonals: T(n,k) (n >= 1, k >= 1) is the number of necklaces with n black beads and k white beads.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 3, 4, 3, 1, 1, 3, 5, 5, 3, 1, 1, 4, 7, 10, 7, 4, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 5, 12, 22, 26, 22, 12, 5, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1

Offset: 1

Franklin T. Adams-Watters, May 02 2014

Turning over the necklace is not allowed (the group is cyclic not dihedral). T(n,k) = T(k,n) follows immediately from the formula. - N. J. A. Sloane, May 03 2014

T(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - Álvar Ibeas, Sep 21 2021

			The table starts:
  1, 1,  1,  1,  1,  1,   1,   1,   1,   1,   1,    1, ...
  1, 2,  2,  3,  3,  4,   4,   5,   5,   6,   6,    7, ...
  1, 2,  4,  5,  7, 10,  12,  15,  19,  22,  26,   31, ...
  1, 3,  5, 10, 14, 22,  30,  43,  55,  73,  91,  116, ...
  1, 3,  7, 14, 26, 42,  66,  99, 143, 201, 273,  364, ...
  1, 4, 10, 22, 42, 80, 132, 217, 335, 504, 728, 1038, ...
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Elashvili and M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233--238. MR1691428 (2000c:13006)
A. Elashvili, M. Jibladze and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
N. J. A. Sloane, A Note on Modular Partitions and Necklaces

Same as A047996 with first row and main diagonal removed.
A037306 is yet another version.
Cf. A003239 (main diagonal).
See A245558, A245559 for a closely related array.

# Maple program for the table - N. J. A. Sloane, May 03 2014:
with(numtheory);
T:=proc(n,k) local d, s, g, t0;
t0:=0; s:=n+k; g:=gcd(n,k);
for d from 1 to s do
   if (g mod d) = 0 then t0:=t0+phi(d)*binomial(s/d,k/d); fi;
od: t0/s; end;
r:=n->[seq(T(n,k),k=1..12)];
[seq(r(n),n=1..12)];

T[n_, k_] := DivisorSum[GCD[n, k], EulerPhi[#] Binomial[(n+k)/#, n/#]& ]/ (n+k); Table[T[n-k+1, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 02 2015 *)

T(n,k) = sumdiv(gcd(n,k),d,eulerphi(d)*binomial((n+k)\d,n\d))/(n+k)

T(n,k) = (Sum_{d | gcd(n,k)} phi(d)*binomial((n+k)/d, n/d))/(n+k). [Corrected by N. J. A. Sloane, May 03 2014]

Edited by N. J. A. Sloane, May 03 2014

Elashvili et al. references supplied by Vladimir Popov, May 17 2014

A245558 Square array read by antidiagonals: T(n,k) = number of n-tuples of nonnegative integers (u_0,...,u_{n-1}) satisfying Sum_{j=0..n-1} j*u_j == 1 mod n and Sum_{j=0..n-1} u_j = m.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 5, 5, 3, 1, 1, 3, 7, 8, 7, 3, 1, 1, 4, 9, 14, 14, 9, 4, 1, 1, 4, 12, 20, 25, 20, 12, 4, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1

Offset: 1

N. J. A. Sloane, Aug 07 2014

The array is symmetric; for the entries on or below the diagonal see A245559.
If the congruence in the definition is changed from Sum_{j=0..n-1} j*u_j == 1 mod n  to Sum_{j=0..n-1} j*u_j == 0 mod n we get the array shown in A241926, A047996, and A037306.
Differs from A011847 from row n = 9, k = 4 on; if the rows are surrounded by 0's, this yields A051168 without its rows 0 and 1, i.e., a(1) is A051168(2,1). - M. F. Hasler, Sep 29 2018
This array was first studied by Fredman (1975). - Petros Hadjicostas, Jul 10 2019

			Square array begins:
  1, 1,  1,  1,   1,   1,    1,    1,    1,    1, ...
  1, 1,  2,  2,   3,   3,    4,    4,    5,    5, ...
  1, 2,  3,  5,   7,   9,   12,   15,   18,   22, ...
  1, 2,  5,  8,  14,  20,   30,   40,   55,   70, ...
  1, 3,  7, 14,  25,  42,   66,   99,  143,  200, ...
  1, 3,  9, 20,  42,  75,  132,  212,  333,  497, ...
  1, 4, 12, 30,  66, 132,  245,  429,  715, 1144, ...
  1, 4, 15, 40,  99, 212,  429,  800, 1430, 2424, ...
  1, 5, 18, 55, 143, 333,  715, 1430, 2700, 4862, ...
  1, 5, 22, 70, 200, 497, 1144, 2424, 4862, 9225, ...
  ...
Reading by antidiagonals, we get:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,  1;
  1, 2,  3,  2,  1;
  1, 3,  5,  5,  3,   1;
  1, 3,  7,  8,  7,   3,   1;
  1, 4,  9, 14, 14,   9,   4,  1;
  1, 4, 12, 20, 25,  20,  12,  4,  1;
  1, 5, 15, 30, 42,  42,  30, 15,  5,  1;
  1, 5, 18, 40, 66,  75,  66, 40, 18,  5, 1;
  1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1;
  ...

Taylor Brysiewicz, Necklaces count polynomial parametric osculants, arXiv:1807.03408 [math.AG], 2018.
A. Elashvili, M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006).
A. Elashvili, M. Jibladze, D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173-188. MR1719140 (2000j:05009). See p. 174.
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 1993, 189-215, Theorem 9.4.
J. E. Iglesias, Enumeration of closest-packings by the space group: a simple approach, Z. Krist. 221 (2006) 237-245, eq. (5).

This array is very similar to but different from A011847.
Cf. A051168, A092964, A241926, A047996, A037306, A245559.
Rows include A001840, A006918, A051170, A011796, A011797, A031164. Main diagonal is A022553.

# To produce the first 10 rows and columns (as on page 174 of the Elashvili et al. 1999 reference):
with(numtheory):
cnk:=(n,k) -> add(mobius(n/d)*d, d in divisors(gcd(n,k)));
anmk:=(n,m,k)->(1/(n+m))*add( cnk(d,k)*binomial((n+m)/d,n/d), d in divisors(gcd(n,m))); # anmk(n,m,k) is the value of a_k(n,m) as in Theorem 1, Equation (4), of the Elashvili et al. 1999 reference.
r2:=(n,k)->[seq(anmk(n,m,k),m=1..10)];
for n from 1 to 10 do lprint(r2(n,1)); od:

rows = 12;
cnk[n_, k_] := Sum[MoebiusMu[n/d] d, {d , Divisors[GCD[n, k]]}];
anmk[n_, m_, k_] := (1/(n+m)) Sum[cnk[d, k] Binomial[(n+m)/d, n/d], {d, Divisors[GCD[n, m]]}];
r2[n_, k_] := Table[anmk[n, m, k], {m, 1, rows}];
T = Table[r2[n, 1], {n, 1, rows}];
Table[T[[n-k+1, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 05 2018, from Maple *)

cp's OEIS Frontend

A047996 Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A185700 The number of periods in a reshuffling operation for compositions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A037306 Triangle T(n,k) read by rows: the number of compositions of n into k parts, modulo cyclic shifts.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A241926 Table read by antidiagonals: T(n,k) (n >= 1, k >= 1) is the number of necklaces with n black beads and k white beads.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A245558 Square array read by antidiagonals: T(n,k) = number of n-tuples of nonnegative integers (u_0,...,u_{n-1}) satisfying Sum_{j=0..n-1} j*u_j == 1 mod n and Sum_{j=0..n-1} u_j = m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica