login
A330858
Triangle read by rows: T(n,k) is the number of permutations in S_n for which all cycles have length <= k.
2
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,3
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.
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
EXAMPLE
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
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 *)
PROG
(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
CROSSREFS
T(n,floor(n/2)) gives A024168.
Cf. A126074.
Sequence in context: A268472 A079474 A091543 * A059575 A338805 A120769
KEYWORD
nonn,tabl
AUTHOR
Peter Kagey, Apr 28 2020
STATUS
approved