SECOND-ORDER EULERIAN NUMBERS OF TYPE B Peter Bala, Jul 17 2012 STIRLING PERMUTATIONS A Stirling permutation (x_1,...,x_(2*n)) 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 say that a Stirling permutation (x_1,...,x_(2*n)) has an ascent at position i if x_i < x_(i+1). EXAMPLE (2344321551) is a Stirling permutation of order 5 with ascents at positions 1, 2, and 7. There is a simple recursive procedure for producing Stirling permutations: given a Stirling permutation p of order n insert the pair of numbers (n+1,n+1) into one of (2*n+1) places, either between the existing elements of p or at the front or at the end of p, to produce a Stirling permutation of order n+1. An easy consequence of this algorithm is that the total number of Stirling permutations of order n is (2*n-1)!!. The second-order Eulerian number A008517(n,k) is defined as the number of Stirling permutations of order n with k ascents. In order to define the type B version of the second-order Eulerian numbers we need a signed analog of the Stirling permutations. SIGNED STIRLING PERMUTATIONS A signed Stirling permutation of order n is 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. Signed Stirling permutations always begin with a 0. We say that a signed Stirling permutation (x_0,x_1,...,x_(2*n)) has an ascent at position i, 0 <= i <= 2*n-1, and call i an ascent position, if x_i < x_(i+1). A subscript i, 0 <= i <= 2*n-1, such that x_i = x_(i+1) or x_i > x_(i+1) will be called a non-ascent position. A signed Stirling permutation of order n with k ascent positions has (2*n-k) non-ascent positions. EXAMPLE (0 -2 3 4 4 3 -2 1 -5 -5 1) is a signed Stirling permutation of order 5 with ascents at positions 1, 2, 6 and 9. The permutation has 6 non-ascent positions. The recursive procedure for producing Stirling permutations is: given a signed Stirling permutation p of order n insert either the pair (n+1,n+1) or the pair (-(n+1),-(n+1)) into one of (2*n+1) places, either between the existing elements of p or at end of p, to produce a signed Stirling permutation of order n+1. The total number of signed Stirling permutations of order n is easily seen to be 2^n*(2*n-1)!!. Let T(n,k) denote the number of signed Stirling permutations of order n with k ascents, with the convention that T(0,0) = 1. Then T(n,k) is a type B analog of the second-order Eulerian numbers A008517(n,k). The recursive procedure for producing signed Stirling permutations leads to a proof of the following proposition. PROPOSITION 1 T(n,k) satisfies the recurrence equation T(n+1,k) = (4*n-2*k+3)*T(n,k-1) + (2*k+1)*T(n,k), n,k >= 0. PROOF A signed Stirling permutation of order n+1 with k ascents can be obtained from a signed Stirling permutation of order n in one of four (mutually exclusive) ways. 1) Let p = (0,x_1,...,x_(2n)) be any one of the T(n,k) signed Stirling permutations of order n having k ascents. Inserting the pair (n+1,n+1) into any of the k ascent positions of p gives a signed Stirling permutation of order n+1 also with k ascents. This results in k*T(n,k) permutations contributing to T(n+1,k). 2) Inserting the pair (-(n+1),-(n+1)) into any of the k ascent positions of p or at the end of p gives a signed Stirling permutation of order n+1 also with k ascents. This results in (k+1)*T(n,k) permutations contributing to T(n+1,k). 3) Now let q = (0,y_1,...,y_(2n)) be any one of the T(n,k-1) signed Stirling permutations having k-1 ascents.Inserting the pair (n+1,n+1) into any of the (2*n-(k-1)) non-ascent positions of q or at the end of q gives a signed Stirling permutation of order n+1 with k ascents. This results in (2*n-(k-1)+1)*T(n,k-1) = (2*n-k+2)*T(n,k-1) permutations contributing to T(n+1,k). 4) Finally, inserting the pair (-(n+1),-(n+1)) into any of the (2*n-(k-1)) non-ascent positions of q gives a signed Stirling permutation of order n+1 with k ascents. This results in (2*n-k+1)*T(n,k) permutations contributing to T(n+1,k). Thus in total T(n+1,k) = k*T(n,k) + (k+1)*T(n,k) + (2*n-k+2)*T(n,k-1) + (2*n-k+1)*T(n,k) = (2*k+1)*T(n,k) + (4*n-2*k+3)*T(n,k-1). END SECOND-ORDER EULERIAN NUMBERS 0F TYPE B - A214406 The triangle begins n\k 0 1 2 3 4 0 1 1 1 1 2 1 8 3 3 1 33 71 15 4 1 112 718 744 105 Let R(n,x) := sum {k = 0..n} T(n,k)*x^k (1) denote the nth row polynomial of the table. R(n,x) is thus the generating function for the signed Stirling permutations of order n by ascents. The first few values are R(0,x) = 1 R(1,x) = 1 + x R(2,x) = 1 + 8*x + 3*x^2 R(4,x) = 1 + 33*x + 71*x^2 + 15*x^3. It is straightforward to verify that the recurrence equation for the terms T(n,k) in Proposition 1 translates into the following recurrence for the type B row polynomials: R(n+1,x) = 2*x*(1-x)*R'(n,x) + (1+(4*n+1)*x)*R(n,x) n = 0,1,2,..., (2) (the prime 'indicates differentiation with respect to x). EXERCISE Let D be the differential operator x/(1-x^2)*d/dx. Show by induction that the rational function u(n,x) := x*R(n,x^2)/(1-x^2)^(2*n+1) (3) satisifes the recurrence u(n+1,x) = D(u(n,x)). (4) CONNECTION WITH THE TYPE B STIRLING NUMBERS OF THE SECOND KIND Sequence A039755, the triangle of type B Stirling numbers of the second kind, begins n\k 0 1 2 3 4 5 0 1 1 1 1 2 1 4 1 3 1 13 9 1 4 1 40 58 16 1 5 1 121 330 170 25 1 This is a Galton array, the entries T(n,k) satisfying the recurrence equation T(n+1,k) = (2*k+1)*T(n,k) + T(n,k-1). (5) It follows that the entries d(n,k) := T(n+k,k) lying along the nth diagonal of the triangle satisfy the recurrence d(n+1,k) = (2*k+1)*d(n,k) + d(n+1,k-1). (6) PROPOSITION 2 The ordinary generating functions for the diagonals of triangle A039755 are rational functions Q(n,x) of the form Q(n,x) := R(n,x)/(1-x)^(2*n+1) (7) where R(n,x) are the row polynomials of the second-order Eulerian numbers of type B. PROOF From (3) x*Q(n,x^2) = u(n,x) and so by (4) x*Q(n+1,x^2) = x/(1-x^2)*d/dx(x*Q(n,x^2)). (8). Let the expansion of Q(n,x) be Q(n,x) = sum {k = 0..inf} c(n,k)*x^k. Then from (8) (1-x^2)* sum {k = 0..inf} c(n+1,k)*x^(2*k) = sum {k = 0..inf} (2*k+1)*c(n,k)*x^(2*k) Equating coefficients on both sides yields the recurrence c(n+1,k) = (2*k+1)*c(n,k) + c(n+1,k-1). This is the same recurrence equation as (6) satisfied by d(n,k). It is an easy matter to check that c(n,k) and d(n,k) share the same initial conditions. Hence we conclude that c(n,k) = d(n,k) and the functions Q(n,x) are indeed the generating functions for the diagonals of A039755. END We give the first few cases of the proposition. Q(0,x) = 1/(1-x) = 1 + x + x^2 + x^3 + ... Q(1,x) = (1+x)/(1-x)^3 = 1 + 4*x + 9*x^2 + 16*x^3 + ... Q(2,x) = (1+8*x+3*x^2)/(1-x)^5 = 1 + 13*x + 58*x^2 + 170*x^3 + .... CONJECTURAL CONNECTION WITH THE BERNOULLI NUMBERS The functions Q(n,x) appear to satisfy the semi-orthogonality property int {x = 0..inf} (1-x)*Q(n,x)*Q(m,x) dx = (-1)^n*(2^(n+m)-2)*Bernoulli(n+m)/(n+m) when n,m >=0 but excluding the case (n,m) = (0,0). -------------------------------------------------------------------------------------------------------------------------------------