A218868 -id:A218868 - cp's OEIS frontend

A005225 Number of permutations of length n with equal cycles.

1, 2, 3, 10, 25, 176, 721, 6406, 42561, 436402, 3628801, 48073796, 479001601, 7116730336, 88966701825, 1474541093026, 20922789888001, 400160588853026, 6402373705728001, 133991603578884052, 2457732174030848001, 55735573291977790576, 1124000727777607680001

Offset: 1

N. J. A. Sloane

			For example, a(4)=10 since, of the 24 permutations of length 4, there are 6 permutations with consist of a single 4-cycle, 3 permutations that consist of two 2-cycles and 1 permutation with four 1-cycles.
Also, a(7)=721 since there are 720 permutations with a single cycle of length 7 and 1 permutation with seven 1-cycles.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D. P. Walsh, A differentiation-based characterization of primes, Abstracts Amer. Math. Soc., 25 (No. 2, 2002), p. 339, #975-11-237.

Alois P. Heinz, Table of n, a(n) for n = 1..450
R. K. Guy, Letter to N. J. A. Sloane, Jul 1988
D. P. Walsh, Primality test based on the generating function
D. P. Walsh, A differentiation-based characterization of primes
H. S. Wilf, Three problems in combinatorial asymptotics, J. Combin. Theory, A 35 (1983), 199-207.

Cf. A038041, A055225, A236696, A317329.
Column k=1 of A218868.
Column k=0 of A364967 (for n>=1).

a:= n-> n!*add((d/n)^d/d!, d=numtheory[divisors](n)):
seq(a(n), n=1..30);  # Alois P. Heinz, Nov 07 2012

Table[n! Sum[((n/d)!*d^(n/d))^(-1), {d, Divisors[n]}], {n, 21}] (* Jean-François Alcover, Apr 04 2011 *)

a(n):= n!*lsum((d!*(n/d)^d)^(-1),d,listify(divisors(n)));
makelist(a(n),n,1,40); /* Emanuele Munarini, Feb 03 2014 */

a(n) = n!*sum(((n/k)!*k^(n/k))^(-1)) where sum is over all divisors k of n. Exponential generating function [for a(1) through a(n)]= sum(exp(t^k/k)-1, k=1..n).

a(n) = (n-1)! + 1 iff n is a prime.

Additional comments from Dennis P. Walsh, Dec 08 2000

More terms from Vladeta Jovovic, Dec 01 2001

A242027 Number T(n,k) of endofunctions on [n] with cycles of k distinct lengths; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 4, 0, 24, 3, 0, 206, 50, 0, 2300, 825, 0, 31742, 14794, 120, 0, 522466, 294987, 6090, 0, 9996478, 6547946, 232792, 0, 218088504, 160994565, 8337420, 0, 5344652492, 4355845868, 299350440, 151200, 0, 145386399554, 128831993037, 11074483860, 18794160

Offset: 0

Alois P. Heinz, Aug 11 2014

			T(3,2) = 3: (1,3,2), (3,2,1), (2,1,3).
Triangle T(n,k) begins:
00 :  1;
01 :  0,          1;
02 :  0,          4;
03 :  0,         24,          3;
04 :  0,        206,         50;
05 :  0,       2300,        825;
06 :  0,      31742,      14794,       120;
07 :  0,     522466,     294987,      6090;
08 :  0,    9996478,    6547946,    232792;
09 :  0,  218088504,  160994565,   8337420;
10 :  0, 5344652492, 4355845868, 299350440, 151200;

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A241980 for n>0, A246283, A246284, A246285, A246286, A246287, A246288, A246289, A246290, A246291.
Row sums give A000312.
T(A000217(n),n) gives A246292.
Cf. A003056, A060281, A218868 (the same for permutations).

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, `if`(k=0, 1, 0),
      `if`(i<1 or k<1, 0, add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1, k-`if`(j=0, 0, 1)), j=0..n/i)))
    end:
T:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j$2, k), j=0..n):
seq(seq(T(n, k), k=0..floor((sqrt(1+8*n)-1)/2)), n=0..14);

multinomial[n_, k_] := n!/Times @@ (k!); b[n_, i_, k_] := b[n, i, k] = If[n == 0, If[k==0, 1, 0], If[i<1 || k<1, 0, Sum[(i-1)!^j*multinomial[n, Join[ {n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1, k-If[j==0, 0, 1]], {j, 0, n/i}]] ]; T[0, 0] = 1; T[n_, k_] := Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, j, k], {j, 0, n}]; Table[T[n, k], {n, 0, 14}, {k, 0, Floor[(Sqrt[1+8n]-1)/2]}] // Flatten (* Jean-François Alcover, Feb 18 2017, translated from Maple *)

A208437 Triangular array read by rows: T(n,k) is the number of set partitions of {1,2,...,n} that have exactly k distinct block sizes.

Original entry on oeis.org

1, 2, 2, 3, 5, 10, 2, 50, 27, 116, 60, 2, 560, 315, 142, 1730, 2268, 282, 6123, 14742, 1073, 30122, 72180, 12600, 2, 116908, 464640, 97020, 32034, 507277, 2676366, 997920, 2, 2492737, 16400098, 8751600, 136853, 15328119, 94209206, 81225144, 1527528, 56182092, 673282610, 614128515, 37837800

Offset: 1

Geoffrey Critzer, Feb 26 2012

Column 1 = A038041.
Column 2 = A088142.
Column 3 = A133118.
Row sums = A000110 (Bell numbers).
Row n has floor([sqrt(1+8n)-1]/2) terms (number of terms increases by one at each triangular number). - Franklin T. Adams-Watters, Feb 26 2012

			:    1;
:    2;
:    2,      3;
:    5,     10;
:    2,     50;
:   27,    116,     60;
:    2,    560,    315;
:  142,   1730,   2268;
:  282,   6123,  14742;
: 1073,  30122,  72180,   12600;

Alois P. Heinz, Rows n = 1..220, flattened
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 180.

Cf. A022915, A116608, A218868.

with(combinat):
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1)*`if`(j=0, 1, x), j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n$2)):
seq(T(n), n=1..16);  # Alois P. Heinz, Aug 21 2014

nn = 15; p = Product[1 + y (Exp[x^i/i!] - 1), {i, 1, nn}];f[list_] := Select[list, # > 0 &];
Map[f, Drop[ Range[0, nn]! CoefficientList[Series[p, {x, 0, nn}], {x, y}], 1]] // Flatten

E.g.f.: Product_{i>=1} 1 + y *(exp(x^i/i!)-1).

T(n*(n+1)/2,n) = A022915(n). - Alois P. Heinz, Apr 08 2016

A005772 Number of permutations of length n with 2 cycle lengths.

Original entry on oeis.org

3, 14, 95, 424, 3269, 21202, 178443, 1622798, 17064179, 177093256, 2293658861, 29296367476, 416567286225, 6250052633294, 103272943796399, 1717954871163982, 32068960264609523, 601640759502181648, 12257756112146028309, 257187849583000601516

Offset: 3

Simon Plouffe

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 3..200
H. S. Wilf, Three problems in combinatorial asymptotics, J. Combin. Theory, A 35 (1983), 199-207.

Column k=2 of A218868.

with(numtheory): with(combinat):
a:= n-> add(add(add((i-1)!^j*(d-1)!^((n-i*j)/d)*
        multinomial(n, i$j, d$((n-i*j)/d))/j!/((n-i*j)/d)!,
        d=select(x->xAlois P. Heinz, Feb 01 2014

multinomial[n_, k_List] := n!/Times @@ (k!); a[n_] := Sum[Sum[Sum[(i - 1)!^j*(d-1)!^((n-i*j)/d)*multinomial[n, Join[Array[i&, j], Array[d&, ((n - i*j)/d)]]]/j!/((n-i*j)/d)!, {d, Select[If[n == i*j, {}, Divisors[n - i*j]], #Jean-François Alcover, Nov 12 2015, after Alois P. Heinz *)

More terms from Vladeta Jovovic, Nov 02 2003

A317327 Number T(n,k) of permutations of [n] with exactly k distinct lengths of increasing runs; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 2, 4, 0, 7, 17, 0, 2, 118, 0, 82, 436, 202, 0, 2, 3294, 1744, 0, 1456, 18164, 20700, 0, 1515, 140659, 220706, 0, 50774, 1096994, 2317340, 163692, 0, 2, 10116767, 27136103, 2663928, 0, 3052874, 94670868, 328323746, 52954112, 0, 2, 1021089326, 4317753402, 888178070

Offset: 0

Alois P. Heinz, Jul 25 2018

			T(4,1) = 7: 1234, 1324, 1423, 2314, 2413, 3412, 4321.
Triangle T(n,k) begins:
  1;
  0,       1;
  0,       2;
  0,       2,        4;
  0,       7,       17;
  0,       2,      118;
  0,      82,      436,       202;
  0,       2,     3294,      1744;
  0,    1456,    18164,     20700;
  0,    1515,   140659,    220706;
  0,   50774,  1096994,   2317340,   163692;
  0,       2, 10116767,  27136103,  2663928;
  0, 3052874, 94670868, 328323746, 52954112;
  ...

Alois P. Heinz, Rows n = 0..60, flattened

Columns k=0-1 give: A000007, A317329.
Row sums give A000142.
Cf. A000217, A003056, A097591, A097592, A123125, A218868, A317273.

b:= proc(u, o, t, s) option remember;
      `if`(u+o=0, x^(nops(s union {t})-1),
       add(b(u-j, o+j-1, 1, s union {t}), j=1..u)+
       add(b(u+j-1, o-j, t+1, s), j=1..o))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2, {})):
seq(T(n), n=0..16);

b[u_, o_, t_, s_] := b[u, o, t, s] = If[u + o == 0, x^(Length[s ~Union~  {t}] - 1), Sum[b[u - j, o + j - 1, 1, s ~Union~ {t}], {j, 1, u}] + Sum[b[u + j - 1, o - j, t + 1, s], {j, 1, o}]];
T[n_] := With[{p = b[n, 0, 0, {}]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
T /@ Range[0, 16] // Flatten (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)

T(n*(n+1)/2,n) = A317273(n).

Sum_{k=0..floor((sqrt(1+8*n)-1)/2)} k * T(n,k) = A317328(n).

A246292 Number of permutations on [n*(n+1)/2] with cycles of n distinct lengths.

Original entry on oeis.org

1, 1, 3, 120, 151200, 10897286400, 70959641905152000, 60493719168990845337600000, 9226024969987629401488081551360000000, 329646772667218349211759153151614073700352000000000, 3498788402132461399351052923160966975192989707740695756800000000000

Offset: 0

Alois P. Heinz, Aug 21 2014

nonn

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

Cf. A000142, A000178, A000217, A022915, A218868, A242027, A317165.

a:= n-> binomial(n+1, 2)!/n!:
seq(a(n), n=0..12);

a(n) = C(n+1,2)! / n!.
a(n) = A218868(n*(n+1)/2,n) = A218868(A000217(n),n).
a(n) = A242027(n*(n+1)/2,n) = A242027(A000217(n),n).
a(n) = A022915(n) * A000178(n-1) for n>0.

A133119 Number of permutations of [n] with 3 cycle lengths.

Original entry on oeis.org

120, 1050, 12712, 141876, 1418400, 17061660, 212254548, 2735287698, 37354035628, 581350330470, 8895742806480, 151305163230480, 2659183039338192, 50112909523522476, 976443721325014300, 20413628375979803370, 434137453618439716068

Offset: 6

Vladeta Jovovic, Sep 18 2007

Alois P. Heinz, Table of n, a(n) for n = 6..200

Cf. A005225, A005772, A038041, A088142.

Column k=3 of A218868.

We obtain e.g.f. for number of permutations of [n] with m cycle lengths if we substitute x(i) with -Sum_{k>0} ((1-exp(x^k/k))^i in cycle index Z(S(m); x(1),x(2),..,x(m)) of symmetric group S(m) of degree m.

More terms from Max Alekseyev, Feb 08 2010

cp's OEIS Frontend

A005225 Number of permutations of length n with equal cycles.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

Extensions

A242027 Number T(n,k) of endofunctions on [n] with cycles of k distinct lengths; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A208437 Triangular array read by rows: T(n,k) is the number of set partitions of {1,2,...,n} that have exactly k distinct block sizes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A005772 Number of permutations of length n with 2 cycle lengths.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A317327 Number T(n,k) of permutations of [n] with exactly k distinct lengths of increasing runs; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246292 Number of permutations on [n*(n+1)/2] with cycles of n distinct lengths.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A133119 Number of permutations of [n] with 3 cycle lengths.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions