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