login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A261531 Number of necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct. 4
1, 1, 1, 2, 2, 4, 15, 25, 69, 254, 1799, 4039, 16828, 61751, 349831, 3485031, 10391139, 49433136, 240065255, 1282012987, 9167583734, 131550812011, 459677216341, 2707382738559, 14318807603110, 94084166753927, 601900541251447, 5894253303715375 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..260

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

FORMULA

a(n) = (1/n) * Sum_{d | n} phi(n/d) * A007837(d) for n>0. - Andrew Howroyd, Apr 02 2017

EXAMPLE

a(4) = 2: 0000, 0001.

a(5) = 4: 00000, 00001, 00011, 00101.

a(6) = 15: 000000, 000001, 000011, 000101, 000112, 000121, 000122, 001001, 001012, 001021, 001022, 001102, 001201, 001202, 010102.

MAPLE

with(numtheory): with(combinat):

g:= l-> (n-> `if`(n=0, 1, add(phi(j)*multinomial(n/j,

        (l/j)[]), j=divisors(igcd(l[])))/n))(add(i, i=l)):

b:= proc(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, [l[], i]))))

    end:

a:= n-> b(n$2, []):

seq(a(n), n=0..35);

MATHEMATICA

multinomial[n_, k_] := n!/Times @@ (k!);

g[l_] := Function[n, If[n==0, 1, Sum[EulerPhi[j]*multinomial[n/j, l/j], {j, Divisors[GCD @@ l]}]/n]][Total[l]];

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]]]]];

a[n_] := b[n, n, {}];

Table[a[n], {n, 0, 35}] (* Jean-Fran├žois Alcover, Mar 21 2017, translated from Maple *)

PROG

(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

CROSSREFS

Cf. A072605, A261599, A261600.

Sequence in context: A205310 A222924 A268423 * A153968 A153965 A121221

Adjacent sequences:  A261528 A261529 A261530 * A261532 A261533 A261534

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Aug 23 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 1 03:36 EDT 2020. Contains 337441 sequences. (Running on oeis4.)