A136715 Triangle T(n,k), 1 <= k <= n, read by rows: T(n,k) is the number of permutations of the set {2,4,6,...,2n} with k excedances. Equivalently, T(n,k) is the number of permutations in the symmetric group S_n having k multiplicative 2-excedances.

1, 1, 1, 0, 4, 2, 0, 4, 16, 4, 0, 0, 36, 72, 12, 0, 0, 36, 324, 324, 36, 0, 0, 0, 576, 2592, 1728, 144, 0, 0, 0, 576, 9216, 20736, 9216, 576, 0, 0, 0, 0, 14400, 115200, 172800, 57600, 2880, 0, 0, 0, 0, 14400, 360000, 1440000, 1440000, 360000, 14400

Offset: 1

Author

Peter Bala, Jan 18 2008

Keywords

• easy
• nonn
• tabl

Comments

Let E_n denote the set {2,4,6,...,2n} and let p denote a bijection p:E_n -> E_n. We say the permutation p has an excedance at position i, 1 <= i <= n, if p(2i) > i. For example, if we represent p in one line notation by the vector (p(2),p(4),...,p(2n)), then the permutation (6,2,8,4,10) of E_5 has three excedances in total (at positions 1, 3 and 5). This array gives the number of permutations of the set E_n with k excedances. This is the viewpoint taken in [Jansson]. See A136716 for the corresponding array when the set E_n is replaced by the set O_n := {1,3,5,...,2n-1}.

Alternatively, we can work with permutations (p(1),p(2),...,p(n)) in the symmetric group S_n and define p to have a multiplicative 2-excedance at position i, 1 <= i <= n, if 2*p(i) > i. Then the (n,k)-th entry of this array gives the number of permutations in S_n with k multiplicative 2-excedances. Compare with A008292, the triangle of Eulerian numbers, which enumerates permutations by the usual excedance number and A136717 which enumerates permutations by multiplicative 3-excedances.

Let e(p)= |{i | 1 <= i < = n, 2*p(i) > i}| denote the number of multiplicative 2-excedances in the permutation p of S_n. This 2-excedance statistic e(p) on the symmetric group S_n is related to a descent statistic as follows.

Define a permutation p in S_n to have a descent from even at position i, 1 <= i <= n-1, if p(i) is even and p(i) > p(i+1). For example, the permutation (2,1,3,5,6,4) in S_6 has two descents from even (at position 1 and position 5). Array A134434 records the number of permutations of S_n with k descents from even.

Let d(p) = |{i | 1 <= i <= n-1, p(i) is even & p(i) > p(i+1)}| count the descents from even in the permutation p. Comparison of the formulas for the entries of this table with the formulas for the entries of A134434 shows that e(p) and d(p) are related by sum {p in S_n} x^e(p) = x^ceiling(n/2)* sum {p in S_n} x^d(p). Thus the shifted multiplicative 2-excedance statistic e(p) - ceiling(n/2) and the descent statistic d(p) are equidistributed on the symmetric group S_n.

Examples

			T(4,2) = 4; the four permutations in S_4 with two multiplicative 2-excedances are (3,4,1,2), (4,3,1,2), (3,1,4,2) and (4,1,3,2). Alternatively, the four permutations (6,8,2,4), (8,6,2,4), (6,2,8,4) and (8,2,6,4) of the set E_4 each have 2 excedances.
Triangle starts
n\k|..1....2....3....4....5....6
--------------------------------
1..|..1
2..|..1....1
3..|..0....4....2
4..|..0....4...16....4
5..|..0....0...36...72...12
6..|..0....0...36..324..324...36
		

Links

• Fredrik Jansson, Variations on the excedance statistic in permutations

Crossrefs

Cf. A000142 (row sums), A008292, A008459, A103371, A120434, A134434, A136716, A136717.

Formula

Recurrence relations:

T(2n,k) = (k+1-n)*T(2n-1,k) + (3n-k)*T(2n-1,k-1) for n >= 1;

T(2n+1,k) = (k-n)*T(2n,k) + (3n+2-k)*T(2n,k-1) for n >= 0. Boundary conditions: T(0,k) = 0 all k; T(n,0) = 0 all n; T(1,1) = 1.

The recurrence relations have the explicit solution T(2n,n+k) = [n!* C(n,k)]^2 and T(2n+1,n+k+1) = 1/(k+1)*[(n+1)!*C(n,k)]^2 = n!*(n+1)!*C(n,k)*C(n+1,k+1); or as a single formula, T(n,k) = floor(n/2)! * floor((n+1)/2)! * C(floor(n/2),k-floor((n+1)/2)) * C(floor((n+1)/2),k-floor(n/2)). Also T(2n,n+k) = n!^2 * A008459 (n,k); T(2n+1,n+k+1) = n!*(n+1)!* A103371 (n,k).

For the even numbered rows, define the shifted row polynomials F(2n,x) := x^(1-n)* sum {k = n..2n} T(2n,k)*x^k = n!^2 * x * (1 + C(n,1)^2*x + C(n,2)^2*x^2 + ... + C(n,n)^2*x^n). For the odd numbered rows, define the shifted row polynomials F(2n+1,x) := x^(-n)* sum {k = n+1..2n+1} T(2n+1,k)*x^k = n!*(n+1)!* ((n+1)*N(n+1,1)*x + n*N(n+1,2)*x^2 +(n-1)* N(n+1,3)*x^3 + ... + N(n+1,n+1)*x^(n+1)), where N(n,k) denotes the Narayana numbers. The first few values are F(1,x) = x, F(2,x) =x+x^2, F(3,x) = 4x+2x^2 and F(4,x) = 4x+16x^2+4x^2.

The recurrence relations yield the identities x*d/dx(F(2n-1,x)/(1-x)^(2n)) = F(2n,x)/(1-x)^(2n+1) and x*d/dx(1/x*F(2n,x)/(1-x)^(2n+1)) = F(2n+1,x)/(1-x)^(2n+2), for n = 1,2,3,... . An easy induction argument now gives the Taylor series expansions: F(2n,x)/(1-x)^(2n+1) = sum {m = 1..inf} (m*(m+1)*...*(m+n-1))^2*x^m; F(2n+1,x)/(1-x)^(2n+2) = sum {m = 1..inf} m*((m+1)*(m+2)*...*(m+n))^2*x^m.

For example, when n = 3 we have for row 6 the expansion (36x + 324x^2 + 324x^3 + 36x^4)/(1-x)^7 = 36x + 576x^2 + 3600x^3 + ... = (1.2.3)^2*x + (2.3.4)^2*x^2 + (3.4.5)^2*x^3 + ... and for row 7 the expansion (576x + 2592x^2 + 1728x^3 + 144x^4)/(1-x)^8 = 576x + 7200x^2 + 43200x^3 + ... = 1*(2.3.4)^2*x + 2*(3.4.5)^2*x^2 + 3*(4.5.6)^2*x^3 + ... .

Relation with the Jacobi polynomials P_n(a,b,x): F(2n,x) = n!^2*x*(1-x)^n *P_n(0,0,(1+x)/(1-x)), F(2n+1,x) = n!*(n+1)!*x*(1-x)^n *P_n(1,0,(1+x)/(1-x)).

Worpitzky-type identities:

Sum {k = n..2n} T(2n,k)*C(x+k,2n) = ((x+1)*(x+2)*...*(x+n))^2;

sum {k = n+1..2n+1} T(2n+1,k)*C(x+k,2n+1) = ((x+1)*(x+2)*...*(x+n))^2*(x+n+1);

and for the odd numbered rows read in reverse order, sum {k = n+1..2n+1} T(2n+1,3n+2-k)*C(x+k,2n+1) = (x+1)*((x+2)*(x+3)*...*(x+n+1))^2.