login
A087132
a(n) is the sum of the squares of the sizes of the conjugacy classes in the symmetric group S_n.
5
1, 1, 2, 14, 146, 2602, 71412, 2675724, 134269158, 8747088662, 717107850956, 72007758701716, 8736187050160132, 1258160557017484564, 212232765513231245096, 41518913481377118146520, 9309797624034705006898470, 2374942651509463493006400390, 683620331016710787068868581580
OFFSET
0,3
COMMENTS
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
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..254 (terms n = 1..57 from Vaclav Kotesovec)
Simon R. Blackburn, John R. Britnell, and Mark Wildon, The probability that a pair of elements of a finite group are conjugate, arXiv:1108.1784 [math.GR], 2011-2012.
Philippe Flajolet, Éric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, arXiv:math/0606370 [math.CO], 2006.
FORMULA
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]
MAPLE
b:= proc(n, i) option remember; uses combinat; `if`(n=0, 1,
`if`(i<1, 0, add(b(n-i*j, i-1)*((i-1)!^j/j!*
multinomial(n, n-i*j, i$j, 0))^2, j=0..n/i)))
end:
a:= n-> b(n$2):
seq(a(n), n=0..21); # Alois P. Heinz, Jul 27 2023
MATHEMATICA
multinomial[n_, k_List] := n! / Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1,
If[i < 1, 0, Sum[b[n-i*j, i-1]*((i-1)!^j/j!*
multinomial[n, {n-i*j, Sequence@@Table[i, {j}], 0}])^2, {j, 0, n/i}]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Mar 29 2024, after Alois P. Heinz *)
PROG
(Magma) [ &+[ c[2]^2 : c in ClassesData(Sym(n))] : n in [1..10]]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
CROSSREFS
Sequence in context: A354286 A346432 A333592 * A036079 A121227 A250916
KEYWORD
nonn
AUTHOR
Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 18 2003
EXTENSIONS
More terms from Vladeta Jovovic, Oct 22 2003
More terms from Vaclav Kotesovec, Sep 21 2014
a(0)=1 prepended by Alois P. Heinz, Jul 27 2023
STATUS
approved