

A144697


Triangle of 3Eulerian numbers.


6



1, 1, 3, 1, 10, 9, 1, 25, 67, 27, 1, 56, 326, 376, 81, 1, 119, 1314, 3134, 1909, 243, 1, 246, 4775, 20420, 25215, 9094, 729, 1, 501, 16293, 115105, 248595, 180639, 41479, 2187, 1, 1012, 53388, 590764, 2048710, 2575404, 1193548, 183412, 6561
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,3


COMMENTS

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


REFERENCES

R. Strosser, Seminaire de theorie combinatoire, I.R.M.A., Universite de Strasbourg, 19691970.


LINKS

Table of n, a(n) for n=3..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.
Mark Conger, A refinement of the Eulerian polynomials and the joint distribution of pi(1) and Des(pi) in S_n, arXiv:math/0508112 [math.CO], 2005.
Sergi Elizalde, Descents on quasiStirling permutations, arXiv:2002.00985 [math.CO], 2020.
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/3!*Sum_{j = 0..k} (1)^(kj)*binomial(n+1,kj)*(j+1)^(n2)*(j+2)*(j+3);
T(n,nk) = 1/3!*Sum_{j = 3..k} (1)^(kj)*binomial(n+1,kj)*j^(n2)*(j1)*(j2).
Recurrence relation:
T(n,k) = (k+1)*T(n1,k) + (nk)*T(n1,k1) with boundary conditions T(n,0) = 1 for n >= 3, T(3,k) = 0 for k >= 1. Special cases: T(n,n3) = 3^(n3); T(n,n4) = A086443 (n2).
E.g.f. (with suitable offsets): 1/3*[(1  x)/(1  x*exp(t  t*x))]^3 = 1/3 + x*t + (x + 3*x^2)*t^2/2! + (x + 10*x^2 + 9*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_3(x) = 1. It follows that the polynomials R_n(x) for n >= 4 have only real zeros (apply Corollary 1.2. of [Liu and Wang]).
The (n+2)th row generating polynomial = 1/3!*Sum_{k = 1..n} (k+2)!*Stirling2(n,k)*x^(k1)*(1x)^(nk).
For n >= 3,
1/3*(x*d/dx)^(n2) (1/(1x)^3) = x/(1x)^(n+1) * Sum_{k = 0..n3} T(n,k)*x^k,
1/3*(x*d/dx)^(n2) (x^3/(1x)^3) = 1/(1x)^(n+1) * Sum_{k = 3..n} T(n,nk)*x^k,
1/(1x)^(n+1) * Sum_{k = 0..n3} T(n,k)*x^k = 1/3! * Sum_{m = 0..inf} (m+1)^(n2)*(m+2)*(m+3)*x^m,
1/(1x)^(n+1) * Sum_{k = 3..n} T(n,nk)*x^k = 1/3! * Sum_{m = 3..inf} m^(n2)*(m1)*(m2)*x^m.
Worpitzkytype identities:
Sum_{k = 0..n3} T(n,k)* binomial(x+k,n) = 1/3!*x^(n2)*(x1) *(x2);
Sum_{k = 3..n} T(n,nk)* binomial(x+k,n) = 1/3!*(x+1)^(n2)*(x+2)*(x+3).
Relation with Stirling numbers (Frobeniustype identities):
T(n+2,k1) = 1/3! * Sum_{j = 0..k} (1)^(kj)* (j+2)!* binomial(nj,kj)*Stirling2(n,j) for n,k >= 1;
T(n+2,k1) = 1/3! * Sum_{j = 0..nk} (1)^(nkj)* (j+2)!* binomial(nj,k)*S(3;n+3,j+3) for n,k >= 1 and
T(n+3,k) = 1/3! * Sum_{j = 0..nk} (1)^(nkj)*(j+3)!* binomial(nj,k)*S(3;n+3,j+3) for n,k >= 0, where S(3;n,k) denotes the 3Stirling numbers A143495(n,k).
The row polynomials of this array are related to the 2Eulerian polynomials (see A144696). For example, 1/3*x*d/dx [x^3*(1 + 7*x + 4*x^2)/(1x)^5] = x^3*(1 + 10*x + 9*x^2)/(1x)^6 and 1/3*x*d/dx [x^3*(1 + 18*x + 33*x^2 + 8*x^3)/(1x)^6] = x^3*(1 + 25*x + 67*x^2 + 27*x^3)/(1x)^7.
For n >=3, the shifted row polynomial t*R(n,t) = 1/3*D^(n2)(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))^(3).  Peter Bala, Apr 22 2012


EXAMPLE

Triangle begins
=================================================
n\k..0......1......2......3......4......5......6
=================================================
3....1
4....1......3
5....1.....10......9
6....1.....25.....67.....27
7....1.....56....326....376.....81
8....1....119...1314...3134...1909....243
9....1....246...4775..20420..25215...9094....729
...
T(5,1) = 10: We represent a permutation p:[n3] > [n] in Permute(n,n3) by its image vector (p(1),...,p(n3)). The 10 permutations in Permute(5,2) having 1 excedance are (1,3), (1,4), (1,5), (3,2), (4,2), (5,2), (2,1), (3,1), (4,1) and (5,1).


MAPLE

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


MATHEMATICA

T[n_, k_] /; 0 < k <= n3 := T[n, k] = (k+1) T[n1, k] + (nk) T[n1, k1];
T[_, 0] = 1; T[_, _] = 0;
Table[T[n, k], {n, 3, 11}, {k, 0, n3}] // Flatten (* JeanFrançois Alcover, Nov 11 2019 *)


CROSSREFS

Cf. A001715 (row sums), A008292, A060056, A143492, A143495, A144696, A144698, A144699.
Sequence in context: A260178 A195812 A264491 * A185419 A252501 A281000
Adjacent sequences: A144694 A144695 A144696 * A144698 A144699 A144700


KEYWORD

easy,nonn,tabl


AUTHOR

Peter Bala, Sep 19 2008


STATUS

approved



