|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
LINKS
|
|
|
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).
|
|
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]];
|
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|