Displaying 1-9 of 9 results found.
page
1
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
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
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)):
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 */
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
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
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)):
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 *)
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
FORMULA
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]];
CROSSREFS
Last elements of rows give A000793.
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
COMMENTS
Two permutation groups are combinatorially equivalent iff they have the same cycle index. Order of partition is lcm of its parts.
LINKS
Index entries for linear recurrences with constant coefficients, signature (1,1,0,-1,-1,2,-1,-1,0,1,1,-1).
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 *)
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
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):
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 *)
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
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
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:
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) )
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
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
Last elements of rows give A074064.
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
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];
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
FORMULA
G.f.: -(x^10-x^3-1)*x^7/((x-1)*(x^2-1)*(x^5-1)*(x^10-1)).
Search completed in 0.045 seconds
|