[go: up one dir, main page]

login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Search: a256067 -id:a256067
     Sort: relevance | references | number | modified | created      Format: long | short | data
Number of distinct orders of permutations of n objects; number of nonisomorphic cyclic subgroups of symmetric group S_n.
+0
15
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,3
COMMENTS
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
LINKS
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.
FORMULA
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
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI) /* 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 ( pp<N, sm += x^pp; pp *= p; );
gf *= sm; /* update g.f. */
); }
gf/=(1-x); /* cumulative sums */
Vec(gf) /* show terms */ /* Joerg Arndt, Jan 19 2011 */
CROSSREFS
Cf. A051613 (first differences), A000792, A000793, A034891, A051625 (all cyclic subgroups), A256067.
KEYWORD
nonn,nice,easy
STATUS
approved
Triangle read by rows, A054525 * A168021.
+0
23
1, 1, 1, 2, 0, 1, 3, 1, 0, 1, 6, 0, 0, 0, 1, 7, 2, 1, 0, 0, 1, 14, 0, 0, 0, 0, 0, 1, 17, 3, 0, 1, 0, 0, 0, 1, 27, 0, 2, 0, 0, 0, 0, 0, 1, 34, 6, 0, 0, 1, 0, 0, 0, 0, 1, 55, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 63, 7, 3, 2, 0, 1, 0, 0, 0, 0, 0, 1, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
OFFSET
1,4
COMMENTS
Row sums = A000041 starting (1, 2, 3, 5, 7, 11, 15, ...).
T(n,k) is the number of partitions of n into parts with GCD = k. - Alois P. Heinz, Jun 06 2013
LINKS
FORMULA
Mobius transform of triangle A168021 = an infinite lower triangular matrix with aerated variants of A000837 in each column; where A000837 = the Mobius transform of the partition numbers, A000041.
EXAMPLE
First few rows of the triangle:
1;
1, 1;
2, 0, 1;
3, 1, 0, 1;
6, 0, 0, 0, 1;
7, 2, 1, 0, 0, 1;
14, 0, 0, 0, 0, 0, 1;
17, 3, 0, 1, 0, 0, 0, 1;
27, 0, 2, 0, 0, 0, 0, 0, 1;
34, 6, 0, 0, 1, 0, 0, 0, 0, 1;
55, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
63, 7, 3, 2, 0, 1, 0, 0, 0, 0, 0, 1;
100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
119, 14, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1;
167, 0, 6, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
209, 17, 0, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1;
296, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
...
MAPLE
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i=1, x,
b(n, i-1)+(p-> add(coeff(p, x, t)*x^igcd(t, i),
t=0..degree(p)))(add(b(n-i*j, i-1), j=1..n/i))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..17); # Alois P. Heinz, Mar 29 2015
MATHEMATICA
b[n_, i_] := b[n, i] = If[n==0, 1, If[i==1, x, b[n, i-1] + Function[{p}, Sum[Coefficient[p, x, t]*x^GCD[t, i], {t, 0, Exponent[p, x]}]][Sum[b[n - i*j, i-1], {j, 1, n/i}]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, n]]; Table[T[n], {n, 1, 17}] // Flatten (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)
CROSSREFS
Cf. A256067 (the same for LCM).
KEYWORD
nonn,tabl
AUTHOR
Gary W. Adamson, Nov 28 2009
EXTENSIONS
Corrected and extended by Alois P. Heinz, Jun 06 2013
STATUS
approved
Triangle T(n,k) in which the n-th row contains the increasing list of distinct orders of degree-n permutations; n>=0, 1<=k<=A009490(n).
+0
4
1, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 10, 12, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30
OFFSET
0,4
LINKS
FORMULA
Sum_{k>=0} T(n,k)*A256554(n,k) = A181844(n).
T(n,k) = k for n>0 and 1<=k<=n.
EXAMPLE
Triangle T(n,k) begins:
1;
1;
1, 2;
1, 2, 3;
1, 2, 3, 4;
1, 2, 3, 4, 5, 6;
1, 2, 3, 4, 5, 6;
1, 2, 3, 4, 5, 6, 7, 10, 12;
1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15;
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20;
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30;
MAPLE
b:= proc(n, i) option remember; `if`(n=0 or i=1, x,
b(n, i-1)+(p-> add(coeff(p, x, t)*x^ilcm(t, i),
t=1..degree(p)))(add(b(n-i*j, i-1), j=1..n/i)))
end:
T:= n->(p->seq((h->`if`(h=0, [][], i))(coeff(p, x, i))
, i=1..degree(p)))(b(n$2)):
seq(T(n), n=0..12);
MATHEMATICA
b[n_, i_] := b[n, i] = If[n == 0 || i == 1, x,
b[n, i - 1] + Function[p, Sum[Coefficient[p, x, t]*x^LCM[t, i],
{t, 1, Exponent[p, x]}]][Sum[b[n - i*j, i - 1], {j, 1, n/i}]]];
T[n_] := Function[p, Table[Function[h, If[h == 0, Nothing, i]][
Coefficient[p, x, i]], {i, 1, Exponent[p, x]}]][b[n, n]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jul 15 2021, after Alois P. Heinz *)
CROSSREFS
Row sums give A060179.
Row lengths give A009490.
Last elements of rows give A000793.
Main diagonal gives A000027.
KEYWORD
nonn,look,tabf
AUTHOR
Alois P. Heinz, Apr 01 2015
STATUS
approved
Number of combinatorially inequivalent cyclic subgroups of S_n of order 6. Number of partitions of n of order 6.
+0
4
1, 2, 3, 5, 7, 9, 12, 16, 19, 24, 29, 34, 40, 48, 54, 63, 72, 81, 91, 104, 114, 128, 142, 156, 171, 190, 205, 225, 245, 265, 286, 312, 333, 360, 387, 414, 442, 476, 504, 539, 574, 609, 645, 688, 724, 768, 812, 856, 901, 954, 999, 1053, 1107, 1161, 1216, 1280
OFFSET
5,2
COMMENTS
Two permutation groups are combinatorially equivalent iff they have the same cycle index. Order of partition is lcm of its parts.
LINKS
FORMULA
G.f.: x^5*(1+x-x^6)/((x-1)*(x^2-1)*(x^3-1)*(x^6-1)). More generally, g.f. for number of partitions of order d is Sum_{i divides d} mu(d/i)*1/Product_{j divides i} (1-x^j).
MATHEMATICA
LinearRecurrence[{1, 1, 0, -1, -1, 2, -1, -1, 0, 1, 1, -1}, {1, 2, 3, 5, 7, 9, 12, 16, 19, 24, 29, 34}, 60] (* Harvey P. Dale, May 23 2020 *)
CROSSREFS
Column k=6 of A256067, A256554.
KEYWORD
easy,nonn
AUTHOR
Vladeta Jovovic, Sep 28 2002
STATUS
approved
Sum over all partitions of n of the LCM of the parts.
+0
9
1, 1, 3, 6, 12, 23, 38, 73, 118, 198, 318, 530, 819, 1298, 1974, 2975, 4516, 6698, 9980, 14550, 21186, 30304, 43503, 62030, 87908, 123292, 172543, 239720, 331688, 458198, 629376, 860332, 1168172, 1583176, 2138438, 2876283, 3859770, 5159886, 6863702, 9112356
OFFSET
0,3
COMMENTS
Old name was: Row sums of A181842.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..188 (terms n=1..80 from Vincenzo Librandi)
FORMULA
a(n) = Sum_{k>=0} k * A256067(n,k) = Sum_{k>=0} A256553(n,k)*A256554(n,k). - Alois P. Heinz, Apr 02 2015
MAPLE
with(combstruct):
a181844 := proc(n) local k, L, l, R, part;
R := NULL; L := 0;
for k from 1 to n do
part := iterstructs(Partition(n), size=k):
while not finished(part) do
l := nextstruct(part);
L := L + ilcm(op(l));
od;
od;
L end:
# second Maple program:
b:= proc(n, i, r) option remember; `if`(n=0, r, `if`(i<1, 0,
b(n, i-1, r)+b(n-i, min(i, n-i), ilcm(i, r))))
end:
a:= n-> b(n$2, 1):
seq(a(n), n=0..42); # Alois P. Heinz, Mar 18 2019
MATHEMATICA
t[n_, k_] := LCM @@@ IntegerPartitions[n, {n - k + 1}] // Total; a[n_] := Sum[t[n, k], {k, 1, n}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Jul 26 2013 *)
CROSSREFS
Cf. A078392 (the same for GCD), A181843, A181842, A256067, A256553, A256554, A306956.
KEYWORD
nonn
AUTHOR
Peter Luschny, Dec 07 2010
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Mar 29 2015
New name from Alois P. Heinz, Mar 18 2019
STATUS
approved
Number of partitions of n of order n.
+0
37
1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 9, 1, 4, 5, 1, 1, 12, 1, 27, 7, 6, 1, 81, 1, 7, 1, 54, 1, 407, 1, 1, 11, 9, 13, 494, 1, 10, 13, 423, 1, 981, 1, 137, 115, 12, 1, 1309, 1, 59, 17, 193, 1, 240, 21, 1207, 19, 15, 1, 47274, 1, 16, 239, 1, 25, 3284, 1, 333, 23, 3731, 1, 42109, 1, 19
OFFSET
1,6
COMMENTS
Order of partition is lcm of its parts.
a(n) is the number of conjugacy classes of the symmetric group S_n such that a representative of the class has order n. Here order means the order of an element of a group. Note that a(n) = 1 if and only if n is a prime power. - W. Edwin Clark, Aug 05 2014
LINKS
Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 1..4000 (first 1025 terms from Joerg Arndt)
FORMULA
Coefficient of x^n in expansion of Sum_{i divides n} A008683(n/i)*1/Product_{j divides i} (1-x^j).
EXAMPLE
The a(15) = 5 partitions are (15), (5,3,3,3,1), (5,5,3,1,1), (5,3,3,1,1,1,1), (5,3,1,1,1,1,1,1,1). - Gus Wiseman, Aug 01 2018
MAPLE
A:= proc(n)
uses numtheory;
local S;
S:= add(mobius(n/i)*1/mul(1-x^j, j=divisors(i)), i=divisors(n));
coeff(series(S, x, n+1), x, n);
end proc:
seq(A(n), n=1..100); # Robert Israel, Aug 06 2014
MATHEMATICA
a[n_] := With[{s = Sum[MoebiusMu[n/i]*1/Product[1-x^j, {j, Divisors[i]}], {i, Divisors[n]}]}, SeriesCoefficient[s, {x, 0, n}]]; Array[a, 80}] (* Jean-François Alcover, Feb 29 2016 *)
Table[Length[Select[IntegerPartitions[n], LCM@@#==n&]], {n, 50}] (* Gus Wiseman, Aug 01 2018 *)
PROG
(PARI)
pr(k, x)={my(t=1); fordiv(k, d, t *= (1-x^d) ); return(t); }
a(n) =
{
my( x = 'x+O('x^(n+1)) );
polcoeff( Pol( sumdiv(n, i, moebius(n/i) / pr(i, x) ) ), n );
}
vector(66, n, a(n) )
\\ Joerg Arndt, Aug 06 2014
KEYWORD
easy,nonn
AUTHOR
Vladeta Jovovic, Sep 28 2002
STATUS
approved
Number T(n,k) of cycle types of degree-n permutations having the k-th smallest possible order; triangle T(n,k), n>=0, 1<=k<=A009490(n), read by rows.
+0
6
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 2, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 1, 1, 1, 4, 2, 4, 1, 5, 1, 1, 1, 1, 1, 1, 4, 3, 4, 1, 7, 1, 1, 1, 2, 2, 1, 1, 1, 1, 5, 3, 6, 2, 9, 1, 2, 1, 3, 4, 1, 1, 1, 1, 1, 1, 5, 3, 6, 2, 12, 1, 2, 1, 4, 1, 6, 2, 2, 1, 2, 1, 1, 1, 2
OFFSET
0,9
COMMENTS
Sum_{k>=0} A256553(n,k)*T(n,k) = A181844(n).
LINKS
EXAMPLE
Triangle T(n,k) begins:
1;
1;
1, 1;
1, 1, 1;
1, 2, 1, 1;
1, 2, 1, 1, 1, 1;
1, 3, 2, 2, 1, 2;
1, 3, 2, 2, 1, 3, 1, 1, 1;
1, 4, 2, 4, 1, 5, 1, 1, 1, 1, 1;
1, 4, 3, 4, 1, 7, 1, 1, 1, 2, 2, 1, 1, 1;
1, 5, 3, 6, 2, 9, 1, 2, 1, 3, 4, 1, 1, 1, 1, 1;
MAPLE
b:= proc(n, i) option remember; `if`(n=0 or i=1, x,
b(n, i-1)+(p-> add(coeff(p, x, t)*x^ilcm(t, i),
t=1..degree(p)))(add(b(n-i*j, i-1), j=1..n/i)))
end:
T:= n->(p->seq((h->`if`(h=0, [][], h))(coeff(p, x, i))
, i=1..degree(p)))(b(n$2)):
seq(T(n), n=0..12);
MATHEMATICA
b[n_, i_] := b[n, i] = If[n == 0 || i == 1, x, b[n, i - 1] + Function[p, Sum[Coefficient[p, x, t]*x^LCM[t, i], {t, 1, Exponent[p, x]}]][Sum[b[n - i*j, i - 1], {j, 1, n/i}]]]; T[n_] := Function[p, Table[Function[h, If[h == 0, {{}, {}}, h]][Coefficient[p, x, i]], {i, 1, Exponent[p, x]}]][b[n, n]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 23 2017, translated from Maple *)
CROSSREFS
Row sums give A000041.
Row lengths give A009490.
Columns k=1-9 give: A000012, A004526, A002264, A008642(n-4), A002266, A074752, A132270, A008643(n-8) for n>7, A008649(n-9) for n>8.
Last elements of rows give A074064.
Main diagonal gives A074761.
KEYWORD
nonn,look,tabf
AUTHOR
Alois P. Heinz, Apr 01 2015
STATUS
approved
Number of cycle types of degree-n permutations having the maximum possible order.
+0
7
1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 2, 4
OFFSET
0,7
LINKS
FORMULA
Coefficient of x^n in expansion of Sum_{i divides A000793(n)} mu(A000793(n)/i)*1/Product_{j divides i} (1-x^j).
EXAMPLE
For n = 22 we have 4 such cycle types: [1, 1, 1, 3, 4, 5, 7], [1, 2, 3, 4, 5, 7], [3, 3, 4, 5, 7], [4, 5, 6, 7].
MAPLE
A000793 := proc(n) option remember; local l, p, i ; l := 1: p := combinat[partition](n): for i from 1 to combinat[numbpart](n) do if ilcm( p[i][j] $ j=1..nops(p[i])) > l then l := ilcm( p[i][j] $ j=1..nops(p[i])) ; fi: od: RETURN(l) ; end proc:
taylInv := proc(i, n) local resul, j, idiv, k ; resul := 1 ; idiv := numtheory[divisors](i) ; for k from 1 to nops(idiv) do j := op(k, idiv) ; resul := resul*taylor(1/(1-x^j), x=0, n+1) ; resul := convert(taylor(resul, x=0, n+1), polynom) ; od ; coeftayl(resul, x=0, n) ; end proc:
A074064 := proc(n) local resul, a793, dvs, i, k ; resul := 0: a793 := A000793(n) ; dvs := numtheory[divisors](a793) ; for k from 1 to nops(dvs) do i := op(k, dvs) ; resul := resul+numtheory[mobius](a793/i)*taylInv(i, n) ; od : RETURN(resul) ; end proc: # R. J. Mathar, Mar 30 2007
MATHEMATICA
b[n_, i_] := b[n, i] = Module[{p}, p = If[i < 1, 1, Prime[i]]; If[n == 0 || i < 1, 1, Max[b[n, i-1], Table[p^j*b[n-p^j, i-1], {j, 1, Log[p, n] // Floor}]]]];
g[n_] := g[n] = b[n, If[n < 8, 3, PrimePi[Ceiling[1.328*Sqrt[n*Log[n] // Floor]]]]];
a[n_] := a[n] = SeriesCoefficient[Sum[MoebiusMu[g[n]/i]/Product[1-x^j, {j, Divisors[i]}], {i, Divisors[g[n]]}] + O[x]^(n+1), n];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 100}] (* Jean-François Alcover, Apr 25 2017, after Alois P. Heinz *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Vladeta Jovovic, Sep 15 2002
EXTENSIONS
More terms from R. J. Mathar, Mar 30 2007
More terms from Sean A. Irvine, Oct 04 2011
More terms from Alois P. Heinz, Mar 29 2015
STATUS
approved
Number of partitions of n of order 10.
+0
2
0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 6, 7, 9, 11, 13, 16, 18, 21, 25, 28, 33, 36, 41, 46, 51, 57, 62, 68, 76, 82, 91, 97, 106, 115, 124, 134, 143, 153, 166, 176, 190, 200, 214, 228, 242, 257, 271, 286, 305, 320, 340, 355, 375, 395, 415, 436, 456, 477, 503, 524
OFFSET
0,10
LINKS
FORMULA
G.f.: -(x^10-x^3-1)*x^7/((x-1)*(x^2-1)*(x^5-1)*(x^10-1)).
CROSSREFS
Column k=10 of A256067.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 31 2015
STATUS
approved

Search completed in 0.045 seconds