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).
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
KEYWORD
nonn
AUTHOR
Stephen P. Humphries, Jun 20 2013
STATUS
approved