|
%I #56 Aug 08 2023 14:24:02
%S 1,1,4,1,13,16,1,32,113,64,1,71,531,821,256,1,150,2090,6470,5385,1024,
%T 1,309,7470,40510,65745,33069,4096,1,628,25191,221800,612295,592884,
%U 194017,16384,1,1267,81853,1113919,4835875,7843369,4915423,1101157,65536
%N Triangle of 4-Eulerian numbers.
%C 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).
%C 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.
%C 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.
%C 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.
%D R. Strosser, Séminaire de théorie combinatoire, I.R.M.A., Université de Strasbourg, 1969-1970.
%H G. C. Greubel, <a href="/A144698/b144698.txt">Rows n = 4..54 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éometrique 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/4!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(n+1,k-j)*(j+1)^(n-3)*(j+2)*(j+3)*(j+4).
%F 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).
%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 >= 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).
%F 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! + ... .
%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_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]).
%F 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).
%F For n >= 4,
%F 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,
%F 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,
%F 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,
%F 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,
%F Worpitzky-type identities:
%F Sum_{k = 0..n-4} T(n,k)*binomial(x+k,n) = (1/4!)*x^(n-3)*(x-1)*(x-2)*(x-3).
%F Sum_{k = 4..n} T(n,n-k)* binomial(x+k,n) = (1/4!)*(x+1)^(n-3)*(x+2)*(x+3)*(x+4).
%F Relation with Stirling numbers (Frobenius-type identities):
%F 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;
%F 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
%F 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).
%F 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
%e Triangle begins
%e ===+=============================================
%e n\k| 0 1 2 3 4 5 6
%e ===+=============================================
%e 4 | 1
%e 5 | 1 4
%e 6 | 1 13 16
%e 7 | 1 32 113 64
%e 8 | 1 71 531 821 256
%e 9 | 1 150 2090 6470 5385 1024
%e 10 | 1 309 7470 40510 65745 33069 4096
%e ...
%e 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).
%p with(combinat):
%p 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):
%p for n from 4 to 12 do
%p seq(T(n,k),k = 0..n-4)
%p end do;
%t T[n_, k_] /; 0 < k <= n-4 := 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, 4, 12}, {k, 0, n-4}] // Flatten (* _Jean-François Alcover_, Nov 11 2019 *)
%o (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
%o (SageMath)
%o m=4 # A144698
%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 04 2022
%Y Cf. A008292, A143493, A143496, A143499, A144696, A144697, A144699.
%Y Cf. A001720 (row sums), A000302 (right diagonal).
%K easy,nonn,tabl
%O 4,3
%A _Peter Bala_, Sep 19 2008
|
