A070947 -id:A070947 - 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

A057693 Number of permutations on n letters that have only cycles of length 3 or less.

Original entry on oeis.org

1, 1, 2, 6, 18, 66, 276, 1212, 5916, 31068, 171576, 1014696, 6319512, 41143896, 281590128, 2007755856, 14871825936, 114577550352, 913508184096, 7526682826848, 64068860545056, 561735627038496, 5068388485760832, 47026385852423616, 447837548306401728

Offset: 0

Dennis P. Walsh, Oct 20 2000

nonn

Related to sequence A000085 since it can be shown that sequence A000085 represents the number of permutations (on n letters) that have only cycles of length 2 or less. Letting b(i) denote the i-th term of the sequence A000085, we obtain a(n)=sum(binomial(n,3*j)*(3*j)!*(1/3)^j*b(n-3*j)/j!,j=0..floor(n/3))

			For example, a(4)=18 since there are 6 permutations with cycles of length 4 to exclude from the 24 permutations on 4 letters, namely (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3) and (1 4 3 2).

Dennis P. Walsh, The number of permutations with only small cycles, preprint.

Alois P. Heinz, Table of n, a(n) for n = 0..300
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, 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.
Dennis P. Walsh, Derivation of the sequence

Cf. A000085, A070945-A070947.

a:= proc(n) option remember; `if`(n<3, n!,
      a(n-1) +(n-1)*a(n-2) +(n-1)*(n-2)*a(n-3))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 06 2013

nn=20;Range[0,nn]!CoefficientList[Series[Exp[ x + x^2/2 + x^3/3],{x,0,nn}],x]  (* Geoffrey Critzer, Oct 28 2012 *)

a(n) = sum(binomial((n, 3 * j) * (3 * j)! * (1/3)^j/j! * sum(binomial(n-3 * j, 2 * k) * (2 * k)! * (1/2)^k/k!, k=0..floor((n-3 * j)/2)), j=0..floor(n/3)))
E.g.f.: exp( x + (x^2)/2 + (x^3)/3 ). Replacing 3 by "length k or less" in the definition of the sequence the E.g.f. is exp( x + (x^2)/2 + ... + (x^k)/k ). - Sharon Sela (sharonsela(AT)hotmail.com), May 16 2002
a(n) = a(n-1)+(n-1)*a(n-2)+(n-1)(n-2)*a(n-3). Generally, for n-permutations that have only cycles of length k or less the recurrence is: a(n)=Sum_i=0...k-1;P(n-1,i)*a(n-i-1) where P(x,i) is the falling factorial. - Geoffrey Critzer, May 23 2009
a(n) ~ n^(2*n/3)*exp(-2*n/3-5/18+5/6*n^(1/3)+1/2*n^(2/3))/sqrt(3) * (1 + 31/(324*n^(1/3)) + 302669/(1049760*n^(2/3))). - Vaclav Kotesovec, Aug 15 2013

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).

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

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

A057693 Number of permutations on n letters that have only cycles of length 3 or less.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula