A261495 Number of necklaces with n white beads and n^2 black beads.

1, 1, 3, 19, 245, 4751, 124936, 4141383, 166237161, 7847250409, 426342182761, 26219808548110, 1801378010581175, 136784412621194274, 11378390032696241010, 1029218687419565103111, 100592759623604055645649, 10565465772302876757883823, 1186893721789951847976898669

Offset: 0

Author

Alois P. Heinz, Aug 21 2015

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..335
• 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

Main diagonal of A261494.

Programs

Maple

with(numtheory):
a:= n-> `if`(n=0, 1, add(binomial((n^2+n)/d, n/d)
             *phi(d), d=divisors(n))/(n^2+n)):
seq(a(n), n=0..20);

Mathematica

a[n_] := If[n==0, 1, DivisorSum[n, Binomial[(n^2+n)/#, n/#]*EulerPhi[#]&]/ (n^2 + n)];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 25 2017, translated from Maple *)

PARI

a(n) = if(n<1, 1, sumdiv(n, d, binomial((n^2 + n)/d, n/d) * eulerphi(d)) / (n^2 + n));
for(n=0, 20, print1(a(n),", ")) \\ Indranil Ghosh, Mar 25 2017

Formula

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

a(n) ~ exp(n+1/2) * n^(n-5/2) / sqrt(2*Pi). - Vaclav Kotesovec, Aug 22 2015