|
%I #34 Sep 08 2022 08:46:04
%S 1,2,8,42,288,2280,21600,226800,2701440,35199360,504403200,7783776000,
%T 130288435200,2322678758400,44286571929600,894449267712000,
%U 19144352747520000,431093162852352000,10224590808047616000,253873324553232384000,6602896050191400960000
%N 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.
%C 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.
%H Charles R Greathouse IV, <a href="/A225108/b225108.txt">Table of n, a(n) for n = 1..442</a>
%F a(n) = Sum_{k=0..n-1} (n-1)!*p(n-1-k) where p is the partition function (A000041).
%F a(n) = A000142(n-1) * A000070(n-1). - _Alois P. Heinz_, Jun 27 2013
%e 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:
%e [ 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.
%p with(combinat):
%p a:= n-> (n-1)! * add(numbpart(k), k=0..n-1):
%p seq(a(n), n=1..25); # _Alois P. Heinz_, Jun 27 2013
%t a[n_] := Sum[(n-1)! PartitionsP[n-1-k], {k, 0, n-1}]; Array[a, 25] (* _Jean-François Alcover_, Jan 17 2016 *)
%o (Magma)
%o s:=0;
%o for k:=0 to n-1 do
%o s:=s+Factorial(n-1)*NumberOfPartitions(n-1-k);
%o end for;
%o (PARI) a(n)=n--!*sum(k=0,n,numbpart(n-k)) \\ _Charles R Greathouse IV_, Jun 28 2013
%K nonn
%O 1,2
%A _Stephen P. Humphries_, Jun 20 2013
|
