0,3

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

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

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)

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

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

(* Alternative: (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

Cf. A080107, A084708, A152175.

Sequence in context: A056293 A275311 A056294 * A361910 A068134 A249051

Adjacent sequences: A084420 A084421 A084422 * A084424 A084425 A084426

nonn,nice

Wouter Meeussen, Jun 26 2003

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

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

approved