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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A084423 Set partitions up to rotations. 14
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

a(n) = [n==0] + [n>0] * (1/n) * Sum_{d|n} phi(d) * A162663(n/d,d). - Robert A. Russell, Jun 10 2018

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

(PARI) seq(n)={Vec(1 + intformal(sum(m=1, n, eulerphi(m)*subst(serlaplace(-1 + exp(sumdiv(m, d, (exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))} \\ Andrew Howroyd, Sep 20 2019

CROSSREFS

Cf. A080107, A084708, A152175.

Sequence in context: A056293 A275311 A056294 * A068134 A249051 A329413

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 16 04:05 EST 2019. Contains 330013 sequences. (Running on oeis4.)