A144696 - OEIS

%I #69 Aug 08 2023 14:23:35

%S 1,1,2,1,7,4,1,18,33,8,1,41,171,131,16,1,88,718,1208,473,32,1,183,

%T 2682,8422,7197,1611,64,1,374,9327,49780,78095,38454,5281,128,1,757,

%U 30973,264409,689155,621199,190783,16867,256

%N Triangle of 2-Eulerian numbers.

%C Let [n] denote the ordered set {1,2,...,n}. The symmetric group S_n consists of the injective mappings p:[n] -> [n]. Such a permutation p has an excedance at position i, 1 <= i < n, if p(i) > i. One well-known interpretation of the Eulerian numbers A(n,k) is that they count the permutations in the symmetric group S_n with k excedances. The triangle of Eulerian numbers is A008292 (but with an offset of 1 in the column numbering). We generalize this definition to restricted permutations as follows.

%C Let r be a nonnegative integer and 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 p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number, denoted by A(r;n,k), is defined as the number of permutations in Permute(n,n-r) having k excedances. Thus the current array of 2-Eulerian numbers gives the number of permutations in Permute(n,n-2) with k excedances. See the example section below for some numerical examples.

%C Clearly A(0;n,k) = A(n,k). The case r = 1 also produces the ordinary Eulerian numbers A(n,k). There is an obvious bijection from Permute(n,n) to Permute(n,n-1) that preserves the number of excedances of a permutation. Consequently, the 1-Eulerian numbers are equal to the 0-Eulerian numbers: A(1;n,k) = A(0;n,k) = A(n,k).

%C For other cases of r-Eulerian numbers see A144697 (r = 3), A144698 (r = 4) and A144699 (r = 5). There is also a concept of r-Stirling numbers of the first and second kinds - see A143491 and A143494. If we multiply the entries of the current array by a factor of 2 and then reverse the rows we obtain A120434.

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

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

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

%C From _Peter Bala_, Dec 27 2019: (Start)

%C This is the array A(1,1,3) in the notation of Hwang et al. (p. 25), where the authors remark that the r-Eulerian numbers were first studied by Shanlan Li (Duoji Bilei, Ch. 4), who gave the summation formulas

%C Sum_{i = 2..n+1} (i-1)*C(i,2) = C(n+3,4) + 2*C(n+2,4)

%C Sum_{i = 2..n+1} (i-1)^2*C(i,2) = C(n+4,5) + 7*C(n+3,5) + 4*C(n+2,5)

%C Sum_{i = 2..n+1} (i-1)^3*C(i,2) = C(n+5,6) + 18*C(n+4,6) + 33*C(n+3,6) + 8*C(n+2,6). (End)

%D J. Riordan. An introduction to combinatorial analysis. New York, J. Wiley, 1958.

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

%D Li, Shanlan (1867). Duoji bilei (Series summation by analogies), 4 scrolls. In Zeguxizhai suanxue  (Mathematics from the Studio Devoted to the Imitation of the Ancient Chinese Tradition) (Jinling ed.), Volume 4.

%D Li, Shanlan (2019). Catégories analogues d’accumulations discrètes (Duoji bilei), traduit et commenté par Andrea Bréard. La Bibliothèque Chinoise. Paris: Les Belles Lettres.

%H G. C. Greubel, <a href="/A144696/b144696.txt">Rows n = 2..52 of the triangle, flattened</a>

%H J. F. Barbero G., J. Salas, and E. J. S. Villaseñor, <a href="http://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 Mark Conger, <a href="https://arxiv.org/abs/math/0508112">A refinement of the Eulerian polynomials and the joint distribution of pi(1) and Des(pi) in S_n</a>, arXiv:math/0508112 [math.CO], 2005.

%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>, Lecture Notes in Math., no.138, Springer Verlag 1970; arXiv:math/0508232 [math.CO], 2005.

%H Hsien-Kuei Hwang, Hua-Huai Chern, and Guan-Huei Duh, <a href="https://arxiv.org/abs/1807.01412">An asymptotic distribution theory for Eulerian recurrences with applications</a>, arXiv:1807.01412 [math.CO], 2018-2019.

%H Tanya Khovanova and Rich Wang, <a href="https://arxiv.org/abs/2302.11067">Ending States of a Special Variant of the Chip-Firing Algorithm</a>, arXiv:2302.11067 [math.CO], 2023.

%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="http://arxiv.org/abs/1208.3104">Some combinatorial sequences associated with context-free grammars</a>, arXiv:1208.3104 [math.CO], 2012. - From _N. J. A. Sloane_, Aug 21 2012

%H Carla D. Savage and Gopal Viswanathan, <a href="https://doi.org/10.37236/16">The 1/k-Eulerian polynomials</a>, Elec. J. of Comb., Vol. 19, Issue 1, #P9 (2012). - From _N. J. A. Sloane_, Feb 06 2013

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

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

%F Recurrence relations:

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

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

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

%F For n >= 2,

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

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

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

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

%F Worpitzky-type identities:

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

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

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

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

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

%F T(n+2,k) = (1/2!) * Sum_{j = 0..n-k} (-1)^(n-k-j)*(j+2)!* binomial(n-j,k)*S(2;n+2,j+2) for n,k >= 0, where S(2;n,k) denotes the 2-Stirling numbers A143494(n,k).

%F The row polynomials of this array are related to the Eulerian polynomials. For example, 1/2*x*d/dx [x*(x + 4*x^2 + x^3)/(1-x)^4] = x^2*(1 + 7*x + 4*x^2)/(1-x)^5 and 1/2*x*d/dx [x*(x + 11*x^2 + 11*x^3 + x^4)/(1-x)^5] = x^2*(1 + 18*x + 33*x^2 + 8*x^3)/(1-x)^6.

%F Row sums A001710. Alternating row sums [1, -1, -2, 8, 16, -136, -272, 3968, 7936, ... ] are alternately (signed) tangent numbers and half tangent numbers - see A000182.

%F Sum_{k = 0..n-2} 2^k*T(n,k) = A069321(n-1). Sum_{k = 0..n-2} 2^(n-k)*T(n,k) = 4*A083410(n-1).

%F For n >=2, the shifted row polynomial t*R(n,t) = (1/2)*D^(n-1)(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))^(-2). - _Peter Bala_, Apr 22 2012

%e The triangle begins

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

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

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

%e 2..|..1

%e 3..|..1.....2

%e 4..|..1.....7.....4

%e 5..|..1....18....33.....8

%e 6..|..1....41...171...131....16

%e 7..|..1....88...718..1208...473....32

%e 8..|..1...183..2682..8422..7197..1611....64

%e ...

%e Row 4 = [1,7,4]: We represent a permutation p:[n-2] -> [n] in Permute(n,n-2) by its image vector (p(1),...,p(n-2)). Here n = 4. The permutation (1,2) has no excedances; 7 permutations have a single excedance, namely, (1,3), (1,4), (2,1), (3,1), (3,2), (4,1) and (4,2); the remaining 4 permutations, (2,3), (2,4), (3,4) and (4,3) each have two excedances.

%p with(combinat):

%p T:= (n,k) -> 1/2!*add((-1)^(k-j)*binomial(n+1,k-j)*(j+1)^(n-1)*(j+2), j = 0..k):

%p for n from 2 to 10 do

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

%p end do;

%t T[n_, k_]:= 1/2!*Sum[(-1)^(k-j)*Binomial[n+1, k-j]*(j+1)^(n-1)*(j+2), {j, 0, k}];

%t Table[T[n, k], {n,2,10}, {k,0,n-2}]//Flatten (* _Jean-François Alcover_, Oct 15 2019 *)

%o (Magma) m:=2; [(&+[(-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=2 # A144696

%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, A120434, A143491, A143494, A143497, A144697, A144698, A144699.

%Y Cf. A000079 (right diagonal), A001710 (row sums).

%Y Cf. A000182 (related to alt. row sums).

%K easy,nonn,tabl

%O 2,3

%A _Peter Bala_, Sep 19 2008