

A144696


Triangle of 2Eulerian numbers.


8



1, 1, 2, 1, 7, 4, 1, 18, 33, 8, 1, 41, 171, 131, 16, 1, 88, 718, 1208, 473, 32, 1, 183, 2682, 8422, 7197, 1611, 64, 1, 374, 9327, 49780, 78095, 38454, 5281, 128, 1, 757, 30973, 264409, 689155, 621199, 190783, 16867, 256
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,3


COMMENTS

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 number of 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.
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.
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).
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.
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.
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.
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.


REFERENCES

J. Riordan.  An introduction to combinatorial analysis.  New York, J. Wiley, 1958.
Carla D. Savage and Gopal Viswanathan, The 1/kEulerian Polynomials, Electr. J. Combinatorics, 19 (2012), #P9.  From N. J. A. Sloane, Feb 06 2013
R. Strosser.  Seminaire de theorie combinatoire, I.R.M.A., Universite de Strasbourg, 19691970.


LINKS

Table of n, a(n) for n=2..46.
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, 2013
Mark Conger.  A refinement of the Eulerian polynomials and the joint distribution of pi(1) and Des(pi) in S_n.
D. Foata, M. Schutzenberger.  Theorie Geometrique des Polynomes Euleriens, Lecture Notes in Math., no.138, Springer Verlag 1970.
L. Liu, Y. Wang,  A unified approach to polynomial sequences with only real zeros
ShiMei Ma, Some combinatorial sequences associated with contextfree grammars, arXiv:1208.3104v2 [math.CO].  From N. J. A. Sloane, Aug 21 2012


FORMULA

T(n,k) = 1/2!*Sum_{j = 0..k} (1)^(kj)*binomial(n+1,kj)*(j+1)^(n1)*(j+2);
T(n,nk) = 1/2!*Sum_{j = 2..k} (1)^(kj)*binomial(n+1,kj)*j^(n1)*(j1).
Recurrence relations:
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).
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! + ... .
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]).
The (n+1)th row generating polynomial = 1/2!*Sum_{k = 1..n} (k+1)!*Stirling2(n,k)*x^(k1)*(1x)^(nk).
For n >= 2,
1/2*(x*d/dx)^(n1) (1/(1x)^2) = x/(1x)^(n+1) * Sum_{k = 0..n2} T(n,k)*x^k,
1/2*(x*d/dx)^(n1) (x^2/(1x)^2) = 1/(1x)^(n+1) * Sum_{k = 2..n} T(n,nk)*x^k,
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,
1/(1x)^(n+1)*Sum_{k = 2..n} T(n,nk)*x^k = 1/2! * Sum_{m = 2..inf} m^(n1)*(m1)*x^m.
Worpitzkytype identities:
Sum_{k = 0..n2} T(n,k)*binomial(x+k,n) = 1/2!*x^(n1)*(x  1);
Sum_{k = 2..n} T(n,nk)*binomial(x+k,n) = 1/2!*(x + 1)^(n1)*(x + 2).
Relation with Stirling numbers (Frobeniustype identities):
T(n+1,k1) = 1/2! * Sum_{j = 0..k} (1)^(kj)*(j+1)!* binomial(nj,kj)*Stirling2(n,j) for n,k >= 1;
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
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).
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.
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.
Sum_{k = 0..n2} 2^k*T(n,k) = A069321(n1). Sum_{k = 0..n2} 2^(nk)*T(n,k) = 4*A083410(n1).
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


EXAMPLE

The triangle begins
===========================================
n\k..0.....1.....2.....3.....4.....5.....6
===========================================
2....1
3....1.....2
4....1.....7.....4
5....1....18....33.....8
6....1....41...171...131....16
7....1....88...718..1208...473....32
8....1...183..2682..8422..7197..1611....64
...
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.


MAPLE

with(combinat):
T:= (n, k) > 1/2!*add((1)^(kj)*binomial(n+1, kj)*(j+1)^(n1)*(j+2), j = 0..k):
for n from 2 to 10 do
seq(T(n, k), k = 0..n2)
end do;


CROSSREFS

Cf. A000182 (related to alt. row sums), A008292, A001710 (row sums), A120434, A143491, A143494, A143497, A144697, A144698, A144699.
Sequence in context: A255138 A115629 A296461 * A072248 A177011 A092276
Adjacent sequences: A144693 A144694 A144695 * A144697 A144698 A144699


KEYWORD

easy,nonn,tabl


AUTHOR

Peter Bala, Sep 19 2008


EXTENSIONS

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010


STATUS

approved



