login
Triangle of second-order Eulerian numbers of type B.
9

%I #41 Dec 17 2022 02:53:18

%S 1,1,1,1,8,3,1,33,71,15,1,112,718,744,105,1,353,5270,14542,9129,945,1,

%T 1080,33057,191384,300291,129072,10395,1,3265,190125,2033885,6338915,

%U 6524739,2071215,135135,1,9824,1038780,18990320,103829590,204889344,150895836,37237680,2027025

%N Triangle of second-order Eulerian numbers of type B.

%C 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.

%C 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.

%H Peter Bala, <a href="/A214406/a214406.txt">Second-order Eulerian numbers of type B</a>

%H Peter Bala, <a href="/A214406/a214406_2.txt">Notes on A214406</a>

%H L. Liu and Y. Wang, <a href="https://arxiv.org/abs/math/0509207">A unified approach to polynomial sequences with only real zeros</a> arXiv:math/0509207 [math.CO], 2005-2006.

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

%F 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.

%F 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.

%F 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.

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

%F 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.

%F Row sums are A001813.

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

%e Row 2: [1,8,3]:

%e Signed Stirling permutations of order 2

%e = = = = = = = = = = = = = = = = = = = =

%e ..............ascents...................ascents

%e (0 2 2 1 1)......1.......(0 -2 -2 1 1).....1

%e (0 1 2 2 1)......2.......(0 1 -2 -2 1).....2

%e (0 1 1 2 2)......2.......(0 1 1 -2 -2).....1

%e (0 2 2 -1 -1)....1.......(0 -2 -2 -1 -1)...1

%e (0 -1 2 2 -1)....1.......(0 -1 -2 -2 -1)...1

%e (0 -1 -1 2 2)....1.......(0 -1 -1 -2 -2)...0

%e ............................................

%e Triangle begins

%e .n\k.|..0.....1......2.......3......4........5......6

%e = = = = = = = = = = = = = = = = = = = = = = = = = = =

%e ..0..|..1

%e ..1..|..1.....1

%e ..2..|..1.....8......3

%e ..3..|..1....33.....71......15

%e ..4..|..1...112....718.....744....105

%e ..5..|..1...353...5270...14542...9129......945

%e ..6..|..1..1080..33057..191384..300291..129072..10395

%e ...

%e Recurrence example: T(4,2) = 11*T(3,1) + 5*T(3,2) = 11*33 + 5*71 = 718.

%t 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;

%t Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Nov 11 2019 *)

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

%K nonn,easy,tabl

%O 0,5

%A _Peter Bala_, Jul 17 2012

%E Missing 1 in data inserted by _Jean-François Alcover_, Nov 11 2019