A001189 -id:A001189 - cp's OEIS frontend

A378163 Triangle read by rows: T(n,k) is the number of subgroups of S_n isomorphic to S_k, where S_n is the n-th symmetric group.

1, 1, 1, 1, 3, 1, 1, 9, 4, 1, 1, 25, 20, 5, 1, 1, 75, 160, 60, 12, 1, 1, 231, 910, 560, 84, 7, 1, 1, 763, 5936, 5740, 560, 56, 8, 1, 1, 2619, 53424, 58716, 3276, 336, 72, 9, 1, 1, 9495, 397440, 734160, 79632, 4620, 480, 90, 10, 1, 1, 35695, 3304620, 8337120, 1105104, 39732, 3300, 660, 110, 11, 1, 1, 140151, 35023120, 133212420, 16571808, 1400784, 20592, 4950, 880, 132, 12, 1, 1, 568503, 322852816, 1769490580, 176344740, 16253952, 130416, 33462, 7150, 1144, 156, 13, 1

Offset: 1

Jianing Song, Nov 18 2024

The number of monomorphisms (i.e., injective homomorphisms) S_k -> S_n is thus |Aut(S_k)|*T(n,k). Note that |Aut(S_k)| = 1 for k = 2, 1440 for k = 6 and k! otherwise.
T(n,k) is related to the number of homomorphisms S_k -> S_n:
     k     | trivial kernel | kernel S_k (k>=2) | kernel A_k (k>=3) | kernel V (k=4) |       total number
-----------+----------------+-------------------+-------------------+----------------+-------------------------
     1     |        1       |         -         |         -         |        -       |            1
-----------+----------------+-------------------+-------------------+----------------+-------------------------
     2     |     b(n)-1     |         1         |         -         |        -       |           b(n)
-----------+----------------+-------------------+-------------------+----------------+-------------------------
     4     |    24*T(n,4)   |         1         |       b(n)-1      |    6*T(n,3)    | 24*T(n,4)+6*T(n,3)+b(n)
-----------+----------------+-------------------+-------------------+----------------+-------------------------
     6     |   1440*T(n,6)  |         1         |       b(n)-1      |         -      |     1440*T(n,6)+b(n)
-----------+----------------+-------------------+-------------------+----------------+-------------------------
 3, 5, >=7 |    k!*T(n,k)   |         1         |       b(n)-1      |         -      |      k!*T(n,k)+b(n)
Here A_n is the n-th alternating group, V = {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} is the Klein-four group in S_4, b = A000085, and T(n,k) = 0 for k > n.
In particular, the number of homomorphisms S_n -> S_n is 1 for n = 1, 2 for n = 2, 58 for n = 4, 1440 + b(6) = 1516 for n = 6, and n! + b(n) otherwise.

			Table reads
  1
  1, 1
  1, 3, 1
  1, 9, 4, 1
  1, 25, 20, 5, 1
  1, 75, 160, 60, 12, 1
  1, 231, 910, 560, 84, 7, 1
  1, 763, 5936, 5740, 560, 56, 8, 1
  1, 2619, 53424, 58716, 3276, 336, 72, 9, 1
  1, 9495, 397440, 734160, 79632, 4620, 480, 90, 10, 1

Mathematics Stack Exchange, Subgroups in GAP

Cf. A000085, A001189, A378279, A378280, A378281, A281097.

A378163 := function(n,k)
local S;
S := SymmetricGroup(n);
return Sum(IsomorphicSubgroups(S,SymmetricGroup(k)),x->Index(S,Normalizer(S,Image(x))));
end; # program given in the Math Stack Exchange link

A378163_row_n := function(n)
local L, C, G, N, k;
N := ListWithIdenticalEntries( n, 0 );
L := ConjugacyClassesSubgroups( SymmetricGroup(n) );
for C in L do
G := Representative(C);
for k in [1..n] do
if not IsomorphismGroups( G, SymmetricGroup(k) ) = fail then
N[k] := N[k]+Size(C);
fi;
od;
od;
return N;
end;

T(n,2) = A001189(n).

A059838 Number of permutations in the symmetric group S_n that have even order.

Original entry on oeis.org

0, 0, 1, 3, 15, 75, 495, 3465, 29295, 263655, 2735775, 30093525, 370945575, 4822292475, 68916822975, 1033752344625, 16813959537375, 285837312135375, 5214921734397375, 99083512953550125, 2004231846526284375, 42088868777051971875, 934957186489800849375

Offset: 0

Avi Peretz (njk(AT)netvision.net.il), Feb 25 2001

From Bob Beals: Let P[n] = probability that a random permutation in S_n has odd order. Then P[n] = sum_k P[random perm in S_n has odd order | n is in a cycle of length k] * P[n is in a cycle of length k]. Now P[n is in a cycle of length k] = 1/n; P[random perm in S_n has odd order | k is even] = 0; P[random perm in S_n has odd order | k is odd] = P[ random perm in S_{n-k} has odd order]. So P[n] = (1/n) * sum_{k odd} P[n-k] = (1/n) P[n-1] + (1/n) sum_{k odd and >=3} P[n-k] = (1/n)*P[n-1] + ((n-2)/n)*P[n-2] and P[1] = 1, P[2] = 1/2. The solution is: P[n] = (1 - 1/2) (1 - 1/4) ... (1-1/(2*[n/2])).

			A permutation in S_4 has even order iff it is a transposition, a product of two disjoint transpositions or a 4 cycle so a(4) = C(4,2)+ C(4,2)/2 + 3! = 15.

T. D. Noe, Table of n, a(n) for n=0..100

Cf. A001189, A000246.

List([1..9],n->Length(Filtered(SymmetricGroup(n),x->(Order(x) mod 2)=0)));

s := series((1-sqrt(1-x^2))/(1-x), x, 21): for i from 0 to 20 do printf(`%d,`,i!*coeff(s,x,i)) od:

a[n_] := a[n] = n! - ((n-1)! - a[n-1]) * (n+Mod[n, 2]-1); a[0] = 0; Table[a[n], {n, 0, 20}](* Jean-François Alcover, Nov 21 2011, after Pari *)
With[{nn=20},CoefficientList[Series[(1-Sqrt[1-x^2])/(1-x),{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Aug 05 2015 *)

a(n)=if(n<1,0,n!-((n-1)!-a(n-1))*(n+n%2-1))

E.g.f.: (1-sqrt(1-x^2))/(1-x).
a(2n) = (2n-1)! + (2n-1)a(2n-1), a(2n+1) = (2n+1)a(2n).
a(n) = n! - A000246(n). - Victor S. Miller

Additional comments and more terms from Victor S. Miller, Feb 25 2001

Further terms and e.g.f. from Vladeta Jovovic, Feb 28 2001

A061130 Number of degree-n even permutations of order dividing 6.

Original entry on oeis.org

1, 1, 1, 3, 12, 36, 126, 666, 6588, 44892, 237996, 2204676, 26370576, 219140208, 1720782792, 19941776856, 234038005776, 2243409386256, 23225205107088, 295070141019312, 4303459657780416, 55200265166477376, 660776587455193056

Offset: 0

Vladeta Jovovic, Apr 14 2001

Alois P. Heinz, Table of n, a(n) for n = 0..522
Lev Glebsky, Melany Licón, Luis Manuel Rivera, On the number of even roots of permutations, arXiv:1907.00548 [math.CO], 2019.

Cf. A000085, A001470, A001472, A052501, A053496 - A053505, A001189, A001471, A001473, A061121 - A061128, A000704, A061129 - A061132, A048099, A051695, A061133 - A061135.

E.g.f.: 1/2*exp(x + 1/2*x^2 + 1/3*x^3 + 1/6*x^6) + 1/2*exp(x - 1/2*x^2 + 1/3*x^3 - 1/6*x^6).

A214003 Number of degree-n permutations of prime order.

Original entry on oeis.org

0, 1, 5, 17, 69, 299, 1805, 9099, 37331, 205559, 4853529, 49841615, 789513659, 9021065871, 70737031469, 420565124399, 22959075244095, 385032305178719, 10010973102879761, 152163983393187399, 1498273284120348539, 15639918041915598815, 1296204202723400597109

Offset: 1

Stephen A. Silver, Feb 15 2013

nonn

			The symmetric group S_5 has 25 elements of order 2, 20 elements of order 3, and 24 elements of order 5. All other elements are of nonprime order (1, 4, or 6), so a(5) = 25 + 20 + 24 = 69.

Stephen A. Silver, Table of n, a(n) for n = 1..451

Cf. A001189, A001471, A057731, A059593, A153760, A153761, A186202.

b:= proc(n,p) option remember;
      `if`(n add(b(n, ithprime(i)), i=1..numtheory[pi](n)):
seq(a(n), n=1..30);  # Alois P. Heinz, Feb 16 2013
# second Maple program:
b:= proc(n, g) option remember; `if`(n=0, `if`(isprime(g), 1, 0),
      add(b(n-j, ilcm(j, g))*(n-1)!/(n-j)!, j=1..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..23);  # Alois P. Heinz, Jan 19 2023

f[list_] :=Total[list]!/Apply[Times, list]/Apply[Times, Map[Length, Split[list]]!]; Table[Total[Map[f, Select[Partitions[n],PrimeQ[Apply[LCM, #]] &]]], {n, 1,23}] (* Geoffrey Critzer, Nov 08 2015 *)

a(n) = Sum_{p prime} A057731(n,p).

E.g.f.: exp(x)*Sum_{p in Primes} exp(x^p/p)-1. - Geoffrey Critzer, Nov 08 2015

A061134 Number of degree-n even permutations of order exactly 8.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 226800, 2494800, 29937600, 259459200, 1816214400, 10897286400, 301491590400, 4419628012800, 51209462304000, 482551041772800, 6979977625420800, 92611036249804800, 2078225819199129600

Offset: 1

Vladeta Jovovic, Apr 14 2001

Cf. A000085, A001470, A001472, A052501, A053496 - A053505, A001189, A001471, A001473, A061121 - A061128, A000704, A061129 - A061132, A048099, A051695, A061133 - A061135.

E.g.f.: - 1/2*exp(x + 1/2*x^2 + 1/4*x^4) - 1/2*exp(x - 1/2*x^2 - 1/4*x^4) + 1/2*exp(x + 1/2*x^2 + 1/4*x^4 + 1/8*x^8) + 1/2*exp(x - 1/2*x^2 - 1/4*x^4 - 1/8*x^8).

A061137 Number of degree-n odd permutations of order dividing 6.

Original entry on oeis.org

0, 0, 1, 3, 6, 30, 270, 1386, 6048, 46656, 387180, 2469060, 17204616, 158065128, 1903506696, 18887563800, 163657221120, 2095170230016, 30792968596368, 346564643468976, 3905503235814240, 58609511127871200, 866032039742528736

Offset: 0

Vladeta Jovovic, Apr 14 2001

Robert Israel, Table of n, a(n) for n = 0..522
Lev Glebsky, Melany Licón, Luis Manuel Rivera, On the number of even roots of permutations, arXiv:1907.00548 [math.CO], 2019.
Robert Israel, Recurrence for this sequence

Cf. A000085, A001470, A001472, A052501, A053496-A053505, A001189, A001471, A001473, A061121-A061128, A000704, A061129-A061132, A048099, A051695, A061133-A061135, A001465, A061136-A061140.

m:=30; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( Exp(x + x^3/3)*Sinh(x^2/2 + x^6/6) )); [0,0] cat [Factorial(n+1)*b[n]: n in [1..m-2]]; // G. C. Greubel, Jul 02 2019

Egf:= exp(x + x^3/3)*sinh(x^2/2 + x^6/6):
S:= series(Egf,x,31):
seq(coeff(S,x,j)*j!,j=0..30); # Robert Israel, Jul 13 2018

With[{m=30}, CoefficientList[Series[Exp[x + x^3/3]*Sinh[x^2/2 + x^6/6], {x, 0, m}], x]*Range[0,m]!] (* Vincenzo Librandi, Jul 02 2019 *)

my(x='x+O('x^30)); concat([0,0], Vec(serlaplace( exp(x + x^3/3)*sinh(x^2/2 + x^6/6) ))) \\ G. C. Greubel, Jul 02 2019

m = 30; T = taylor(exp(x + x^3/3)*sinh(x^2/2 + x^6/6), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # G. C. Greubel, Jul 02 2019

E.g.f.: exp(x + x^3/3)*sinh(x^2/2 + x^6/6).

Linear recurrence of order 12 whose coefficients are polynomials in n of degree up to 15: see link. - Robert Israel, Jul 13 2018

A051684 Auxiliary sequence for calculation of number of even permutations of degree n and order exactly 2.

Original entry on oeis.org

0, -1, -3, -3, 5, 15, -21, -133, 27, 1215, 935, -12441, -23673, 138047, 469455, -1601265, -9112561, 18108927, 182135007, -161934625, -3804634785, -404007681, 83297957567

Offset: 1

Vladeta Jovovic

sign

V. Jovovic, Some combinatorial characteristics of symmetric and alternating groups (in Russian), Belgrade, 1980, unpublished.

Cf. A001189, A051685.

a(n) = c(n, 2), where c(n, d)=Sum_{k=1..n} (-1)^(k+1)*(n-1)!/(n-k)! *Sum_{l:lcm{k, l}=d} c(n-k, l), c(0, 1)=1.
a(n)=2*A048099(n)-A001189(n)=A048099(n)-A001465(n) a(n)=(-1)^n*A001464(n)-1 a(n)=a(n-1)-(n-1)*(a(n-2)+1) E.g.f.: -e^x+e^(x-(1/2)*x^2) - Matthew J. White (mattjameswhite(AT)hotmail.com), Mar 02 2006
a(n) = Sum((-1)^j*n!/(2^j*j!*(n-2*j)!),j=1..floor(n/2)). - Vladeta Jovovic, Mar 06 2006

A051685 Auxiliary sequence for calculation of number of even permutations of degree n and order exactly 4.

Original entry on oeis.org

0, 0, 0, -6, -30, 0, 420, 2100, 6804, -20160, -376200, -2102760, -6606600, 53237184, 965306160, 5941244400, 12774059760, -305998041600, -5264368533216, -33983490935520, -16008359119200, 3139364813249280, 52132631033313600, 341037535726730304, -715693892444414400

Offset: 1

Vladeta Jovovic

V. Jovovic, Some combinatorial characteristics of symmetric and alternating groups (in Russian), Belgrade, 1980, unpublished.

Cf. A001189, A001473, A051684.

a(n) = c(n, 4), where c(n, d)=Sum_{k=1..n} (-1)^(k+1)*(n-1)!/(n-k)! *Sum_{l:lcm{k, l}=d} c(n-k, l), c(0, 1)=1.

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 05 2003

A088042 Number of permutations in the symmetric group S_n such that the size of their conjugacy class is odd.

Original entry on oeis.org

1, 2, 4, 4, 16, 76, 232, 106, 946, 5716, 27776, 63856, 272416, 2390480, 10349536, 2027026, 34459426, 344594404, 2618916472, 10475679736, 54997260256, 568305978472, 3132225435824, 1807129471456, 12047128545376, 175289251587776, 1326384554695552

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 02 2003

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..500

Cf. A088994, A060632.

Cf. A000085, A001189.

a:= n-> n!*add((binomial(n-(n mod 2), 2*k) mod 2)/((n-2*k)!*k!*2^k),
        k=0..floor(n/2)):
seq(a(n), n=1..30);  # Alois P. Heinz, May 01 2013

a[n_] := n!*Sum[Mod[Binomial[n-Mod[n, 2], 2*k], 2]/((n-2*k)!*k!*2^k), {k, 0, Floor[n/2]}]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 17 2014, after Alois P. Heinz *)

a(n) = Sum_{k=0..floor(n/2)} n!/(n-2*k)!/k!/2^k*(C(n-(n mod 2), 2*k) mod 2). - Vladeta Jovovic, Nov 06 2003

More terms from Vladeta Jovovic, Nov 03 2003

A143911 Triangle read by rows: T(n,k) = number of forests on n labeled nodes, where k is the maximum of the number of edges per tree (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 9, 12, 16, 1, 25, 60, 80, 125, 1, 75, 330, 480, 750, 1296, 1, 231, 1680, 3920, 5250, 9072, 16807, 1, 763, 9408, 33600, 49000, 72576, 134456, 262144, 1, 2619, 56952, 254016, 598500, 762048, 1210104, 2359296, 4782969, 1, 9495, 348120

Offset: 1

Alois P. Heinz, Sep 04 2008

			T(4,1) = 9, because 9 forests on 4 labeled nodes have 1 as the maximum of the number of edges per tree:
  .1-2. .1.2. .1.2. .1.2. .1.2. .1.2. .1-2. .1.2. .1.2.
  ..... ...|. ..... .|... ..\.. ../.. ..... .|.|. ..X..
  .4.3. .4.3. .4-3. .4.3. .4.3. .4.3. .4-3. .4.3. .4.3.
Triangle begins:
  1;
  1,  1;
  1,  3,   3;
  1,  9,  12,  16;
  1, 25,  60,  80, 125;
  1, 75, 330, 480, 750, 1296;

Alois P. Heinz, Rows n = 1..141, flattened

Columns k=0-1 give: A000012, A001189.
Row sums give A001858.
Rightmost diagonal gives A000272.
Cf. A138464.

A:= (n,k)-> coeff(series(exp(add(j^(j-2) *x^j/j!, j=1..k)), x, n+1), x,n)*n!: T:= (n,k)-> A(n,k+1)-A(n,k): seq(seq(T(n,k), k=0..n-1), n=1..11);

A[n_, k_] := SeriesCoefficient[Exp[Sum[j^(j-2)*x^j/j!, {j, 1, k}]], {x, 0, n}]*n!; T[n_, k_] := A[n, k+1] - A[n, k];
Table[T[n, k], {n, 1, 11}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, May 31 2016, translated from Maple *)

See program.

cp's OEIS Frontend

A378163 Triangle read by rows: T(n,k) is the number of subgroups of S_n isomorphic to S_k, where S_n is the n-th symmetric group.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

GAP

Formula

A059838 Number of permutations in the symmetric group S_n that have even order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

Extensions

A061130 Number of degree-n even permutations of order dividing 6.

Views

Author

Keywords

Links

Crossrefs

Formula

A214003 Number of degree-n permutations of prime order.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A061134 Number of degree-n even permutations of order exactly 8.

Views

Author

Keywords

Crossrefs

Formula

A061137 Number of degree-n odd permutations of order dividing 6.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A051684 Auxiliary sequence for calculation of number of even permutations of degree n and order exactly 2.

Views

Author

Keywords

References

Crossrefs

Formula

A051685 Auxiliary sequence for calculation of number of even permutations of degree n and order exactly 4.

Views

Author

Keywords

References

Crossrefs

Formula

Extensions