OFFSET
0,5
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.
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.
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
EXAMPLE
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.
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 *)
CROSSREFS
KEYWORD
AUTHOR
Peter Bala, Jul 17 2012
EXTENSIONS
Missing 1 in data inserted by Jean-François Alcover, Nov 11 2019
STATUS
approved