A144698 Triangle of 4-Eulerian numbers.

1, 1, 4, 1, 13, 16, 1, 32, 113, 64, 1, 71, 531, 821, 256, 1, 150, 2090, 6470, 5385, 1024, 1, 309, 7470, 40510, 65745, 33069, 4096, 1, 628, 25191, 221800, 612295, 592884, 194017, 16384, 1, 1267, 81853, 1113919, 4835875, 7843369, 4915423, 1101157, 65536

Offset: 4

Author

Peter Bala, Sep 19 2008

Keywords

• easy
• nonn
• tabl

Comments

This is the case r = 4 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 4-Eulerian numbers are the number of permutations in Permute(n,n-4) with k excedances. For other cases see A008292 (r = 0 and r = 1), A144696 (r = 2), A144697 (r = 3) and A144699 (r = 5).

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

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

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

Examples

			Triangle begins
  ===+=============================================
  n\k|  0      1      2      3      4      5      6
  ===+=============================================
   4 |  1
   5 |  1      4
   6 |  1     13     16
   7 |  1     32    113     64
   8 |  1     71    531    821    256
   9 |  1    150   2090   6470   5385   1024
  10 |  1    309   7470  40510  65745  33069   4096
  ...
T(6,1) = 13: We represent a permutation p:[n-4] -> [n] in Permute(n,n-4) by its image vector (p(1),...,p(n-4)). The 13 permutations in Permute(6,2) having 1 excedance are (1,3), (1,4), (1,5), (1,6), (3,2), (4,2), (5,2), (6,2), (2,1), (3,1), (4,1), (5,1) and (6,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 = 4..54 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éometrique 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. A008292, A143493, A143496, A143499, A144696, A144697, A144699.

Cf. A001720 (row sums), A000302 (right diagonal).

Programs

Magma

m:=4; [(&+[(-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 04 2022

Maple

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

Mathematica

T[n_, k_] /; 0 < k <= n-4 := 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, 4, 12}, {k, 0, n-4}] // Flatten (* Jean-François Alcover, Nov 11 2019 *)

SageMath

m=4 # A144698
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 04 2022

Formula

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

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

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 >= 4, T(4,k) = 0 for k >= 1. Special cases: T(n,n-4) = 4^(n-4); T(n,n-5) = 5^(n-3) - 4^(n-3) - (n-3)*4^(n-4).

E.g.f. (with suitable offsets): 1/4*[(1 - x)/(1 - x*exp(t - t*x))]^4 = 1/4 + x*t + (x + 4*x^2)*t^2/2! + (x + 13*x^2 + 16*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_4(x) = 1. It follows that the polynomials R_n(x) for n >= 5 have only real zeros (apply Corollary 1.2. of [Liu and Wang]).

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

For n >= 4,

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

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

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

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

Worpitzky-type identities:

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

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

Relation with Stirling numbers (Frobenius-type identities):

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

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

T(n+4,k) = 1/4! * Sum_{j = 0..n-k} (-1)^(n-k-j)*(j+4)!* binomial(n-j,k)*S(4;n+4,j+4) for n,k >= 0, where S(4;n,k) denotes the 4-Stirling numbers of the second kind A143496(n,k).

For n >=4, the shifted row polynomial t*R(n,t) = (1/4)*D^(n-3)(f(x,t)) evaluated at x = 0, where D is the operator (1-t)*(1+x)*d/dx and f(x,t) = (1+x*t/(t-1))^(-4). - Peter Bala, Apr 22 2012