A261494 Number A(n,k) of necklaces with n white beads and k*n black beads; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 4, 10, 10, 1, 1, 1, 5, 19, 43, 26, 1, 1, 1, 6, 31, 116, 201, 80, 1, 1, 1, 7, 46, 245, 776, 1038, 246, 1, 1, 1, 8, 64, 446, 2126, 5620, 5538, 810, 1, 1, 1, 9, 85, 735, 4751, 19811, 42288, 30667, 2704, 1

Offset: 0

Author

Alois P. Heinz, Aug 21 2015

Keywords

• nonn
• tabl

Comments

For k>=1 is column k asymptotic to (k+1)^((k+1)*n-1/2) / (sqrt(2*Pi) * k^(k*n+1/2) * n^(3/2)). - Vaclav Kotesovec, Aug 22 2015

Examples

			A(2,2) = 3: 000011, 000101, 001001.
A(3,2) = 10: 000000111, 000001011, 000010011, 000100011, 001000011, 010000011, 000010101, 000100101, 001000101, 001001001.
Square array A(n,k) begins:
  1,  1,    1,    1,     1,     1,      1, ...
  1,  1,    1,    1,     1,     1,      1, ...
  1,  2,    3,    4,     5,     6,      7, ...
  1,  4,   10,   19,    31,    46,     64, ...
  1, 10,   43,  116,   245,   446,    735, ...
  1, 26,  201,  776,  2126,  4751,   9276, ...
  1, 80, 1038, 5620, 19811, 54132, 124936, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• Eric Weisstein's World of Mathematics, Necklace
• Wikipedia, Necklace (combinatorics)
• Index entries for sequences related to necklaces

Crossrefs

Columns k=0-10 give: A000012, A003239, A082936, A261497, A261498, A261499, A261500, A261501, A261502, A261503, A261504.

Main diagonal gives A261495.

Lower diagonal gives A261496.

Cf. A000010.

Programs

Maple

with(numtheory):
A:= (n, k)-> `if`(n=0, 1, add(binomial((k+1)*n/d, n/d)
                    *phi(d), d=divisors(n))/((k+1)*n)):
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

A[n_, k_] := If[n==0, 1, DivisorSum[n, Binomial[(k+1)*n/#, n/#]*EulerPhi[#] /((k+1)*n)&]]; Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 19 2017, translated from Maple *)

PARI

a(n,k) = if(n<1, 1, sumdiv(n, d, binomial((k + 1)*n/d, n/d) * eulerphi(d)) / ((k + 1)*n));
for(d=0, 14, for(n=0, d, print1(a(n, d - n),", ");); print();) \\ Indranil Ghosh, Mar 25 2017

Formula

A(n,k) = 1/((k+1)*n) * Sum_{d|n} C((k+1)*n/d,n/d) * A000010(d) for n>0, A(0,k) = 1.

A(n,k) = 1/((k+1)*n)*Sum_{i=1..n} C((k+1)*gcd(n,i),gcd(n,i)) = 1/((k+1)*n)*Sum_{i=1..n} C((k+1)*n/gcd(n,i),n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)) for n >= 1, where phi = A000010. - Richard L. Ollerton, May 19 2021