A219836 Triangular array counting derangements by number of descents.

1, 2, 0, 4, 4, 1, 8, 24, 12, 0, 16, 104, 120, 24, 1, 32, 392, 896, 480, 54, 0, 64, 1368, 5544, 5984, 1764, 108, 1, 128, 4552, 30384, 57640, 34520, 6048, 224, 0, 256, 14680, 153400, 470504, 495320, 180416, 19936, 448, 1

Offset

2,2

Comments

T(n,k) is the number of derangements of [n] with k descents.

Links

Table of n, a(n) for n=2..46.

Shishuo Fu, Z. Lin, J. Zeng, Two new unimodal descent polynomials, arXiv preprint arXiv:1507.05184 [math.CO], 2015-2019.

Formula

The g.f. F(x,y) = Sum_{n>=2,1<=k<=n-1}T(n,k)x^n/n!y^k satisfies the partial differential equation (1-xy) D_{x}F + (y^2-y) D_{y}F = F + 1 - e^(-xy). (Is there a closed form solution?)

Example

Array begins
1
2, 0
4, 4, 1
8, 24, 12, 0
16, 104, 120, 24, 1
T(4,2) = 4 counts 2143, 3142, 3421, 4312.

Mathematica

u[n_, 0] := 0; u[n_, k_] /; k == n-1 := If [EvenQ[n], 1, 0]; u[n_, k_] /; 1 <= k <= n - 2 := (n - k) u[n - 1, k - 1] + (k + 1) u[n - 1, k]; Table[u[n, k], {n, 2, 10}, {k, n - 1}]

Crossrefs

Cf. A008292. (analogous for permutations)

Row sums give A000166. A046739 counts derangements of [n] by number of excedances.

Sequence in context: A167312 A114122 A319934 * A004174 A348874 A300328

Adjacent sequences: A219833 A219834 A219835 * A219837 A219838 A219839

Keyword

nonn,tabl

Author

David Callan, Nov 29 2012

Status

approved