login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A009490 Number of distinct orders of permutations of n objects; number of nonisomorphic cyclic subgroups of symmetric group S_n. 16
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 (list; graph; refs; listen; history; text; internal format)
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

T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)

Index entries for sequences related to lcm's

FORMULA

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

G.f.: Prod(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.

Sequence in context: A300526 A006874 A034890 * A243930 A064778 A317491

Adjacent sequences:  A009487 A009488 A009489 * A009491 A009492 A009493

KEYWORD

nonn,nice,easy

AUTHOR

David W. Wilson

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 March 1 08:23 EST 2021. Contains 341732 sequences. (Running on oeis4.)