login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A084423 Set partitions up to rotations. 9
1, 1, 2, 3, 7, 12, 43, 127, 544, 2361, 11703, 61690, 351773, 2126497, 13639372, 92197523, 655035769, 4874404108, 37893370473, 306986431847, 2586209749712, 22612848403571, 204850732480285, 1919652428481930, 18581619724363401, 185543613289200949 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Partitions of n objects distinct under the cyclic group, C_n. By comparison the partition numbers (A000041) are the partitions distinct under the symmetric group, S_n and the set partitions are those distinct under the discrete group containing only the identity. - Franklin T. Adams-Watters, Jun 09 2008

Equivalently, number of n-bead necklaces using any number of unlabeled (interchangable) colors. - Andrew Howroyd, Sep 25 2017

LINKS

Franklin T. Adams-Watters and Alois P. Heinz, Table of n, a(n) for n = 0..500 (first 61 terms from Franklin T. Adams-Watters)

Robert M. Dickau, Bell number diagrams

Wouter Meeussen, Set Partitions Up To Rotation

Tilman Piesk, Partition related number triangles

FORMULA

a(p) = (Bell(p)+2*(p-1))/p for prime p; cf. A079609. - Vladeta Jovovic, Jul 04 2003

U(k,j) = 1 if k=0, else Sum_{i=1..k} C(k-1,i-1) Sum_{d|j} U(k-i,j)*d^{i-1}. Then a(n) = (Sum_{j|n} phi(j)*U(n/j,j))/n. (U(k,j) is the number of partitions invariant under a permutation with k cycles of j objects each.) - Franklin T. Adams-Watters, Jun 09 2008

EXAMPLE

Of the Bell(4) = 15 set partitions of 4, only 7 remain distinct under rotation:

{{1,2,3,4}},

{{1}, {2,3,4}},

{{1,2}, {3,4}},

{{1,3}, {2,4}},

{{1}, {2}, {3,4}},

{{1}, {3}, {2,4}},

{{1}, {2}, {3}, {4}}}

MATHEMATICA

<<DiscreteMath`Combinatorica`; shrink[n_Integer] := Union[ First[ Sort[ NestList[Sort[Sort /@ ( #/.i_Integer:>Mod[i+1, n, 1])]&, #, n]]]& /@ SetPartitions[n]]; Table[ Length[ shrink[k]], {k, 11}]

u[0, _] = 1; u[k_, j_] := u[k, j] = Sum[Binomial[k-1, i-1]*Sum[u[k-i, j]*d^(i-1), {d, Divisors[j]}], {i, 1, k}]; a[n_] := Sum[EulerPhi[j]*u[n/j, j], {j, Divisors[n]}]/n; a[0] = 1; Table[a[n], {n, 0, 24}] (* Jean-Fran├žois Alcover, May 14 2012, after Franklin T. Adams-Watters *)

PROG

(PARI) U(k, j) = if(k==0, 1, sum(i=1, k, binomial(k-1, i-1)*sumdiv(j, d, U(k-i, j) *d^(i-1)))) /* U is unoptimized; should remember previous values. */

a(n) = sumdiv(n, j, eulerphi(j)*U(n\j, j))/n \\ Franklin T. Adams-Watters, Jun 09 2008

CROSSREFS

Cf. A080107, A152175.

Sequence in context: A056293 A275311 A056294 * A068134 A249051 A225093

Adjacent sequences:  A084420 A084421 A084422 * A084424 A084425 A084426

KEYWORD

nonn,nice

AUTHOR

Wouter Meeussen, Jun 26 2003

EXTENSIONS

More terms from Robert G. Wilson v, Jun 27 2003

More terms from Franklin T. Adams-Watters, Jun 09 2008

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 19:36 EST 2018. Contains 299469 sequences. (Running on oeis4.)