A072605 Number of necklaces with n beads over an n-ary alphabet {a1,a2,...,an} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 0, where #(w,x) counts the letters x in word w.
1, 1, 2, 4, 13, 50, 270, 1641, 11945, 96784, 887982, 8939051, 99298354, 1195617443, 15619182139, 219049941201, 3293800835940, 52746930894774, 897802366250126, 16167544246362567, 307372573011579188, 6148811682561390279, 129164845357784003661
Offset: 0
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..200
- Frank 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, Necklaces
Programs
-
Mathematica
neck[li:{__Integer}] := Module[{n, d}, n=Plus@@li; d=n-First[li]; Fold[ #1+(EulerPhi[ #2]*(n/#2)!)/Times@@((li/#2)!)&, 0, Divisors[GCD@@li]]/n]; Table[ Plus@@(neck /@ IntegerPartitions[n]), {n, 24}] -
PARI
a(n)={if(n==0, 1, my(p=prod(k=1, n, 1/(1-x^k/k!) + O(x*x^n))); sumdiv(n, d, eulerphi(n/d)*d!*polcoeff(p,d))/n)} \\ Andrew Howroyd, Dec 20 2017
Formula
a(n) = (1/n) * Sum_{d|n} phi(n/d) * A005651(d) for n > 0. - Andrew Howroyd, Sep 25 2017
See Mathematica line.
a(n) ~ c * (n-1)!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264818011615... . - Vaclav Kotesovec, Aug 27 2015
Extensions
a(0)=1 prepended by Alois P. Heinz, Aug 23 2015
Name changed by Andrew Howroyd, Sep 25 2017