A378495 Triangle read by rows: T(n,k) is the number of derangements in S_n with no k-cycles. 1 <= k <= n.

0, 0, 0, 0, 2, 0, 0, 6, 9, 3, 0, 24, 24, 44, 20, 0, 160, 225, 175, 265, 145, 0, 1140, 1224, 1434, 1350, 1854, 1134, 0, 8988, 11025, 12313, 12145, 11473, 14833, 9793, 0, 80864, 93456, 100232, 106280, 113336, 107576, 133496, 93176, 0, 809856, 965601, 1057761, 1141425, 1108161, 1162161, 1108161, 1334961, 972081

Offset: 1

Author

Peter Kagey, Nov 29 2024

Keywords

• nonn
• tabl

Comments

A derangement is a permutation with no fixed points.

Conjecture: For n >= 3, the GCD of the n-th row is n-1.

Examples

			Triangle begins:
   | 1      2      3       4       5       6       7       8      9
---+---------------------------------------------------------------
 1 | 0
 2 | 0,     0
 3 | 0,     2,     0
 4 | 0,     6,     9,      3
 5 | 0,    24,    24,     44,     20
 6 | 0,   160,   225,    175,    265,    145
 7 | 0,  1140,  1224,   1434,   1350,   1854,   1134
 8 | 0,  8988, 11025,  12313,  12145,  11473,  14833,   9793
 9 | 0, 80864, 93456, 100232, 106280, 113336, 107576, 133496, 93176
		

Crossrefs

Cf. A000166, A038205, A122974, A238474.

Formula

T(n,1) = 0.

T(n,k) = Sum_{i=0..n} (-1)^i*binomial(n,i)*A122974(n-i,k) for k > 1.

T(n,2) = A038205(n).

T(n,n-1) = A000166(n) for n >= 3.

T(n,n) = A000166(n) - (n-1)! for n >= 3.

Conjecture: T(n,n-1) - T(n,n-2) = abs(A238474(n-4)) for n >= 4.

Conjecture: T(n,n-2) - T(n,n) = (n-3)!*(n-4)*(n-1)/2 for n >= 5.