A057693 -id:A057693 - cp's OEIS frontend

A126074 Triangle read by rows: T(n,k) is the number of permutations of n elements that have the longest cycle length k.

1, 1, 1, 1, 3, 2, 1, 9, 8, 6, 1, 25, 40, 30, 24, 1, 75, 200, 180, 144, 120, 1, 231, 980, 1260, 1008, 840, 720, 1, 763, 5152, 8820, 8064, 6720, 5760, 5040, 1, 2619, 28448, 61236, 72576, 60480, 51840, 45360, 40320, 1, 9495, 162080, 461160, 653184, 604800, 518400, 453600, 403200, 362880

Offset: 1

Dan Dima, Mar 01 2007

Sum of the n-th row is the number of all permutations of n elements: Sum_{k=1..n, T(n,k)} = n! = A000142(n) We can extend T(n,k)=0, if k<=0 or k>n.
From Peter Luschny, Mar 07 2009: (Start)
Partition product of prod_{j=0..n-2}(k-n+j+2) and n! at k = -1, summed over parts with equal biggest part (see the Luschny link).
Underlying partition triangle is A102189.
Same partition product with length statistic is A008275.
Diagonal a(A000217(n)) = rising_factorial(1,n-1), A000142(n-1) (n > 0).
Row sum is A000142. (End)
Let k in {1,2,3,...} index the family of sequences A000012, A000085, A057693, A070945, A070946, A070947, ... respectively. Column k is the k-th sequence minus its immediate predecessor. For example, T(5,3)=A057693(5)-A000085(5). - Geoffrey Critzer, May 23 2009

			Triangle T(n,k) begins:
  1;
  1,   1;
  1,   3,    2;
  1,   9,    8,    6;
  1,  25,   40,   30,   24;
  1,  75,  200,  180,  144,  120;
  1, 231,  980, 1260, 1008,  840,  720;
  1, 763, 5152, 8820, 8064, 6720, 5760, 5040;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.
S. W. Golomb and P. Gaal, On the number of permutations of n objects with greatest cycle length k, Adv. in Appl. Math., 20(1), 1998, 98-107.
IBM Research, Ponder This, December 2006.
Peter Luschny, Counting with Partitions. [From _Peter Luschny_, Mar 07 2009]
Peter Luschny, Generalized Stirling_1 Triangles. [From _Peter Luschny_, Mar 07 2009]
D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.

Cf. A000142.
Cf. A071007, A080510, A028418.
Cf. A157386, A157385, A157384, A157383, A157400, A157391, A157392, A157393, A157394, A157395. - Peter Luschny, Mar 07 2009
T(2n,n) gives A052145 (for n>0). - Alois P. Heinz, Apr 21 2017

A:= proc(n,k) option remember; `if`(n<0, 0, `if`(n=0, 1,
       add(mul(n-i, i=1..j-1)*A(n-j,k), j=1..k)))
    end:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n,k), k=1..n), n=1..10);  # Alois P. Heinz, Feb 11 2013

Table[CoefficientList[ Series[(Exp[x^m/m] - 1) Exp[Sum[x^k/k, {k, 1, m - 1}]], {x, 0, 8}], x]*Table[n!, {n, 0, 8}], {m, 1, 8}] // Transpose // Grid (* Geoffrey Critzer, May 23 2009 *)

def A126074(n, k):
    f = factorial(n)
    P = Partitions(n, max_part=k, inner=[k])
    return sum(f // p.aut() for p in P)
for n in (1..9): print([A126074(n,k) for k in (1..n)]) # Peter Luschny, Apr 17 2016

T(n,1) = 1.
T(n,2) = n! * Sum_{k=1..[n/2]} 1/(k! * (2!)^k * (n-2*k)!).
T(n,k) = n!/k * (1-1/(n-k)-...-1/(k+1)-1/2k), if n/3 < k <= n/2.
T(n,k) = n!/k, if n/2 < k <= n.
T(n,n) = (n-1)! = A000142(n-1).
E.g.f. for k-th column: exp(-x^k*LerchPhi(x,1,k))*(exp(x^k/k)-1)/(1-x). - Vladeta Jovovic, Mar 03 2007
From Peter Luschny, Mar 07 2009: (Start)
T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n
T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,..,a_n such that
1*a_1+2*a_2+...+n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*..*a_n!),
f^a = (f_1/1!)^a_1*..*(f_n/n!)^a_n and f_n = product_{j=0..n-2}(j-n+1). (End)
Sum_{k=1..n} k * T(n,k) = A028418(n). - Alois P. Heinz, May 17 2016

A070945 Number of permutations on n letters that have only cycles of length 4 or less.

Original entry on oeis.org

1, 1, 2, 6, 24, 96, 456, 2472, 14736, 92304, 632736, 4661856, 36364032, 297668736, 2583425664, 23550535296, 224086162176, 2221083839232, 22976670905856, 246829966447104, 2745834333566976, 31605782067081216, 376290722808502272

Offset: 0

N. J. A. Sloane and Sharon Sela, May 18 2002

nonn

Dennis P. Walsh, The Number of Permutations with Only Small Cycles, preprint [From Geoffrey Critzer, May 24 2009]

Michael De Vlieger, Table of n, a(n) for n = 0..499
P. L. Krapivsky, J. M. Luck, Coverage fluctuations in theater models, arXiv:1902.04365 [cond-mat.stat-mech], 2019.
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013 and J. Int. Seq. 17 (2014) #14.1.1 .
R. Petuchovas, Asymptotic analysis of the cyclic structure of permutations, arXiv:1611.02934 [math.CO], p. 6, 2016.

Cf. A057693.

with (combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, m>=card))}, labeled]; end: A:=a(4):seq(count(A, size=n), n=0..22); # Zerinvary Lajos, Jun 11 2008
G := exp(x+(1/2)*x^2+(1/3)*x^3+(1/4)*x^4): seq(factorial(n)*coeftayl(G, x = 0, n), n = 0 .. 22); # Emeric Deutsch, Jun 21 2009

Table[Sum[Binomial[n, 4 i]*(4 i)!/(i!*4^i)* Sum[Binomial[n - 4 i, 3 j]*(3 j)!/(j!*3^j)* Sum[Binomial[n - 4 i - 3 j, 2 k]*(2 k)!/(k!*2^k), {k, 0, n}], {j, 0, n}], {i, 0, n}], {n, 0, 22}] (* Geoffrey Critzer, May 24 2009 *)
With[{nn = 23, k = 5}, CoefficientList[Exp[-Log[1 - x] + O[x]^k // Normal] + O[x]^nn, x] Range[0, nn - 1]!] (* Michael De Vlieger, Mar 29 2019, after Jean-François Alcover at A070947 *)

E.g.f.: exp(x + 1/2*x^2 + 1/3*x^3 + 1/4*x^4).

A070947 Number of permutations on n letters that have only cycles of length 6 or less.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 4320, 29520, 225360, 1890720, 17169120, 166112640, 1680462720, 18189031680, 209008512000, 2532028896000, 32143053484800, 425585741760000, 5865854258188800, 84489178710067200, 1266667808011315200, 19700712491727974400

Offset: 0

N. J. A. Sloane and Sharon Sela, May 18 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..514
P. L. Krapivsky, J. M. Luck, Coverage fluctuations in theater models, arXiv:1902.04365 [cond-mat.stat-mech], 2019.
R. Petuchovas, Asymptotic analysis of the cyclic structure of permutations, arXiv:1611.02934 [math.CO], p. 6, 2016.

Cf. A057693.

with(combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, m>=card))}, labeled]; end: A:=a(6):seq(count(A, size=n), n=0..21); # Zerinvary Lajos, Jun 11 2008
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)
      *binomial(n-1, j-1)*(j-1)!, j=1..min(n, 6)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 28 2017

terms = 22; CoefficientList[Exp[-Log[1-x] + O[x]^7 // Normal] + O[x]^terms, x]*Range[0, terms-1]! (* Jean-François Alcover, Dec 28 2017 *)

from sympy.core.cache import cacheit
from sympy import binomial, factorial as f
@cacheit
def a(n): return 1 if n==0 else sum(a(n-j)*binomial(n - 1, j - 1)*f(j - 1) for j in range(1, min(n, 6)+1))
print([a(n) for n in range(31)]) # Indranil Ghosh, Dec 29 2017, after Alois P. Heinz

E.g.f.: exp(x+1/2*x^2+1/3*x^3+1/4*x^4+1/5*x^5+1/6*x^6).

A070946 Number of permutations on n letters that have only cycles of length 5 or less.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 600, 3480, 22800, 164880, 1285920, 10516320, 92931840, 877374720, 8762014080, 91819440000, 1005716908800, 11584953158400, 139521689740800, 1748830512960000, 22750446292531200, 306931140411955200, 4296645083802470400, 62213458150660147200

Offset: 0

N. J. A. Sloane and Sharon Sela, May 18 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..532
P. L. Krapivsky, J. M. Luck, Coverage fluctuations in theater models, arXiv:1902.04365 [cond-mat.stat-mech], 2019.
Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
R. Petuchovas, Asymptotic analysis of the cyclic structure of permutations, arXiv:1611.02934 [math.CO], p. 6, 2016.

Cf. A057693.

with(combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, m>=card))}, labeled]; end: A:=a(5):seq(count(A, size=n), n=0..21); # Zerinvary Lajos, Jun 11 2008
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)
      *binomial(n-1, j-1)*(j-1)!, j=1..min(n, 5)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 25 2018

With[{nn=30},CoefficientList[Series[Exp[x+x^2/2+x^3/3+x^4/4+ x^5/5], {x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Mar 24 2016 *)

E.g.f.: exp(x+1/2*x^2+1/3*x^3+1/4*x^4+1/5*x^5).

a(n) = n!*Sum_{k=1..n} (1/k!)*Sum_{r=0..k} binomial(k,r)*Sum_{m=0..r} 2^(m-r)*binomial(r,m)*Sum_{j=0..m} binomial(m,j)*binomial(j,n-m-k-j-r)*3^(j-m)*4^(n-r-m-k-2*j)*5^(m+k+j+r-n) for n > 0. - Vladimir Kruchinin, Jan 26 2011

A334569 E.g.f.: exp(-(x + x^2/2 + x^3/3)).

Original entry on oeis.org

1, -1, 0, 0, 6, -6, -24, -120, 540, 1764, 2016, -68256, -147960, 700920, 11870496, 5245344, -330495984, -2602348560, 6794046720, 141179998464, 619736321376, -6025074044256, -66284988059520, -87481563442560, 4660723755205056, 34028147176271424, -98057302990861824

Offset: 0

Seiichi Manyama, May 06 2020

sign

Seiichi Manyama, Table of n, a(n) for n = 0..500

Column 3 of A334568.

Cf. A057693, A334562.

m = 25; Range[0, m]! * CoefficientList[Series[Exp[-(x + x^2/2 + x^3/3)], {x, 0, m}], x] (* Amiram Eldar, May 03 2021 *)

N=40; x='x+O('x^N); Vec(serlaplace(exp(-x-x^2/2-x^3/3)))

a(0) = 1 and a(n) = - (n-1)! * Sum_{k=1..min(3,n)} a(n-k)/(n-k)!.

D-finite with recurrence a(n) +a(n-1) +(n-1)*a(n-2) +(n-1)*(n-2)*a(n-3)=0. - R. J. Mathar, May 07 2020

A071007 Number of permutations in the symmetric group S_n such that the maximal cycle has length exactly 3.

Original entry on oeis.org

0, 0, 0, 2, 8, 40, 200, 980, 5152, 28448, 162080, 979000, 6179360, 40575392, 279199648, 1997406320, 14825619200, 114365751040, 912510870272, 7521873125408, 64045101880960, 561615674345600, 5067769601121920, 47023128008540992, 447820056115824128

Offset: 0

Sharon Sela (sharonsela(AT)hotmail.com), May 19 2002

nonn

E.g.f.: exp( x + (x^2)/2 + (x^3)/3 ) - exp( x + (x^2)/2 ).

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

Cf. A057693, A000085, A027617.

Column k=3 of A126074.

nn=20;Range[0,nn]!CoefficientList[Series[Exp[x+x^2/2+x^3/3]-Exp[x+x^2/2],{x,0,nn}],x]  (* Geoffrey Critzer, Jan 23 2013 *)

for(n=0,25,print1(polcoeff(serlaplace(exp(x+x^2/2+x^3/3)-exp(x+x^2/2)),n)","))

a(n) = A057693(n) - A000085(n).

More terms from Ralf Stephan, Apr 09 2003

A202364 Number of n-permutations with at least one cycle of length >=4.

Original entry on oeis.org

0, 0, 0, 0, 6, 54, 444, 3828, 34404, 331812, 3457224, 38902104, 472682088, 6185876904, 86896701072, 1305666612144, 20907918062064, 355572850545648, 6401460197543904, 121637573726005152, 2432837939316094944, 51090380436082401504, 1123995659389121919168

Offset: 0

Geoffrey Critzer, Jan 09 2013

nonn

a(n) = n! - A057693(n). - Vaclav Kotesovec, Oct 09 2013

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.

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

Cf. A000142, A033312, A066052, A028418.

b:= proc(n) option remember; `if`(n<4, [6, 54, 444, 3828][n+1],
      ((5*n+3+n^2)*b(n-1) -(n+3)*b(n-2) -(n+3)*(n+2)*b(n-3)
      -(n+3)*(n+2)*(n+1)^2*b(n-4))/n)
    end:
a:= n-> `if`(n<4, 0, b(n-4)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 09 2013

nn=25;Range[0,nn]!CoefficientList[Series[1/(1-x)-Exp[x+x^2/2+x^3/3],{x,0,nn}],x]
(* Second program: *)
b[n_] := b[n] = If[n<4, {6, 54, 444, 3828}[[n+1]], ((5*n+3+n^2)*b[n-1] - (n + 3)*b[n-2] - (n+3)*(n+2)*b[n-3] - (n+3)*(n+2)*(n+1)^2*b[n-4])/n]; a[n_] := If[n<4, 0, b[n-4]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 08 2017, after Alois P. Heinz *)

E.g.f.: 1/(1-x) - exp(x + x^2/2 + x^3/3).

A330858 Triangle read by rows: T(n,k) is the number of permutations in S_n for which all cycles have length <= k.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 1, 10, 18, 24, 1, 26, 66, 96, 120, 1, 76, 276, 456, 600, 720, 1, 232, 1212, 2472, 3480, 4320, 5040, 1, 764, 5916, 14736, 22800, 29520, 35280, 40320, 1, 2620, 31068, 92304, 164880, 225360, 277200, 322560, 362880, 1, 9496, 171576, 632736

Offset: 1

Peter Kagey, Apr 28 2020

			For n = 3 and k = 2, the T(3,2) = 4 permutations in S_3 where all cycle lengths are less than or equal to 2 are:
(1)(2)(3), (12)(3), (13)(2), and (1)(23).
Table begins:
n\k| 1    2     3     4      5      6      7      8      9
---+------------------------------------------------------
  1| 1
  2| 1    2
  3| 1    4     6
  4| 1   10    18    24
  5| 1   26    66    96    120
  6| 1   76   276   456    600    720
  7| 1  232  1212  2472   3480   4320   5040
  8| 1  764  5916 14736  22800  29520  35280  40320
  9| 1 2620 31068 92304 164880 225360 277200 322560 362880

Peter Kagey, Table of n, a(n) for n = 1..10011 (first 141 rows, flattened)
Steven Finch, Second best, Third worst, Fourth in line, arxiv:2202.07621 [math.CO], 2022.

Cf. A068424, A333726.
Columns 2-6: A000085, A057693, A070945, A070946, A070947.
T(n,floor(n/2)) gives A024168.
Cf. A126074.

T[n_, k_] := T[n, k] = If[n <= k, n!, n*T[n-1, k] - FactorialPower[n-1, k]* T[n-k-1, k]];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 28 2020 *)

T4(n, k)=if(k<1 || k>n, 0, n!/(n-k)!); \\ A068424
T(n,k) = if (n<=k, n!, n*T(n-1,k) - T4(n-1,k)*T(n-k-1,k));
tabl(nn) = for (n=1, nn, for (k=1, n, print1(T(n,k), ", ")); print); \\ Michel Marcus, May 09 2020

T(n,k) = n! if n <= k, otherwise T(n,k) = n*T(n-1,k) - A068424(n-1,k)*T(n-k-1,k).

T(n,k) = Sum_{j=1..k} A126074(n,j). - Alois P. Heinz, Jul 08 2022

A355293 Expansion of e.g.f. 1 / (1 - x - x^2/2 - x^3/3).

Original entry on oeis.org

1, 1, 3, 14, 82, 610, 5450, 56700, 674520, 9027480, 134236200, 2195701200, 39180094800, 757389032400, 15767305554000, 351689317980000, 8367381470448000, 211518767796336000, 5661504152255952000, 159954273475764768000, 4757034049019572320000, 148547713504322452320000, 4859583724723970642400000

Offset: 0

Ilya Gutkovskiy, Jun 27 2022

nonn

Cf. A007840, A057693, A080599, A189886, A355294.

nmax = 22; CoefficientList[Series[1/(1 - x - x^2/2 - x^3/3), {x, 0, nmax}], x] Range[0, nmax]!
a[0] = a[1] = 1; a[2] = 3; a[n_] := a[n] = n a[n - 1] + n (n - 1) a[n - 2]/2 + n (n - 1) (n - 2) a[n - 3]/3; Table[a[n], {n, 0, 22}]

a(n) = n * a(n-1) + n * (n-1) * a(n-2) / 2 + n * (n-1) * (n-2) * a(n-3) / 3.

A186526 Number T(n,k) of permutations on n elements with exactly k 3-cycles; triangle read by rows.

Original entry on oeis.org

1, 1, 2, 4, 2, 16, 8, 80, 40, 520, 160, 40, 3640, 1120, 280, 29120, 8960, 2240, 259840, 87360, 13440, 2240, 2598400, 873600, 134400, 22400, 28582400, 9609600, 1478400, 246400, 343235200, 114329600, 19219200, 1971200, 246400, 4462057600, 1486284800, 249849600, 25625600, 3203200, 62468806400, 20807987200, 3497894400, 358758400, 44844800, 936987251200, 312344032000, 52019968000, 5829824000, 448448000, 44844800

Offset: 0

Dennis P. Walsh, Feb 23 2011

Triangle T(n,k) with 0<=k<=floor(n/3) gives the number of permutations in the symmetric group Sn that have exactly k cycles of length 3. The sum of T(n,k) over all k equals n!.

			For n=4 and k=1, T(4,1)=8 since there are 8 permutations on 4 elements with 1 cycle of length 3, namely, (abc)(d), (acb)(d), (abd)(c), (adb)(c), (acd)(b), (adc)(b), (bcd)(a), and (bdc)(a).
Triangle T(n,k) begins:
:     1;
:     1;
:     2;
:     4,    2;
:    16,    8;
:    80,   40;
:   520,  160,   40;
:  3640, 1120,  280;
: 29120, 8960, 2240;
: ...

Arratia, R. and Tavaré, S. (1992). The cycle structure of random permutations. Ann. Probab. 20 1567-1591.

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

Cf. A000142, A057693, A008290, A114320.

seq(seq(n!*(1/3)^x/x!*sum((-1/3)^j/j!,j=0..(floor(n/3)-x)),x=0..floor(n/3)),n=0..15);
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(b(n-i)*
      `if`(i=3, x, 1)*binomial(n-1, i-1)*(i-1)!, i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..15);  # Alois P. Heinz, Sep 25 2016

nn = 8; Range[0, nn]! CoefficientList[
   Series[Exp[x^3/3 (y - 1)]/(1 - x), {x, 0, nn}], {x, y}] // Grid

T(n,k) = (n!(1/3)^k)/k!*sum((-1/3)^j/j!, j=0..(m-k)) where m=floor(n/3).

E.g.f.: exp(x^3/3*(y-1))/(1-x). - Geoffrey Critzer, Aug 26 2012.

cp's OEIS Frontend

A126074 Triangle read by rows: T(n,k) is the number of permutations of n elements that have the longest cycle length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A070945 Number of permutations on n letters that have only cycles of length 4 or less.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A070947 Number of permutations on n letters that have only cycles of length 6 or less.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A070946 Number of permutations on n letters that have only cycles of length 5 or less.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A334569 E.g.f.: exp(-(x + x^2/2 + x^3/3)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A071007 Number of permutations in the symmetric group S_n such that the maximal cycle has length exactly 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A202364 Number of n-permutations with at least one cycle of length >=4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula