|
| |
|
|
A144696
|
|
Triangle of 2-Eulerian numbers.
|
|
9
|
|
|
|
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 well-known 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.
Let r be a nonnegative integer and 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 p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number, denoted by A(r;n,k), is defined as the number of permutations in Permute(n,n-r) having k excedances. Thus the current array of 2-Eulerian numbers gives the number of permutations in Permute(n,n-2) 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,n-1) that preserves the number of excedances of a permutation. Consequently, the 1-Eulerian numbers are equal to the 0-Eulerian numbers: A(1;n,k) = A(0;n,k) = A(n,k).
For other cases of r-Eulerian numbers see A144697 (r = 3), A144698 (r = 4) and A144699 (r = 5). There is also a concept of r-Stirling 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 2-excedance statistic of a permutation (see also [Foata & Schutzenberger, Chapitre 4, Section 3]). We define a permutation p in Permute(n,n-2) to have a 2-excedance at position i (1 <=i <= n-2) if p(i) >= i + 2.
Given a permutation p in Permute(n,n-2), define ~p to be the permutation in Permute(n,n-2) that takes i to n+1 - p(n-i-1). The map ~ is a bijection of Permute(n,n-2) with the property that if p has (resp. does not have) an excedance in position i then ~p does not have (resp. has) a 2-excedance at position n-i-1. Hence ~ gives a bijection between the set of permutations with k excedances and the set of permutations with (n-k) 2-excedances. Thus reading the rows of this array in reverse order gives a triangle whose entries count the permutations in Permute(n,n-2) with k 2-excedances.
Example: Represent a permutation p:[n-2] -> [n] in Permute(n,n-2) by its image vector (p(1),...,p(n-2)). 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 2-excedances only in the first three positions and the final two positions.
This is the array A(1,1,3) in the notation of Hwang et al. (p. 25), where the authors remark that the r-Eulerian numbers were first studied by Shanlan Li (Duoji Bilei, Ch. 4), who gave the summation formulas
Sum_{i = 2..n+1} (i-1)*C(i,2) = C(n+3,4) + 2*C(n+2,4)
Sum_{i = 2..n+1} (i-1)^2*C(i,2) = C(n+4,5) + 7*C(n+3,5) + 4*C(n+2,5)
Sum_{i = 2..n+1} (i-1)^3*C(i,2) = C(n+5,6) + 18*C(n+4,6) + 33*C(n+3,6) + 8*C(n+2,6). (End)
|
|
|
REFERENCES
|
J. Riordan. An introduction to combinatorial analysis. New York, J. Wiley, 1958.
R. Strosser. Séminaire de théorie combinatoire, I.R.M.A., Université de Strasbourg, 1969-1970.
Li, Shanlan (1867). Duoji bilei (Series summation by analogies), 4 scrolls. In Zeguxizhai suanxue (Mathematics from the Studio Devoted to the Imitation of the Ancient Chinese Tradition) (Jinling ed.), Volume 4.
Li, Shanlan (2019). Catégories analogues d’accumulations discrètes (Duoji bilei), traduit et commenté par Andrea Bréard. La Bibliothèque Chinoise. Paris: Les Belles Lettres.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = (1/2!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(n+1,k-j)*(j+1)^(n-1)*(j+2);
T(n,n-k) = (1/2!)*Sum_{j = 2..k} (-1)^(k-j)*binomial(n+1,k-j)*j^(n-1)*(j-1).
Recurrence relations:
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 >= 2, T(2,k) = 0 for k >= 1. Special cases: T(n,n-2) = 2^(n-2); T(n,n-3) = A066810(n-1).
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*(1-x)*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^(k-1)*(1-x)^(n-k).
For n >= 2,
(1/2)*(x*d/dx)^(n-1) (1/(1-x)^2) = x/(1-x)^(n+1) * Sum_{k = 0..n-2} T(n,k)*x^k,
(1/2)*(x*d/dx)^(n-1) (x^2/(1-x)^2) = 1/(1-x)^(n+1) * Sum_{k = 2..n} T(n,n-k)*x^k,
1/(1-x)^(n+1)*Sum_{k = 0..n-2} T(n,k)*x^k = (1/2!) * Sum_{m = 0..inf} (m+1)^(n-1)*(m+2)*x^m,
1/(1-x)^(n+1)*Sum_{k = 2..n} T(n,n-k)*x^k = (1/2!) * Sum_{m = 2..inf} m^(n-1)*(m-1)*x^m.
Worpitzky-type identities:
Sum_{k = 0..n-2} T(n,k)*binomial(x+k,n) = (1/2!)*x^(n-1)*(x - 1);
Sum_{k = 2..n} T(n,n-k)*binomial(x+k,n) = (1/2!)*(x + 1)^(n-1)*(x + 2).
Relation with Stirling numbers (Frobenius-type identities):
T(n+1,k-1) = (1/2!) * Sum_{j = 0..k} (-1)^(k-j)*(j+1)!* binomial(n-j,k-j)*Stirling2(n,j) for n,k >= 1;
T(n+1,k-1) = (1/2!) * Sum_{j = 0..n-k} (-1)^(n-k-j)*(j+1)!* binomial(n-j,k)*S(2;n+2,j+2) for n,k >= 1 and
T(n+2,k) = (1/2!) * Sum_{j = 0..n-k} (-1)^(n-k-j)*(j+2)!* binomial(n-j,k)*S(2;n+2,j+2) for n,k >= 0, where S(2;n,k) denotes the 2-Stirling 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)/(1-x)^4] = x^2*(1 + 7*x + 4*x^2)/(1-x)^5 and 1/2*x*d/dx [x*(x + 11*x^2 + 11*x^3 + x^4)/(1-x)^5] = x^2*(1 + 18*x + 33*x^2 + 8*x^3)/(1-x)^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..n-2} 2^k*T(n,k) = A069321(n-1). Sum_{k = 0..n-2} 2^(n-k)*T(n,k) = 4*A083410(n-1).
For n >=2, the shifted row polynomial t*R(n,t) = (1/2)*D^(n-1)(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))^(-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:[n-2] -> [n] in Permute(n,n-2) by its image vector (p(1),...,p(n-2)). 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)^(k-j)*binomial(n+1, k-j)*(j+1)^(n-1)*(j+2), j = 0..k):
for n from 2 to 10 do
seq(T(n, k), k = 0..n-2)
end do;
|
|
|
MATHEMATICA
|
T[n_, k_]:= 1/2!*Sum[(-1)^(k-j)*Binomial[n+1, k-j]*(j+1)^(n-1)*(j+2), {j, 0, k}];
|
|
|
PROG
|
(Magma) m:=2; [(&+[(-1)^(k-j)*Binomial(n+1, k-j)*Binomial(j+m, m-1)*(j+1)^(n-m+1): j in [0..k]])/m: k in [0..n-m], n in [m..m+10]]; // G. C. Greubel, Jun 04 2022
(SageMath)
def T(n, k): return (1/m)*sum( (-1)^(k-j)*binomial(n+1, k-j)*binomial(j+m, m-1)*(j+1)^(n-m+1) for j in (0..k) )
flatten([[T(n, k) for k in (0..n-m)] for n in (m..m+10)]) # G. C. Greubel, Jun 04 2022
|
|
|
CROSSREFS
|
Cf. A000182 (related to alt. row sums).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
