cp's OEIS Frontend

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.

%I A072605 #51 Feb 16 2025 08:32:46
%S A072605 1,1,2,4,13,50,270,1641,11945,96784,887982,8939051,99298354,
%T A072605 1195617443,15619182139,219049941201,3293800835940,52746930894774,
%U A072605 897802366250126,16167544246362567,307372573011579188,6148811682561390279,129164845357784003661
%N 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.
%H A072605 Alois P. Heinz, <a href="/A072605/b072605.txt">Table of n, a(n) for n = 0..200</a>
%H A072605 Frank Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A072605 F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A072605 Eric Weisstein's world of Mathematics, <a href="https://mathworld.wolfram.com/Necklace.html">Necklaces</a>
%F A072605 a(n) = (1/n) * Sum_{d|n} phi(n/d) * A005651(d) for n > 0. - _Andrew Howroyd_, Sep 25 2017
%F A072605 See Mathematica line.
%F A072605 a(n) ~ c * (n-1)!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264818011615... . - _Vaclav Kotesovec_, Aug 27 2015
%t A072605 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}]
%o A072605 (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
%Y A072605 Cf. A005651, A052307, A247551, A261531, A261599, A261600.
%K A072605 easy,nonn
%O A072605 0,3
%A A072605 _Wouter Meeussen_, Aug 06 2002
%E A072605 a(0)=1 prepended by _Alois P. Heinz_, Aug 23 2015
%E A072605 Name changed by _Andrew Howroyd_, Sep 25 2017