%I
%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 2Eulerian 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 wellknown 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,nr) denote the set of injective maps p:[nr] > [n], which we think of as permutations of n numbers taken nr at a time. Clearly, Permute(n,nr) = n!/r!. We say that p has an excedance at position i, 1 <= i <= nr, if p(i) > i. Then the rEulerian number, denoted by A(r;n,k), is defined as the number of permutations in Permute(n,nr) having k excedances. Thus the current array of 2Eulerian numbers gives the number of permutations in Permute(n,n2) 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,n1) that preserves the number of excedances of a permutation. Consequently, the 1Eulerian numbers are equal to the 0Eulerian numbers: A(1;n,k) = A(0;n,k) = A(n,k).
%C For other cases of rEulerian numbers see A144697 (r = 3), A144698 (r = 4) and A144699 (r = 5). There is also a concept of rStirling 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 2excedance statistic of a permutation (see also [Foata & Schutzenberger, Chapitre 4, Section 3]). We define a permutation p in Permute(n,n2) to have a 2excedance at position i (1 <=i <= n2) if p(i) >= i + 2.
%C Given a permutation p in Permute(n,n2), define ~p to be the permutation in Permute(n,n2) that takes i to n+1  p(ni1). The map ~ is a bijection of Permute(n,n2) with the property that if p has (resp. does not have) an excedance in position i then ~p does not have (resp. has) a 2excedance at position ni1. Hence ~ gives a bijection between the set of permutations with k excedances and the set of permutations with (nk) 2excedances. Thus reading the rows of this array in reverse order gives a triangle whose entries count the permutations in Permute(n,n2) with k 2excedances.
%C Example: Represent a permutation p:[n2] > [n] in Permute(n,n2) by its image vector (p(1),...,p(n2)). 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 2excedances only in the first three positions and the final two positions.
%D J. Riordan.  An introduction to combinatorial analysis.  New York, J. Wiley, 1958.
%D Carla D. Savage and Gopal Viswanathan, The 1/kEulerian Polynomials, Electr. J. Combinatorics, 19 (2012), #P9.  From _N. J. A. Sloane_, Feb 06 2013
%D R. Strosser.  Seminaire de theorie combinatoire, I.R.M.A., Universite de Strasbourg, 19691970.
%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, 2013
%H Mark Conger. <a href="http://arxiv.org/abs/math.CO/0508112"> A refinement of the Eulerian polynomials and the joint distribution of pi(1) and Des(pi) in S_n.</a>
%H D. Foata, M. Schutzenberger. <a href="http://www.arXiv.org/abs/math.CO/0508232"> Theorie Geometrique des Polynomes Euleriens</a>, Lecture Notes in Math., no.138, Springer Verlag 1970.
%H L. Liu, Y. Wang, <a href="http://www.arXiv.org/abs/math.CO/0509207"> A unified approach to polynomial sequences with only real zeros</a>
%H ShiMei Ma, <a href="http://arxiv.org/abs/1208.3104">Some combinatorial sequences associated with contextfree grammars</a>, arXiv:1208.3104v2 [math.CO].  From N. J. A. Sloane, Aug 21 2012
%F T(n,k) = 1/2!*Sum_{j = 0..k} (1)^(kj)*binomial(n+1,kj)*(j+1)^(n1)*(j+2);
%F T(n,nk) = 1/2!*Sum_{j = 2..k} (1)^(kj)*binomial(n+1,kj)*j^(n1)*(j1).
%F Recurrence relations:
%F T(n,k) = (k+1)*T(n1,k) + (nk)*T(n1,k1) with boundary conditions T(n,0) = 1 for n >= 2, T(2,k) = 0 for k >= 1. Special cases: T(n,n2) = 2^(n2); T(n,n3) = A066810(n1).
%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*(1x)*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^(k1)*(1x)^(nk).
%F For n >= 2,
%F 1/2*(x*d/dx)^(n1) (1/(1x)^2) = x/(1x)^(n+1) * Sum_{k = 0..n2} T(n,k)*x^k,
%F 1/2*(x*d/dx)^(n1) (x^2/(1x)^2) = 1/(1x)^(n+1) * Sum_{k = 2..n} T(n,nk)*x^k,
%F 1/(1x)^(n+1)*Sum_{k = 0..n2} T(n,k)*x^k = 1/2! * Sum_{m = 0..inf} (m+1)^(n1)*(m+2)*x^m,
%F 1/(1x)^(n+1)*Sum_{k = 2..n} T(n,nk)*x^k = 1/2! * Sum_{m = 2..inf} m^(n1)*(m1)*x^m.
%F Worpitzkytype identities:
%F Sum_{k = 0..n2} T(n,k)*binomial(x+k,n) = 1/2!*x^(n1)*(x  1);
%F Sum_{k = 2..n} T(n,nk)*binomial(x+k,n) = 1/2!*(x + 1)^(n1)*(x + 2).
%F Relation with Stirling numbers (Frobeniustype identities):
%F T(n+1,k1) = 1/2! * Sum_{j = 0..k} (1)^(kj)*(j+1)!* binomial(nj,kj)*Stirling2(n,j) for n,k >= 1;
%F T(n+1,k1) = 1/2! * Sum_{j = 0..nk} (1)^(nkj)*(j+1)!* binomial(nj,k)*S(2;n+2,j+2) for n,k >= 1 and
%F T(n+2,k) = 1/2! * Sum_{j = 0..nk} (1)^(nkj)*(j+2)!* binomial(nj,k)*S(2;n+2,j+2) for n,k >= 0, where S(2;n,k) denotes the 2Stirling 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)/(1x)^4] = x^2*(1 + 7*x + 4*x^2)/(1x)^5 and 1/2*x*d/dx [x*(x + 11*x^2 + 11*x^3 + x^4)/(1x)^5] = x^2*(1 + 18*x + 33*x^2 + 8*x^3)/(1x)^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..n2} 2^k*T(n,k) = A069321(n1). Sum_{k = 0..n2} 2^(nk)*T(n,k) = 4*A083410(n1).
%F For n >=2, the shifted row polynomial t*R(n,t) = 1/2*D^(n1)(f(x,t)) evaluated at x = 0, where D is the operator (1t)*(1+x)*d/dx and f(x,t) = (1+x*t/(t1))^(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:[n2] > [n] in Permute(n,n2) by its image vector (p(1),...,p(n2)). 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)^(kj)*binomial(n+1,kj)*(j+1)^(n1)*(j+2), j = 0..k):
%p for n from 2 to 10 do
%p seq(T(n,k),k = 0..n2)
%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, n2}] // Flatten (* _JeanFrançois Alcover_, Oct 15 2019 *)
%Y Cf. A000182 (related to alt. row sums), A008292, A001710 (row sums), A120434, A143491, A143494, A143497, A144697, A144698, A144699.
%K easy,nonn,tabl
%O 2,3
%A _Peter Bala_, Sep 19 2008
%E Spelling/notation corrections by _Charles R Greathouse IV_, Mar 18 2010
