login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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
Alois P. Heinz, Table of n, a(n) for n = 0..500 (first 61 terms from Franklin T. Adams-Watters)
Colin Adams, Chaim Even-Zohar, Jonah Greenberg, Reuben Kaufman, David Lee, Darin Li, Dustin Ping, Theodore Sandstrom, and Xiwen Wang, Virtual Multicrossings and Petal Diagrams for Virtual Knots and Links, arXiv:2103.08314 [math.GT], 2021.
Robert M. Dickau, Bell number diagrams
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
From Richard L. Ollerton, May 09 2021: (Start)
For n >= 1:
a(n) = (1/n)*Sum_{k=1..n} A162663(gcd(n,k),n/gcd(n,k)).
a(n) = (1/n)*Sum_{k=1..n} A162663(n/gcd(n,k),gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
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}]
(* Second program (not needing Combinatorica): *)
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
Sequence in context: A056293 A275311 A056294 * A361910 A068134 A249051
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)