login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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: A002874 A324961 A078592 * A052646 A320343 A002856

Adjacent sequences:  A225105 A225106 A225107 * A225109 A225110 A225111

KEYWORD

nonn

AUTHOR

Stephen P. Humphries, Jun 20 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 21 15:00 EST 2019. Contains 329371 sequences. (Running on oeis4.)