

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 2excedances.


3



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


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,...,2n1}.
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 2excedance 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 2excedances. Compare with A008292, the triangle of Eulerian numbers, which enumerates permutations by the usual excedance number and A136717 which enumerates permutations by multiplicative 3excedances.
Let e(p)= {i  1 <= i < = n, 2*p(i) > i} denote the number of multiplicative 2excedances in the permutation p of S_n. This 2excedance 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 <= n1, 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 <= n1, 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 2excedance statistic e(p)  ceiling(n/2) and the descent statistic d(p) are equidistributed on the symmetric group S_n.


LINKS

Table of n, a(n) for n=1..55.
Fredrik Jansson, Variations on the excedance statistic in permutations


FORMULA

Recurrence relations:
T(2n,k) = (k+1n)*T(2n1,k) + (3nk)*T(2n1,k1) for n >= 1;
T(2n+1,k) = (kn)*T(2n,k) + (3n+2k)*T(2n,k1) 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),kfloor((n+1)/2)) * C(floor((n+1)/2),kfloor(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^(1n)* 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 +(n1)* 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(2n1,x)/(1x)^(2n)) = F(2n,x)/(1x)^(2n+1) and x*d/dx(1/x*F(2n,x)/(1x)^(2n+1)) = F(2n+1,x)/(1x)^(2n+2), for n = 1,2,3,... . An easy induction argument now gives the Taylor series expansions: F(2n,x)/(1x)^(2n+1) = sum {m = 1..inf} (m*(m+1)*...*(m+n1))^2*x^m; F(2n+1,x)/(1x)^(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)/(1x)^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)/(1x)^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*(1x)^n *P_n(0,0,(1+x)/(1x)), F(2n+1,x) = n!*(n+1)!*x*(1x)^n *P_n(1,0,(1+x)/(1x)).
Worpitzkytype 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+2k)*C(x+k,2n+1) = (x+1)*((x+2)*(x+3)*...*(x+n+1))^2.


EXAMPLE

T(4,2) = 4; the four permutations in S_4 with two multiplicative 2excedances 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


CROSSREFS

Cf. A000142 (row sums), A008292, A008459, A103371, A120434, A134434, A136716, A136717.
Sequence in context: A121829 A021708 A016690 * A077116 A249507 A135730
Adjacent sequences: A136712 A136713 A136714 * A136716 A136717 A136718


KEYWORD

easy,nonn,tabl


AUTHOR

Peter Bala, Jan 18 2008


STATUS

approved



