A084423 Set partitions up to rotations.

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

Offset: 0

Author

Wouter Meeussen, Jun 26 2003

Keywords

• nonn
• nice

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

Examples

			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}}.
		

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
• Wouter Meeussen, Set Partitions Up To Rotation
• Tilman Piesk, Partition related number triangles

Crossrefs

Cf. A080107, A084708, A152175.

Programs

Mathematica

<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 *)

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

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)

Extensions

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

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