A208183 Number of distinct k-colored necklaces with n beads per color; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 6, 16, 4, 1, 1, 1, 24, 318, 188, 10, 1, 1, 1, 120, 11352, 30804, 2896, 26, 1, 1, 1, 720, 623760, 11211216, 3941598, 50452, 80, 1, 1, 1, 5040, 48648960, 7623616080, 15277017432, 586637256, 953056, 246, 1, 1

Offset

0,12

Comments

From Vaclav Kotesovec, Aug 23 2015: (Start)

Column k > 1 is asymptotic to k^(k*n-1/2) / ((2*Pi)^((k-1)/2) * n^((k+1)/2)).

Row r > 0 is asymptotic to (r*n)! / (r*n*(r!)^n). (End)

Links

Alois P. Heinz, Antidiagonals n = 0..35, flattened

Formula

A(n,k) = Sum_{d|n} phi(n/d)*(k*d)!/(d!^k*k*n) if n,k>0; A(n,k) = 1 else.

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

Example

A(1,4) =  6: {0123, 0132, 0213, 0231, 0312, 0321}.
A(3,2) =  4: {000111, 001011, 010011, 010101}.
A(4,2) = 10: {00001111, 00010111, 00100111, 01000111, 00011011, 00110011, 00101011, 01010011, 01001011, 01010101}.
Square array A(n,k) begins:
  1, 1,  1,     1,         1,              1, ...
  1, 1,  1,     2,         6,             24, ...
  1, 1,  2,    16,       318,          11352, ...
  1, 1,  4,   188,     30804,       11211216, ...
  1, 1, 10,  2896,   3941598,    15277017432, ...
  1, 1, 26, 50452, 586637256, 24934429725024, ...

Maple

with(numtheory):
A:= (n, k)-> `if`(n=0 or k=0, 1,
              add(phi(n/d) *(k*d)!/(d!^k *k*n), d=divisors(n))):
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

A[n_, k_] :=  If[n == 0 || k == 0, 1, Sum[EulerPhi[n/d]*(k*d)!/(d!^k*k*n), {d, Divisors[n]}]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

Crossrefs

Rows n=0-8 give: A000012, A104150, A137729, A208184, A208185, A208186, A208187, A208188, A208189.

Columns k=0+1, 2-8 give: A000012, A003239, A118644, A207816, A208190, A208191, A208192, A208193.

Main diagonal gives A252765.

Cf. A000010, A000142.

Sequence in context: A253586 A347621 A318191 * A214810 A257248 A090737

Adjacent sequences: A208180 A208181 A208182 * A208184 A208185 A208186

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 24 2012

Status

approved