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

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

Author

Peter Kagey, Apr 28 2020

Keywords

• nonn
• tabl

Examples

			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
		

Links

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

Crossrefs

Cf. A068424, A333726.

Columns 2-6: A000085, A057693, A070945, A070946, A070947.

T(n,floor(n/2)) gives A024168.

Cf. A126074.

Programs

Mathematica

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

PARI

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

Formula

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