A225108 Number of pairs (x,y) of elements x of the symmetric group S_{n-1} and y of the symmetric group S_{n} that commute. Here the symmetric group S_{n-m} is to be thought of as the subgroup of the symmetric group S_n which stabilizes n-m+1,n-m+2,...n.

1, 2, 8, 42, 288, 2280, 21600, 226800, 2701440, 35199360, 504403200, 7783776000, 130288435200, 2322678758400, 44286571929600, 894449267712000, 19144352747520000, 431093162852352000, 10224590808047616000, 253873324553232384000, 6602896050191400960000

Offset: 1

Author

Stephen P. Humphries, Jun 20 2013

Keywords

• nonn

Comments

We have a formula for the number of pairs (x,y) of elements x of the symmetric group S_{n-m} and y of the symmetric group S_{n} that commute.

Examples

			When n=2 every element of S_1 commutes with every element of S_2, so we get a(2) = 2. When n=3 the following are the 8 commuting pairs:
[ Id, Id], [ Id, (1, 2)], [ Id, (1, 3, 2)], [ Id, (1, 2, 3)], [ Id, (1, 3)], [ Id, (2, 3)], [ (1, 2), (1, 2)], [ (1, 2), Id ] where Id is the identity element.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..442

Programs

Magma

s:=0;
for k:=0 to n-1 do
    s:=s+Factorial(n-1)*NumberOfPartitions(n-1-k);
end for;

Maple

with(combinat):
a:= n-> (n-1)! * add(numbpart(k), k=0..n-1):
seq(a(n), n=1..25);  # Alois P. Heinz, Jun 27 2013

Mathematica

a[n_] := Sum[(n-1)! PartitionsP[n-1-k], {k, 0, n-1}]; Array[a, 25] (* Jean-François Alcover, Jan 17 2016 *)

PARI

a(n)=n--!*sum(k=0,n,numbpart(n-k)) \\ Charles R Greathouse IV, Jun 28 2013

Formula

a(n) = Sum_{k=0..n-1} (n-1)!*p(n-1-k) where p is the partition function (A000041).

a(n) = A000142(n-1) * A000070(n-1). - Alois P. Heinz, Jun 27 2013