A144699 Triangle of 5-Eulerian numbers.

1, 1, 5, 1, 16, 25, 1, 39, 171, 125, 1, 86, 786, 1526, 625, 1, 181, 3046, 11606, 12281, 3125, 1, 372, 10767, 70792, 142647, 92436, 15625, 1, 755, 36021, 380071, 1279571, 1553145, 663991, 78125, 1, 1522, 116368, 1880494, 9818494, 19555438, 15519952, 4608946, 390625

Offset: 5

Author

Peter Bala, Sep 19 2008

Keywords

• easy
• nonn
• tabl

Comments

This is the case r = 5 of the r-Eulerian numbers, denoted by A(r;n,k), defined as follows. Let [n] denote the ordered set {1,2,...,n} and let r be a nonnegative integer. Let Permute(n,n-r) denote the set of injective maps p:[n-r] -> [n], which we think of as permutations of n numbers taken n-r at a time. Clearly, |Permute(n,n-r)| = n!/r!. We say that the permutation p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number A(r;n,k) is defined as the number of permutations in Permute(n,n-r) with k excedances. Thus the 5-Eulerian numbers count the permutations in Permute(n,n-5) with k excedances. For other cases see A008292 (r = 0 and r = 1), A144696 (r = 2), A144697 (r = 3) and A144698 (r = 4).

An alternative interpretation of the current array due to [Strosser] involves the 5-excedance statistic of a permutation (see also [Foata & Schutzenberger, Chapitre 4, Section 3]). We define a permutation p in Permute(n,n-5) to have a 5-excedance at position i (1 <=i <= n-5) if p(i) >= i + 5.

Given a permutation p in Permute(n,n-5), define ~p to be the permutation in Permute(n,n-5) that takes i to n+1 - p(n-i-4). The map ~ is a bijection of Permute(n,n-5) with the property that if p has (resp. does not have) an excedance in position i then ~p does not have (resp. has) a 5-excedance at position n-i-4. Hence ~ gives a bijection between the set of permutations with k excedances and the set of permutations with (n-k) 5-excedances. Thus reading the rows of this array in reverse order gives a triangle whose entries count the permutations in Permute(n,n-5) with k 5-excedances.

Example: Represent a permutation p:[n-5] -> [n] in Permute(n,n-5) by its image vector (p(1),...,p(n-5)). In Permute(12,7) the permutation p = (1,2,4,12,3,6,5) does not have an excedance in the first two positions (i = 1 and 2) or in the final three positions (i = 5, 6 and 7). The permutation ~p = (8,7,10,1,9,11,12) has 5-excedances only in the first three positions and the final two positions.

Examples

			Triangle begins
=======================================================
n\k|..0.......1......2......3.........4.......5.......6
=======================================================
5..|..1
6..|..1.......5
7..|..1......16......25
8..|..1......39.....171.....125
9..|..1......86.....786....1526.....625
10.|..1.....181....3046...11606...12281....3125
11.|..1.....372...10767...70792..142647...92436...15625
...
T(7,1) = 16: We represent a permutation p:[n-5] -> [n] in Permute(n,n-5) by its image vector (p(1),...,p(n-5)). The 16 permutations in Permute(7,2) having 1 excedance are (1,3), (1,4), (1,5), (1,6), (1,7), (3,2), (4,2), (5,2), (6,2), (7,2), (2,1), (3,1), (4,1), (5,1), (6,1) and (7,1).
		

References

• R. Strosser, Séminaire de théorie combinatoire, I.R.M.A., Université de Strasbourg, 1969-1970.

Links

• G. C. Greubel, Rows n = 5..55 of the triangle, flattened
• J. F. Barbero G., J. Salas, and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624 [math.CO], 2013-2015.
• Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 9.
• Sergi Elizalde, Descents on quasi-Stirling permutations, arXiv:2002.00985 [math.CO], 2020.
• D. Foata and M. Schutzenberger, Théorie Géométrique des Polynômes Eulériens, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math., no. 138, Springer Verlag, 1970.
• L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, arXiv:math/0509207 [math.CO], 2005-2006.
• Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO], 2012. - From _N. J. A. Sloane_, Aug 21 2012

Crossrefs

Cf. A001725 (row sums), A008292, A143494, A144696, A144697, A144698.

Programs

Magma

m:=5; [(&+[(-1)^(k-j)*Binomial(n+1,k-j)*Binomial(j+m,m-1)*(j+1)^(n-m+1): j in [0..k]])/m: k in [0..n-m], n in [m..m+10]]; // G. C. Greubel, Jun 08 2022

Maple

with(combinat):
T:= (n,k) -> 1/5!*add((-1)^(k-j)*binomial(n+1,k-j)*(j+1)^(n-4)*(j+2)*(j+3)*(j+4)*(j+5),j = 0..k):
for n from 5 to 13 do
seq(T(n,k),k = 0..n-5)
end do;

Mathematica

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

SageMath

m=5 # A144699
def T(n,k): return (1/m)*sum( (-1)^(k-j)*binomial(n+1,k-j)*binomial(j+m,m-1)*(j+1)^(n-m+1) for j in (0..k) )
flatten([[T(n,k) for k in (0..n-m)] for n in (m..m+10)]) # G. C. Greubel, Jun 08 2022

Formula

T(n,k) = (1/5!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(n+1,k-j)*(j+1)^(n-4)*(j+2)*(j+3)*(j+4)*(j+5).

T(n,n-k) = (1/5!)*Sum_{j = 5..k} (-1)^(k-j)*binomial(n+1,k-j)*j^(n-4)*(j-1)*(j-2)*(j-3)*(j-4).

Recurrence relation:

T(n,k) = (k+1)*T(n-1,k) + (n-k)*T(n-1,k-1) with boundary conditions T(n,0) = 1 for n >= 5, T(5,k) = 0 for k >= 1.

E.g.f. (with suitable offsets): (1/5)*((1 - x)/(1 - x*exp(t - t*x)))^5 = 1/5 + x*t + (x + 5*x^2)*t^2/2! + (x + 16*x^2 + 25*x^3)*t^3/3! + ... .

The row generating polynomials R_n(x) satisfy the recurrence R_(n+1)(x) = (n*x+1)*R_n(x) + x*(1-x)*d/dx(R_n(x)) with R_5(x) = 1. It follows that the polynomials R_n(x) for n >= 6 have only real zeros (apply Corollary 1.2. of [Liu and Wang]).

The (n+4)-th row generating polynomial = (1/5!)*Sum_{k = 1..n} (k+4)!*Stirling2(n,k)*x^(k-1)*(1-x)^(n-k).

For n >= 5,

(1/5)*(x*d/dx)^(n-4) (1/(1-x)^5) = (x/(1-x)^(n+1)) * Sum_{k = 0..n-5} T(n,k)*x^k,

(1/5)*(x*d/dx)^(n-4) (x^5/(1-x)^5) = (1/(1-x)^(n+1)) * Sum_{k = 5..n} T(n,n-k)*x^k,

(1/(1-x)^(n+1)) * Sum_{k = 0..n-5} T(n,k)*x^k = (1/5!) * Sum_{m = 0..infinity} (m+1)^(n-4)*(m+2)*(m+3)*(m+4)*(m+5)*x^m,

(1/(1-x)^(n+1)) * Sum_{k = 5..n} T(n,n-k)*x^k = (1/5!) * Sum_{m = 5..infinity} m^(n-4)*(m-1)*(m-2)*(m-3)*(m-4)*x^m.

Worpitzky-type identities:

Sum_{k = 0..n-5} T(n,k)*binomial(x+k,n) = (1/5!)*x^(n-4)*(x-1)*(x-2)*(x-3)*(x-4).

Sum_{k = 5..n} T(n,n-k)* binomial(x+k,n) = (1/5!)*(x+1)^(n-4)*(x+2)*(x+3)*(x+4)*(x+5).

Relation with Stirling numbers (Frobenius-type identities):

T(n+4,k-1) = (1/5!) * Sum_{j = 0..k} (-1)^(k-j)* (j+4)!* binomial(n-j,k-j)*Stirling2(n,j) for n,k >= 1;

T(n+4,k-1) = (1/5!) * Sum_{j = 0..n-k} (-1)^(n-k-j)*(j+4)!* binomial(n-j,k)*S(5;n+5,j+5) for n,k >= 0 and

T(n+5,k) = (1/5!) * Sum_{j = 0..n-k} (-1)^(n-k-j)*(j+5)!* binomial(n-j,k)*S(5;n+5,j+5) for n,k >= 0, where S(5;n,k) denotes the 5-Stirling numbers of the second kind, which are given by the formula S(5;n+5,j+5) = 1/j!*Sum_{i = 0..j} (-1)^(j-i)*binomial(j,i)*(i+5)^n for n,j >= 0.