|
%I #67 Nov 03 2023 11:03:18
%S 1,1,2,3,7,12,43,127,544,2361,11703,61690,351773,2126497,13639372,
%T 92197523,655035769,4874404108,37893370473,306986431847,2586209749712,
%U 22612848403571,204850732480285,1919652428481930,18581619724363401,185543613289200949
%N Set partitions up to rotations.
%C 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
%C Equivalently, number of n-bead necklaces using any number of unlabeled (interchangable) colors. - _Andrew Howroyd_, Sep 25 2017
%H Alois P. Heinz, <a href="/A084423/b084423.txt">Table of n, a(n) for n = 0..500</a> (first 61 terms from Franklin T. Adams-Watters)
%H Colin Adams, Chaim Even-Zohar, Jonah Greenberg, Reuben Kaufman, David Lee, Darin Li, Dustin Ping, Theodore Sandstrom, and Xiwen Wang, <a href="https://arxiv.org/abs/2103.08314">Virtual Multicrossings and Petal Diagrams for Virtual Knots and Links</a>, arXiv:2103.08314 [math.GT], 2021.
%H Robert M. Dickau, <a href="https://web.archive.org/web/20190331234613/http://mathforum.org/advanced/robertd/bell.html">Bell number diagrams</a>
%H Wouter Meeussen, <a href="http://users.telenet.be/Wouter.Meeussen/SetPartitionsUpToRotations.nb">Set Partitions Up To Rotation</a>
%H Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Partition_related_number_triangles#rot">Partition related number triangles</a>
%F a(p) = (Bell(p)+2*(p-1))/p for prime p; cf. A079609. - _Vladeta Jovovic_, Jul 04 2003
%F 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
%F a(n) = [n==0] + [n>0] * (1/n) * Sum_{d|n} phi(d) * A162663(n/d,d). - _Robert A. Russell_, Jun 10 2018
%F From _Richard L. Ollerton_, May 09 2021: (Start)
%F For n >= 1:
%F a(n) = (1/n)*Sum_{k=1..n} A162663(gcd(n,k),n/gcd(n,k)).
%F 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)
%e Of the Bell(4) = 15 set partitions of 4, only 7 remain distinct under rotation:
%e {{1,2,3,4}},
%e {{1}, {2,3,4}},
%e {{1,2}, {3,4}},
%e {{1,3}, {2,4}},
%e {{1}, {2}, {3,4}},
%e {{1}, {3}, {2,4}},
%e {{1}, {2}, {3}, {4}}}
%t <<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}]
%t (* Second program (not needing Combinatorica): *)
%t 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_ *)
%o (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. */
%o a(n) = sumdiv(n,j,eulerphi(j)*U(n\j,j))/n \\ _Franklin T. Adams-Watters_, Jun 09 2008
%o (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
%Y Cf. A080107, A084708, A152175.
%K nonn,nice
%O 0,3
%A _Wouter Meeussen_, Jun 26 2003
%E More terms from _Robert G. Wilson v_, Jun 27 2003
%E More terms from _Franklin T. Adams-Watters_, Jun 09 2008
|
