A214406 Triangle of second-order Eulerian numbers of type B.

1, 1, 1, 1, 8, 3, 1, 33, 71, 15, 1, 112, 718, 744, 105, 1, 353, 5270, 14542, 9129, 945, 1, 1080, 33057, 191384, 300291, 129072, 10395, 1, 3265, 190125, 2033885, 6338915, 6524739, 2071215, 135135, 1, 9824, 1038780, 18990320, 103829590, 204889344, 150895836, 37237680, 2027025

Offset: 0

Author

Peter Bala, Jul 17 2012

Keywords

• nonn
• easy
• tabl

Comments

The second-order Eulerian numbers A008517 count Stirling permutations by ascents. A Stirling permutation of order n is a permutation of the multiset {1,1,2,2,...,n,n} such that for each i, 1 <= i <= n, the elements lying between the two occurrences of i are larger than i.

We define a signed Stirling permutation of order n to be a vector (x_0, x_1, ..., x_(2*n)) such that x_0 = 0 and (|x_1|, ... ,|x_(2*n)|) is a Stirling permutation of order n. We say that a signed Stirling permutation (x_0, x_1, ... , x_(2*n)) has an ascent at position j, 0 <= j <= 2*n-1, if |x_j| < |x_(j+1)|. We define T(n,k), the second-order Eulerian numbers of type B, as the number of signed Stirling permutations of order n having k ascents. An example is given below.

Examples

			Row 2: [1,8,3]:
Signed Stirling permutations of order 2
= = = = = = = = = = = = = = = = = = = =
..............ascents...................ascents
(0 2 2 1 1)......1.......(0 -2 -2 1 1).....1
(0 1 2 2 1)......2.......(0 1 -2 -2 1).....2
(0 1 1 2 2)......2.......(0 1 1 -2 -2).....1
(0 2 2 -1 -1)....1.......(0 -2 -2 -1 -1)...1
(0 -1 2 2 -1)....1.......(0 -1 -2 -2 -1)...1
(0 -1 -1 2 2)....1.......(0 -1 -1 -2 -2)...0
............................................
Triangle begins
.n\k.|..0.....1......2.......3......4........5......6
= = = = = = = = = = = = = = = = = = = = = = = = = = =
..0..|..1
..1..|..1.....1
..2..|..1.....8......3
..3..|..1....33.....71......15
..4..|..1...112....718.....744....105
..5..|..1...353...5270...14542...9129......945
..6..|..1..1080..33057..191384..300291..129072..10395
...
Recurrence example: T(4,2) = 11*T(3,1) + 5*T(3,2) = 11*33 + 5*71 = 718.
		

Links

• Peter Bala, Second-order Eulerian numbers of type B
• Peter Bala, Notes on A214406
• L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros arXiv:math/0509207 [math.CO], 2005-2006.

Crossrefs

Cf. A001813 (row sums), A008517, A039755, A185896, A034940.

Programs

Mathematica

T[n_, k_] /; 0 < k <= n := T[n, k] = (4n-2k-1) T[n-1, k-1] + (2k+1) T[n-1, k]; T[, 0] = 1; T[, _] = 0;
Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 11 2019 *)

Formula

T(n,k) = Sum_{i = 0..k} (-1)^(i-k)*binomial(2*n+1,k-i)*S(n+i,i), where S(n,k) = 1/(2^k*k!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*(2*j+1)^n = A039755(n,k).

It appears that Sum_{k = 0..n} (-1)^(k+1)*T(n,k)/((2*n-k)*binomial(2*n,k)) = (-1)^n *(2^n-2)*Bernoulli(n)/n.

Recurrence equation: T(n,k) = (4*n-2*k-1)*T(n-1,k-1) + (2*k+1)*T(n-1,k), for n,k >= 0.

The row polynomials R(n,x) may be calculated by means of the recurrence equation R(0,x) = 1 and for n >= 0, R(n,x^2) = (1 - x^2)^(2*n)*d/dx( x/(1-x^2)^(2*n-1)*R(n-1,x^2) ). Equivalently, x*R(n,x^2)/(1 - x^2)^(2*n+1)) = D^n(x), where D is the differential operator x/(1 - x^2)*d/dx.

Another recurrence is R(n+1,x) = 2*x*(1 - x)*d/dx(R(n,x)) + (1 + (4*n+1)*x)*R(n,x). It follows that the row polynomials R(n,x) have only real zeros (apply Liu and Wang, Corollary 1.2 with f(x) = R(n,x) and g(x) = R'(n,x)).

For n >= 0, the rational functions Q(n,x) := R(n,x)/(1 - x)^(2*n+1) are the o.g.f.'s for the diagonals of the type B Stirling numbers of the second kind A039755. They appear to satisfy the semi-orthogonality property Integral_{x = 0..oo} (1 - x)*Q(n,x)*Q(m,x) dx = (-1)^n*(2^(n+m) - 2)*Bernoulli(n+m)/(n+m), for n, m >= 0 but excluding the case (n,m) = (0,0). A similar result holds for the row polynomials of A185896.

Row sums are A001813.

Define functions F(n,z) := Sum_{k >= 0} (2*k+1)^(k+n)*z^k/k!, n = 0,1,2,.... Then exp(-x/2)*F(n,x/2*exp(-x)) = R(n,x)/(1 - x)^(2*n+1). - Peter Bala, Jul 26 2012

Extensions

Missing 1 in data inserted by Jean-François Alcover, Nov 11 2019