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,9

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

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

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

Example

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, ...

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 *)

Prog

(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

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.

Sequence in context: A306684 A293991 A288638 * A365673 A349574 A168377

Adjacent sequences: A261491 A261492 A261493 * A261495 A261496 A261497

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 21 2015

Status

approved