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

Author

David Callan, Nov 29 2012

Keywords

• nonn
• tabl

Comments

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A008292. (analogous for permutations)

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

Programs

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}]

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?)