

A144699


Triangle of 5Eulerian numbers.


6



1, 1, 5, 1, 16, 25, 1, 39, 171, 125, 1, 86, 786, 1526, 625, 1, 181, 3046, 11606, 12281, 3125, 1, 372, 10767, 70792, 142647, 92436, 15625, 1, 755, 36021, 380071, 1279571, 1553145, 663991, 78125, 1, 1522, 116368, 1880494, 9818494, 19555438, 15519952
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

5,3


COMMENTS

This is the case r = 5 of the rEulerian 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,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 the permutation p has an excedance at position i, 1 <= i <= nr, if p(i) > i. Then the rEulerian number A(r;n,k) is defined as the number of permutations in Permute(n,nr) with k excedances. Thus the 5Eulerian numbers count the permutations in Permute(n,n5) with k excedances. For other cases see A008292 (r = 0 and r = 1), A144696 (r = 2), A144697 (r = 3) and A144698 (r = 4).
An alternative interpretation of the current array due to [Strosser] involves the 5excedance statistic of a permutation (see also [Foata & Schutzenberger, Chapitre 4, Section 3]). We define a permutation p in Permute(n,n5) to have a 5excedance at position i (1 <=i <= n5) if p(i) >= i + 5.
Given a permutation p in Permute(n,n5), define ~p to be the permutation in Permute(n,n5) that takes i to n+1  p(ni4). The map ~ is a bijection of Permute(n,n5) with the property that if p has (resp. does not have) an excedance in position i then ~p does not have (resp. has) a 5excedance at position ni4. Hence ~ gives a bijection between the set of permutations with k excedances and the set of permutations with (nk) 5excedances. Thus reading the rows of this array in reverse order gives a triangle whose entries count the permutations in Permute(n,n5) with k 5excedances.
Example: Represent a permutation p:[n5] > [n] in Permute(n,n5) by its image vector (p(1),...,p(n5)). 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 5excedances only in the first three positions and the final two positions.


REFERENCES

R. Strosser, Séminaire de théorie combinatoire, I.R.M.A., Université de Strasbourg, 19691970.


LINKS

Table of n, a(n) for n=5..47.
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 [math.CO], 20132015.
D. Foata, M. Schutzenberger, Théorie Géometrique des Polynômes Eulériens, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math., no. 138, Springer Verlag, 1970.
L. Liu, Y. Wang, A unified approach to polynomial sequences with only real zeros, arXiv:math/0509207 [math.CO], 20052006.
ShiMei Ma, Some combinatorial sequences associated with contextfree grammars, arXiv:1208.3104v2 [math.CO], 2012.  From N. J. A. Sloane, Aug 21 2012


FORMULA

T(n,k) = 1/5!*Sum_{j = 0..k} (1)^(kj)*binomial(n+1,kj)*(j+1)^(n4)*(j+2)*(j+3)*(j+4)*(j+5).
T(n,nk) = 1/5!*Sum_{j = 5..k} (1)^(kj)*binomial(n+1,kj)*j^(n4)*(j1)*(j2)*(j3)*(j4).
Recurrence relation:
T(n,k) = (k+1)*T(n1,k) + (nk)*T(n1,k1) with boundary conditions T(n,0) = 1 for n >= 5, T(5,k) = 0 for k >= 1.
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! + ... .
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_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]).
The (n+4)th row generating polynomial = 1/5!*Sum_{k = 1..n} (k+4)!*Stirling2(n,k)*x^(k1)*(1x)^(nk).
For n >= 5,
1/5*(x*d/dx)^(n4) (1/(1x)^5) = x/(1x)^(n+1) * Sum_{k = 0..n5} T(n,k)*x^k,
1/5*(x*d/dx)^(n4) (x^5/(1x)^5) = 1/(1x)^(n+1) * Sum_{k = 5..n} T(n,nk)*x^k,
1/(1x)^(n+1) * Sum_{k = 0..n5} T(n,k)*x^k = 1/5! * Sum_{m = 0..inf} (m+1)^(n4)*(m+2)*(m+3)*(m+4)*(m+5)*x^m,
1/(1x)^(n+1) * Sum_{k = 5..n} T(n,nk)*x^k = 1/5! * Sum_{m = 5..inf} m^(n4)*(m1)*(m2)*(m3)*(m4)*x^m,
Worpitzkytype identities:
Sum_{k = 0..n5} T(n,k)*binomial(x+k,n) = 1/5!*x^(n4)*(x1)*(x2)*(x3)*(x4).
Sum_{k = 5..n} T(n,nk)* binomial(x+k,n) = 1/5!*(x+1)^(n4)*(x+2)*(x+3)*(x+4)*(x+5).
Relation with Stirling numbers (Frobeniustype identities):
T(n+4,k1) = 1/5! * Sum_{j = 0..k} (1)^(kj)* (j+4)!* binomial(nj,kj)*Stirling2(n,j) for n,k >= 1;
T(n+4,k1) = 1/5! * Sum_{j = 0..nk} (1)^(nkj)*(j+4)!* binomial(nj,k)*S(5;n+5,j+5) for n,k >= 0 and
T(n+5,k) = 1/5! * Sum_{j = 0..nk} (1)^(nkj)*(j+5)!* binomial(nj,k)*S(5;n+5,j+5) for n,k >= 0, where S(5;n,k) denotes the 5Stirling numbers of the second kind, which are given by the formula S(5;n+5,j+5) = 1/j!*Sum_{i = 0..j} (1)^(ji)*binomial(j,i)*(i+5)^n for n,j >= 0.


EXAMPLE

Triangle begins
=======================================================
n\k..0.......1......2......3.........4.......5.......6
=======================================================
5....1
6....1.......5
7....1......16......25
8....1......39.....171.....125
9....1......86.....786....1526.....625
10...1.....181....3046...11606...12281....3125
11...1.....372...10767...70792..142647...92436...15625
...
T(7,1) = 16: We represent a permutation p:[n5] > [n] in Permute(n,n5) by its image vector (p(1),...,p(n5)). 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).


MAPLE

with(combinat):
T:= (n, k) > 1/5!*add((1)^(kj)*binomial(n+1, kj)*(j+1)^(n4)*(j+2)*(j+3)*(j+4)*(j+5), j = 0..k):
for n from 5 to 13 do
seq(T(n, k), k = 0..n5)
end do;


CROSSREFS

Cf. A001725 (row sums), A008292, A143494, A144696, A144697, A144698.
Sequence in context: A211805 A211808 A093826 * A066787 A058352 A121755
Adjacent sequences: A144696 A144697 A144698 * A144700 A144701 A144702


KEYWORD

easy,nonn,tabl


AUTHOR

Peter Bala, Sep 19 2008


STATUS

approved



