login
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
1, 2, 8, 42, 288, 2280, 21600, 226800, 2701440, 35199360, 504403200, 7783776000, 130288435200, 2322678758400, 44286571929600, 894449267712000, 19144352747520000, 431093162852352000, 10224590808047616000, 253873324553232384000, 6602896050191400960000
OFFSET
1,2
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.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..442
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
EXAMPLE
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.
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 *)
PROG
(Magma)
s:=0;
for k:=0 to n-1 do
s:=s+Factorial(n-1)*NumberOfPartitions(n-1-k);
end for;
(PARI) a(n)=n--!*sum(k=0, n, numbpart(n-k)) \\ Charles R Greathouse IV, Jun 28 2013
CROSSREFS
Sequence in context: A324961 A351814 A078592 * A052646 A352646 A320343
KEYWORD
nonn
AUTHOR
STATUS
approved