|
| |
|
|
A084423
|
|
Set partitions up to rotations.
|
|
6
| |
|
|
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
(list; graph; refs; listen; history; 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 (FrankTAW(AT)Netscape.net), Jun 09 2008
|
|
|
LINKS
| Franklin T. Adams-Watters, Table of n, a(n) for n = 0..60
Robert M. Dickau, Bell number diagrams
Wouter Meeussen, Set Partitions Up To Rotation
|
|
|
FORMULA
| a(p) = (Bell(p)+2*(p-1))/p for prime p; cf. A079609. - Vladeta Jovovic (vladeta(AT)eunet.rs), 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 (FrankTAW(AT)Netscape.net), 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}]
|
|
|
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 (FrankTAW(AT)Netscape.net), Jun 09 2008
|
|
|
CROSSREFS
| Cf. A080107, A000110.
Cf. A000041.
Sequence in context: A143879 A056293 A056294 * A068134 A081256 A084955
Adjacent sequences: A084420 A084421 A084422 * A084424 A084425 A084426
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| Wouter Meeussen (wouter.meeussen(AT)pandora.be), Jun 26 2003
|
|
|
EXTENSIONS
| More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Jun 27 2003
More terms from Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Jun 09 2008
|
| |
|
|
