login
Triangular array counting derangements by number of descents.
2

%I #19 Feb 04 2020 16:57:35

%S 1,2,0,4,4,1,8,24,12,0,16,104,120,24,1,32,392,896,480,54,0,64,1368,

%T 5544,5984,1764,108,1,128,4552,30384,57640,34520,6048,224,0,256,14680,

%U 153400,470504,495320,180416,19936,448,1

%N Triangular array counting derangements by number of descents.

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

%H Shishuo Fu, Z. Lin, J. Zeng, <a href="http://arxiv.org/abs/1507.05184">Two new unimodal descent polynomials</a>, arXiv preprint arXiv:1507.05184 [math.CO], 2015-2019.

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

%e Array begins

%e 1

%e 2, 0

%e 4, 4, 1

%e 8, 24, 12, 0

%e 16, 104, 120, 24, 1

%e T(4,2) = 4 counts 2143, 3142, 3421, 4312.

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

%Y Cf. A008292. (analogous for permutations)

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

%K nonn,tabl

%O 2,2

%A _David Callan_, Nov 29 2012