A051625 -id:A051625 - cp's OEIS frontend

A009490 Number of distinct orders of permutations of n objects; number of nonisomorphic cyclic subgroups of symmetric group S_n.

1, 1, 2, 3, 4, 6, 6, 9, 11, 14, 16, 20, 23, 27, 31, 35, 43, 47, 55, 61, 70, 78, 88, 98, 111, 123, 136, 152, 168, 187, 204, 225, 248, 271, 296, 325, 356, 387, 418, 455, 495, 537, 581, 629, 678, 732, 787, 851, 918, 986, 1056, 1133, 1217, 1307, 1399, 1498, 1600, 1708, 1823

Offset: 0

David W. Wilson

Also number of different LCM's of partitions of n.

a(n) <= A023893(n), which counts the nonisomorphic Abelian subgroups of S_n. - M. F. Hasler, May 24 2013

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
L. Elliott, A. Levine, and J. D. Mitchell, Counting monogenic monoids and inverse monoids, arXiv:2303.12387 [math.GR], 2023.
Index entries for sequences related to lcm's

Cf. A051613 (first differences), A000792, A000793, A034891, A051625 (all cyclic subgroups), A256067.

b:= proc(n,i) option remember; local p;
      p:= `if`(i<1, 1, ithprime(i));
      `if`(n=0 or i<1, 1, b(n, i-1)+
      add(b(n-p^j, i-1), j=1..ilog[p](n)))
    end:
a:= n-> b(n, numtheory[pi](n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 15 2013

Table[ Length[ Union[ Apply[ LCM, Partitions[ n ], 1 ] ] ], {n, 30} ]
f[n_] := Length@ Union[LCM @@@ IntegerPartitions@ n]; Array[f, 60, 0]
(* Caution, the following is Extremely Slow and Resource Intensive *) CoefficientList[ Series[ Expand[ Product[1 + Sum[x^(Prime@ i^k), {k, 4}], {i, 10}]/(1 - x)], {x, 0, 30}], x]
b[n_, i_] := b[n, i] = Module[{p}, p = If[i<1, 1, Prime[i]]; If[n == 0 || i<1, 1, b[n, i-1]+Sum[b[n-p^j, i-1], {j, 1, Log[p, n]}]]]; a[n_] := b[n, PrimePi[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 03 2014, after Alois P. Heinz *)

/* compute David W. Wilson's g.f., needs <1 sec for 1000 terms */
N=1000;  x='x+O('x^N); /* N terms */
gf=1; /* generating function */
{ forprime(p=2,N,
    sm = 1;  pp=p;  /* sum;  prime power */
    while ( ppJoerg Arndt, Jan 19 2011 */

a(n) = Sum_{k=0..n} b(k), where b(k) is the number of partitions of k into distinct prime power parts (1 excluded) (A051613). - Vladeta Jovovic

G.f.: (Product_{p prime} (1 + Sum_{k >= 1} x^(p^k))) / (1-x). - David W. Wilson, Apr 19 2000

A051636 Number of "labeled" cyclic subgroups of alternating group A_n.

Original entry on oeis.org

1, 1, 2, 8, 32, 167, 947, 6974, 53426, 454682, 4303532, 50366912, 553031624, 6760260236, 90333982832, 1369522152392, 20986020606632, 350528387240264, 5751957395258096, 111685506968916032, 2139383543480892032, 41770889787378732752, 869742098042083451264

Offset: 1

Vladeta Jovovic

Alois P. Heinz, Table of n, a(n) for n = 1..140
L. Naughton and G. Pfeiffer, Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group, J. Int. Seq. 16 (2013) #13.5.8.

Row sums of A303728.

Cf. A000010, A051625.

b:= proc(n, i, m, t) option remember; `if`(n=0, (1+(-1)^t)/numtheory
      [phi](m), add(1/j!/i^j*b(n-i*j, i-1, ilcm(m, `if`(j=0, 1, i)),
       irem(t+j*irem(i+1, 2), 2)), j=`if`(i=1, n, 0..n/i)))
    end:
a:= n-> n!*b(n$2, 1, 0)/2:
seq(a(n), n=1..25);  # Alois P. Heinz, Jul 03 2018

f[list_] :=Total[list]!/(Apply[Times, list]*Apply[Times, Map[Length, Split[list]]!])/EulerPhi[Apply[LCM, list]]; Table[Total[Map[f,
   Select[IntegerPartitions[n],EvenQ[Length[Select[#, EvenQ[#] &]]] &]]], {n, 1, 21}] (* Geoffrey Critzer, Oct 03 2015 *)
b[n_, i_, m_, t_] := b[n, i, m, t] = If[n == 0, (1 + (-1)^t)/
     EulerPhi[m], If[i == 0, 0, Sum[1/j!/i^j*b[n - i*j, i - 1, LCM[m,
     If[j == 0, 1, i]], Mod[t+j*Mod[i+1, 2], 2]], {j, Range[0, n/i]}]]];
a[n_] := n! b[n, n, 1, 0]/2;
Array[a, 25] (* Jean-François Alcover, Jun 04 2021, after Alois P. Heinz *)

\\ permcount is number of permutations of given type.
permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
a(n)={my(s=0); forpart(p=n, if(sum(i=1, #p, p[i]-1)%2==0, s+=permcount(p) / eulerphi(lcm(Vec(p))))); s} \\ Andrew Howroyd, Jul 03 2018

a(n) = 1/2*Sum_{pi} (1+(-1)^(k_2+k_4+...)) * n!/(k_1!*1^k_1*k_2!*2^k_2*...*k_n!*n^k_n*phi(lcm{i:k_i != 0})), where pi runs through all partitions k_1+2*k_2+...+n*k_n=n and phi is Euler's function.

A074881 Triangle T(n,k) giving number of labeled cyclic subgroups of order k in symmetric group S_n, n >= 1, 1 <= k <= g(n), where g(n) = A000793(n) is Landau's function.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 9, 4, 3, 1, 25, 10, 15, 6, 10, 1, 75, 40, 90, 36, 120, 1, 231, 175, 420, 126, 735, 120, 126, 105, 1, 763, 616, 2730, 336, 5320, 960, 1260, 1008, 840, 336, 1, 2619, 2884, 15498, 756, 41580, 4320, 11340, 6720, 6804, 7560, 4320, 3024, 2268

Offset: 1

Vladeta Jovovic, Sep 30 2002

A057731 contains zeros. This sequence contains only positive values of A057731(n,k)/A000010(k). - Alois P. Heinz, Feb 16 2013

			Triangle begins:
  1;
  1,   1;
  1,   3,   1;
  1,   9,   4,   3;
  1,  25,  10,  15,   6,  10;
  1,  75,  40,  90,  36, 120;
  1, 231, 175, 420, 126, 735, 120, 126, 105;
  ...

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

Row sums give A051625.

Cf. A000010, A181949.

nmax = 10;
T[n_, k_] := n! SeriesCoefficient[O[x]^(n+1) + Sum[MoebiusMu[k/i]*Exp[ Sum[x^j/j, {j, Divisors[i]}]], {i, Divisors[k]}], {x, 0, n}]/ EulerPhi[k];
Table[DeleteCases[Table[T[n, k], {k, 1, 2 nmax}], 0], {n, 1, nmax}] // Flatten (* Jean-François Alcover, Sep 16 2019, after Andrew Howroyd *)

T(n,k)={n!*polcoeff(sumdiv(k, i, moebius(k/i)*exp(sumdiv(i, j, x^j/j) + O(x*x^n))), n)/eulerphi(k)} \\ Andrew Howroyd, Jul 02 2018

T(n,k) = A057731(n,k)/A000010(k).

A063182 Number of cyclic subgroups of the group S_n X S_n (where S_n is the symmetric group of degree n).

Original entry on oeis.org

1, 4, 26, 314, 5222, 168632, 5736908, 291993032, 18599068328, 1547379999392, 136254185631632, 18749419634845088, 2367416741670079712, 387737484226037810048, 78779133220155242489792, 17651532033334188604514432, 3945247307615376458903485568

Offset: 1

Vladeta Jovovic, Jul 10 2001

nonn

Cf. A051625, A060648, (unlabeled case) A063183.

a(9)-a(17) from Stephen A. Silver, Feb 22 2013

A074260 Number of labeled cyclic subgroups of S_n having the maximum possible order.

Original entry on oeis.org

1, 1, 1, 1, 3, 10, 120, 105, 336, 2268, 15120, 332640, 498960, 6486480, 43243200, 259459200, 3113510400, 35286451200, 1270312243200, 3016991577600, 60339831552000, 1267136462592000, 37169336236032000, 160292762517888000

Offset: 0

Vladeta Jovovic, Sep 20 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..100

Cf. A051625, A074064.

a(n) = A074859(n)/A000010(A000793(n)).

A181949 Weighted sum of all cyclic subgroups of the Symmetric Group.

Original entry on oeis.org

1, 3, 10, 43, 231, 1531, 11068, 89895, 820543, 8484871, 95647476, 1186289083, 15648402355, 221728356123, 3354790995676, 53999879550991, 936289020367263, 17163114699673615, 328827078340587148, 6630244432204704771, 139769193881466850051, 3092293682224076627683

Offset: 1

Olivier Gérard, Apr 03 2012

Sum of the orders of all cyclic subgroups of the Sym_n.
The identity permutation is counted for each subgroup, i.e. A051625(n) times.
Each permutation is counted several times according to its conjugacy class.

			a(4) = 1*1 + 2*3 + 2*6 + 3*4 + 4*3 = 1+6+12+12+12 = 43.

Cf. A000793, A051625, A074881.

a(n) = Sum_{k=1..A000793(n)} k*A074881(n, k). - Andrew Howroyd, Jul 02 2018

a(9)-a(22) from Andrew Howroyd, Jul 02 2018

A218958 Total number of maximal cyclic subgroups of the symmetric group, counting conjugates as distinct.

Original entry on oeis.org

1, 1, 1, 4, 13, 31, 246, 1296, 10774, 83238, 788820, 6835170, 81364944, 848378532, 11423650616, 156289508025, 2380629720720, 33284133330760, 605934954285120, 9708364832948820, 190330953679235040, 3715069138923234960, 77101583995105472880, 1506549946554254503440

Offset: 0

Liam Naughton, Nov 23 2012

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Andrew Howroyd, PARI program for this sequence and A218963
Liam Naughton and Goetz Pfeiffer, Integer sequences realized by the subgroup pattern of the symmetric group, arXiv:1211.1911 [math.GR], 2012-2013.
Liam Naughton, CountingSubgroups.g
Liam Naughton and Goetz Pfeiffer, Tomlib, The GAP table of marks library

Cf. A051625, A218932, A218949, A218963.

\\ See links for program script file.
a(n)=MaximalCyclicSubgroupCount(n, v->1); \\ Andrew Howroyd, Jul 17 2018

Terms a(14) and beyond from Andrew Howroyd, Jul 03 2018

A062297 Number of distinct Abelian subgroups of the symmetric group S_n.

Original entry on oeis.org

1, 2, 5, 21, 87, 612, 3649, 35515, 289927, 377118, 36947363, 657510251, 7736272845

Offset: 1

Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 02 2001

L. Naughton and G. Pfeiffer, Integer sequences realized by the subgroup pattern of the symmetric group, arXiv:1211.1911 [math.GR], 2012-2013 and J. Int. Seq. 16 (2013) #13.5.8

Cf. A005432, A051625.

# GAP 4.4
LoadPackage("sonata");;
for n in [2,3,4,5,6,7,8,9,10] do
    p := SymmetricGroup(n) ;;
    o := Order(p);
    s := Subgroups(p);
    f := Filtered(s, g -> IsAbelian(g));
    a := Size(f);
    Print(a," ") ;
od; # R. J. Mathar, May 24 2013

a(9)-a(13) added by Liam Naughton

A074880 Number of labeled cyclic subgroups of S_n having order n.

Original entry on oeis.org

1, 1, 1, 3, 6, 120, 120, 1260, 6720, 128520, 362880, 20041560, 39916800, 1132971840, 11721790080, 163459296000, 1307674368000, 87307501881600, 355687428096000, 19137704006453760, 205947392645030400, 5118231678995635200, 51090942171709440000, 4769913628444053196800

Offset: 1

Vladeta Jovovic, Sep 30 2002

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A051625, A074260.

a(n)={n!*polcoeff(sumdiv(n, i, moebius(n/i)*exp(sumdiv(i, j, x^j/j) + O(x*x^n))), n)/eulerphi(n)} \\ Andrew Howroyd, Jul 02 2018

a(n) = A074351(n)/A000010(n).

Terms a(22) and beyond from Andrew Howroyd, Jul 02 2018

A226142 The smallest positive integer k such that the symmetric group S_n is a product of k cyclic groups.

Original entry on oeis.org

1, 1, 2, 3, 3, 4, 4

Offset: 1

W. Edwin Clark, May 27 2013

Since S_{n+1} is a product of a subgroup isomorphic to S_n and the cyclic group <(1,2,3,...,n+1)> we have a(n+1) <= a(n) + 1. On the other hand it is not clear that a(n) <= a(n+1) for all n. A lower bound is given by A226143(n) = ceiling(log(m)(n!)), m = A000793(n), a sequence that is not nondecreasing.
This sequence was suggested by a posting of L. Edson Jeffery on the seqfans mailing list on May 24, 2013.
Cardinality of the smallest subset(s) X of S_n such that every permutation in S_n can be expressed as a product of some elements in X. - Joerg Arndt, Dec 13 2015

			a(7) = 4 since a factorization of S_7 is given by C_1*C_2*C_3*C_4 where
C_1 = <(1,2,3,4)(5,6,7)>,
C_2 = <(1,4,6)(2,3,5,7)>,
C_3 = <(1,2,5,7)(3,4,6)>,
C_4 = <(1,3,5,6,7)(2,4)>,
and a brute force computation shows that S_7 is not a product of 3 or fewer cyclic subgroups.

Miklós Abért, Symmetric groups as products of Abelian subgroups, Bull. Lond. Math. Soc., Volume 34, Issue 04, July 2002, pp. 451-456.

Cf. A051625, A225788.

cp's OEIS Frontend

A009490 Number of distinct orders of permutations of n objects; number of nonisomorphic cyclic subgroups of symmetric group S_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A051636 Number of "labeled" cyclic subgroups of alternating group A_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A074881 Triangle T(n,k) giving number of labeled cyclic subgroups of order k in symmetric group S_n, n >= 1, 1 <= k <= g(n), where g(n) = A000793(n) is Landau's function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A063182 Number of cyclic subgroups of the group S_n X S_n (where S_n is the symmetric group of degree n).

Views

Author

Keywords

Crossrefs

Extensions

A074260 Number of labeled cyclic subgroups of S_n having the maximum possible order.

Views

Author

Keywords

Links

Crossrefs

Formula

A181949 Weighted sum of all cyclic subgroups of the Symmetric Group.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A218958 Total number of maximal cyclic subgroups of the symmetric group, counting conjugates as distinct.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A062297 Number of distinct Abelian subgroups of the symmetric group S_n.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Extensions

A074880 Number of labeled cyclic subgroups of S_n having order n.

Views

Author

Keywords