A144699 - OEIS

%I #48 Aug 08 2023 14:24:17

%S 1,1,5,1,16,25,1,39,171,125,1,86,786,1526,625,1,181,3046,11606,12281,

%T 3125,1,372,10767,70792,142647,92436,15625,1,755,36021,380071,1279571,

%U 1553145,663991,78125,1,1522,116368,1880494,9818494,19555438,15519952,4608946,390625

%N Triangle of 5-Eulerian numbers.

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

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

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

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

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

%H G. C. Greubel, <a href="/A144699/b144699.txt">Rows n = 5..55 of the triangle, flattened</a>

%H J. F. Barbero G., J. Salas, and E. J. S. Villaseñor, <a href="https://arxiv.org/abs/1307.5624">Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications</a>, arXiv preprint arXiv:1307.5624 [math.CO], 2013-2015.

%H Ming-Jian Ding and Bao-Xuan Zhu, <a href="https://doi.org/10.1016/j.aam.2023.102591">Some results related to Hurwitz stability of combinatorial polynomials</a>, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 9.

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2002.00985">Descents on quasi-Stirling permutations</a>, arXiv:2002.00985 [math.CO], 2020.

%H D. Foata and M. Schutzenberger, <a href="https://arxiv.org/abs/math/0508232">Théorie Géométrique des Polynômes Eulériens</a>, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math., no. 138, Springer Verlag, 1970.

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

%H Shi-Mei Ma, <a href="https://arxiv.org/abs/1208.3104">Some combinatorial sequences associated with context-free grammars</a>, arXiv:1208.3104v2 [math.CO], 2012. - From _N. J. A. Sloane_, Aug 21 2012

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

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

%F Recurrence relation:

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

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

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

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

%F For n >= 5,

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

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

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

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

%F Worpitzky-type identities:

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

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

%F Relation with Stirling numbers (Frobenius-type identities):

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

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

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

%e Triangle begins

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

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

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

%e 5..|..1

%e 6..|..1.......5

%e 7..|..1......16......25

%e 8..|..1......39.....171.....125

%e 9..|..1......86.....786....1526.....625

%e 10.|..1.....181....3046...11606...12281....3125

%e 11.|..1.....372...10767...70792..142647...92436...15625

%e ...

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

%p with(combinat):

%p 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):

%p for n from 5 to 13 do

%p seq(T(n,k),k = 0..n-5)

%p end do;

%t T[n_, k_] /; 0 < k <= n-5 := T[n, k] = (k+1) T[n-1, k] + (n-k) T[n-1, k-1];

%t T[_, 0] = 1; T[_, _] = 0;

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

%o (Magma)

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

%o (SageMath)

%o m=5 # A144699

%o 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) )

%o flatten([[T(n,k) for k in (0..n-m)] for n in (m..m+10)]) # _G. C. Greubel_, Jun 08 2022

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

%K easy,nonn,tabl

%O 5,3

%A _Peter Bala_, Sep 19 2008