login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144697 Triangle of 3-Eulerian numbers. 6

%I

%S 1,1,3,1,10,9,1,25,67,27,1,56,326,376,81,1,119,1314,3134,1909,243,1,

%T 246,4775,20420,25215,9094,729,1,501,16293,115105,248595,180639,41479,

%U 2187,1,1012,53388,590764,2048710,2575404,1193548,183412,6561

%N Triangle of 3-Eulerian numbers.

%C This is the case r = 3 of the r-Eulerian 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,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 the permutation p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number A(r;n,k) is defined as the number of permutations in Permute(n,n-r) with k excedances. Thus the 3-Eulerian numbers count the permutations in Permute(n,n-3) with k excedances (see the example section below for a numerical example).

%C For other cases see A008292 (r = 0 and r = 1), A144696 (r = 2), A144698 (r = 4) and A144699 (r = 5).

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

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

%C Example: Represent a permutation p:[n-3] -> [n] in Permute(n,n-3) by its image vector (p(1),...,p(n-3)). 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 3-excedances only in the first three positions and the final two positions.

%D R. Strosser, Seminaire de theorie combinatoire, I.R.M.A., Universite de Strasbourg, 1969-1970.

%H J. F. Barbero G., J. Salas and E. J. S. Villaseñor, <a href="https://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 D. Foata, M. Schutzenberger, <a href="https://arxiv.org/abs/math/0508232">Théorie Géometrique des Polynômes Eulériens</a>, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math., no. 138, Springer Verlag, 1970.

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

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

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

%F Recurrence relation:

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

%F 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! + ... .

%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_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]).

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

%F For n >= 3,

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

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

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

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

%F Worpitzky-type identities:

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

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

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

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

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

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

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

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

%e Triangle begins

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

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

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

%e 3..|..1

%e 4..|..1......3

%e 5..|..1.....10......9

%e 6..|..1.....25.....67.....27

%e 7..|..1.....56....326....376.....81

%e 8..|..1....119...1314...3134...1909....243

%e 9..|..1....246...4775..20420..25215...9094....729

%e ...

%e T(5,1) = 10: We represent a permutation p:[n-3] -> [n] in Permute(n,n-3) by its image vector (p(1),...,p(n-3)). 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).

%p with(combinat):

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

%p for n from 3 to 11 do

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

%p end do;

%Y Cf. A001715 (row sums), A008292, A060056, A143492, A143495, A144696, A144698, A144699.

%K easy,nonn,tabl

%O 3,3

%A _Peter Bala_, Sep 19 2008

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 19:58 EST 2019. Contains 319251 sequences. (Running on oeis4.)