cp's OEIS Frontend

A261531 Number of necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.

%I A261531 #37 Feb 16 2025 08:33:26
%S A261531 1,1,1,2,2,4,15,25,69,254,1799,4039,16828,61751,349831,3485031,
%T A261531 10391139,49433136,240065255,1282012987,9167583734,131550812011,
%U A261531 459677216341,2707382738559,14318807603110,94084166753927,601900541251447,5894253303715375
%N A261531 Number of necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.
%H A261531 Alois P. Heinz, <a href="/A261531/b261531.txt">Table of n, a(n) for n = 0..260</a>
%H A261531 F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A261531 F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A261531 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Necklace.html">Necklace</a>
%H A261531 Wikipedia, <a href="https://en.wikipedia.org/wiki/Necklace_(combinatorics)">Necklace (combinatorics)</a>
%H A261531 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A261531 a(n) = (1/n) * Sum_{d | n} phi(n/d) * A007837(d) for n>0. - _Andrew Howroyd_, Apr 02 2017
%e A261531 a(4) = 2: 0000, 0001.
%e A261531 a(5) = 4: 00000, 00001, 00011, 00101.
%e A261531 a(6) = 15: 000000, 000001, 000011, 000101, 000112, 000121, 000122, 001001, 001012, 001021, 001022, 001102, 001201, 001202, 010102.
%p A261531 with(numtheory): with(combinat):
%p A261531 g:= l-> (n-> `if`(n=0, 1, add(phi(j)*multinomial(n/j,
%p A261531         (l/j)[]), j=divisors(igcd(l[])))/n))(add(i, i=l)):
%p A261531 b:= proc(n, i, l) `if`(i*(i+1)/2<n, 0,`if`(n=0, g(l),
%p A261531       b(n, i-1, l)+`if`(i>n, 0, b(n-i, i-1, [l[], i]))))
%p A261531     end:
%p A261531 a:= n-> b(n$2, []):
%p A261531 seq(a(n), n=0..35);
%t A261531 multinomial[n_, k_] := n!/Times @@ (k!);
%t A261531 g[l_] := Function[n, If[n==0, 1, Sum[EulerPhi[j]*multinomial[n/j, l/j], {j, Divisors[GCD @@ l]}]/n]][Total[l]];
%t A261531 b[n_, i_, l_] := If[i*(i+1)/2<n, 0, If[n==0, g[l], b[n, i-1, l] + If[i>n, 0, b[n-i, i-1, Append[l, i]]]]];
%t A261531 a[n_] := b[n, n, {}];
%t A261531 Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Mar 21 2017, translated from Maple *)
%o A261531 (PARI) a(n)={if(n==0, 1, my(p=prod(k=1, n, (1+x^k/k!) + O(x*x^n))); sumdiv(n, d, eulerphi(n/d)*d!*polcoeff(p, d))/n)} \\ _Andrew Howroyd_, Dec 21 2017
%Y A261531 Cf. A072605, A261599, A261600.
%K A261531 nonn
%O A261531 0,4
%A A261531 _Alois P. Heinz_, Aug 23 2015