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

Comments

A derangement is a permutation with no fixed points.

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

Links

Table of n, a(n) for n=1..55.

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.

Example

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.

Sequence in context: A137250 A329290 A244133 * A348639 A244142 A161800

Adjacent sequences: A378492 A378493 A378494 * A378496 A378497 A378498

Keyword

nonn,tabl

Author

Peter Kagey, Nov 29 2024

Status

approved