cp's OEIS Frontend

A087132 a(n) is the sum of the squares of the sizes of the conjugacy classes in the symmetric group S_n.

%I A087132 #49 Mar 29 2024 09:59:15
%S A087132 1,1,2,14,146,2602,71412,2675724,134269158,8747088662,717107850956,
%T A087132 72007758701716,8736187050160132,1258160557017484564,
%U A087132 212232765513231245096,41518913481377118146520,9309797624034705006898470,2374942651509463493006400390,683620331016710787068868581580
%N A087132 a(n) is the sum of the squares of the sizes of the conjugacy classes in the symmetric group S_n.
%C A087132 This is a natural quantity to consider when viewing the symmetric group (Sym_n) as a set. a(n) is the sum over all elements of Sym_n of the size of their conjugacy class. Each conjugacy class is thus counted as many times as its size, giving a sum of squares. - _Olivier Gérard_, Feb 12 2012
%H A087132 Alois P. Heinz, <a href="/A087132/b087132.txt">Table of n, a(n) for n = 0..254</a> (terms n = 1..57 from Vaclav Kotesovec)
%H A087132 Simon R. Blackburn, John R. Britnell, and Mark Wildon, <a href="http://arxiv.org/abs/1108.1784">The probability that a pair of elements of a finite group are conjugate</a>, arXiv:1108.1784 [math.GR], 2011-2012.
%H A087132 Philippe Flajolet, Éric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, <a href="https://arxiv.org/abs/math/0606370">A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics</a>, arXiv:math/0606370 [math.CO], 2006.
%F A087132 a(n) = (n!)^2 * (c/n^2 + O((log n)/n^3)), where c = prod_{k>=1}sum_{n>=0}1/(k*n!)^2 ~ 4.263403514152669778298935... (see A246879). [Corrected by _Vaclav Kotesovec_, Sep 21 2014]
%p A087132 b:= proc(n, i) option remember; uses combinat; `if`(n=0, 1,
%p A087132       `if`(i<1, 0, add(b(n-i*j, i-1)*((i-1)!^j/j!*
%p A087132        multinomial(n, n-i*j, i$j, 0))^2, j=0..n/i)))
%p A087132     end:
%p A087132 a:= n-> b(n$2):
%p A087132 seq(a(n), n=0..21);  # _Alois P. Heinz_, Jul 27 2023
%t A087132 multinomial[n_, k_List] := n! / Times @@ (k!);
%t A087132 b[n_, i_] := b[n, i] = If[n == 0, 1,
%t A087132     If[i < 1, 0, Sum[b[n-i*j, i-1]*((i-1)!^j/j!*
%t A087132     multinomial[n, {n-i*j, Sequence@@Table[i, {j}], 0}])^2, {j, 0, n/i}]]];
%t A087132 a[n_] := b[n, n];
%t A087132 Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Mar 29 2024, after _Alois P. Heinz_ *)
%o A087132 (Magma) [ &+[ c[2]^2 : c in ClassesData(Sym(n))] : n in [1..10]]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
%Y A087132 Cf. A000041, A073906, A192983, A206820. - _Olivier Gérard_, Feb 12 2012
%Y A087132 Cf. A000142, A246879.
%K A087132 nonn
%O A087132 0,3
%A A087132 Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 18 2003
%E A087132 More terms from _Vladeta Jovovic_, Oct 22 2003
%E A087132 More terms from _Vaclav Kotesovec_, Sep 21 2014
%E A087132 a(0)=1 prepended by _Alois P. Heinz_, Jul 27 2023