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

Author

Alois P. Heinz, Feb 24 2012

Keywords

• nonn
• tabl

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)

Examples

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

Links

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

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.

Programs

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

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