OFFSET
1,3
COMMENTS
A permutation p of the set O_n := {1,3,5,...,2n-1} is a bijection p:O_n -> O_n. We say the permutation p has an excedance at position i, 1 <= i <= n, if p(2i-1) > i. For example, if we represent permutations in one line notation by the vector (p(1),p(3),...,p(2n-1)) then the permutation (1,3,7,9,5) of O_5 has three excedances in total (at positions 2, 3 and 4).
This array gives the number of permutations of the set O_n with k excedances. This is the viewpoint taken in [Jansson]. See A136715 for the corresponding array when O_n is replaced by the set E_n := {2,4,6,...,2n}.
Alternatively, the bijection f:O_n -> [n] defined by f(i) = (i+1)/2 allows us to work with permutations in the symmetric group S_n, rather than permutations of O_n. The excedance condition p(2i-1) > i on permutations of O_n becomes the equivalent condition 2*q(i)-1 > i on permutations q of [n].
Let now q be a permutation in the group S_n and define e(q):= |{i | 1 <= i < = n, 2*q(i)-1 > i}|. Then the (n,k)-th entry in this array gives the number of permutations q in S_n such that e(q) = k.
This excedance type statistic e(q) on the symmetric group S_n is related to a descent statistic as follows. Define a permutation q in S_n to have a descent from odd at position i, 1 <= i <= n-1, if q(i) is odd and q(i) > q(i+1).
For example, the permutation (2,6,5,3,1,4) in the group S_6 has two descents from odd (at position 3 and position 4). Array A134435 records the number of permutations in S_n with k descents from odd. Let d(q) = |{i | 1 <= i <= n-1, q(i) is odd & q(i) > q(i+1)}| count the descents from odd in the permutation q.
Comparison of the formulas for the entries of this table with the formulas for the entries of A134435 shows that e(q) and d(q) are related by sum {q in S_n} x^e(q) = x^floor(n/2)* sum {q in S_n} x^d(q). Thus the shifted excedance statistic e(q) - floor(n/2) and the descent statistic d(q) are equidistributed on the symmetric group S_n.
LINKS
Fredrik Jansson, Variations on the excedance statistic in permutations.
S. Kitaev and J. Remmel, Classifying descents according to parity, Annals of Combinatorics, 11, 2007, 173-193.
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+1-n)*T(2n,k) + (3n+1-k)*T(2n,k-1) for n >= 0. Boundary conditions: T(0,k) = 0 all k; T(1,0) = 1; T(n,0) = 0 for n > 1.
The recurrence relations have the explicit solution T(2n,n+k) = n!^2 * C(n-1,k) * C(n+1,k+1) and T(2n+1,n+k) = n!*(n+1)!*C(n,k)*C(n+1,k), or as a single formula, T(n,k) = floor(n/2)! * floor((n+1)/2)! * C(floor((n-1)/2),k-floor(n/2)) * C(floor(n/2)+1,k-floor((n-1)/2)).
Also T(2n,n+k) = n!*(n+1)!*N(n,k+1), where N(n,k) denotes the Narayana number A001263 (n,k).
For the even numbered rows, define the shifted row polynomials G(2n,x) := x^(1-n)* sum {k = n..2n-1} T(2n,k)*x^k . For the odd numbered rows, define the shifted row polynomials G(2n+1,x) := x^(1-n)* sum {k = n..2n} T(2n+1,k)*x^k.
The first few values are G(1,x) = x, G(2,x) = 2x, G(3,x) = 2x+4x^2 and G(4,x) = 12x+12x^2. The recurrence relations yield the identities x*d/dx(1/x*G(2n-1,x)/(1-x)^(2n)) = G(2n,x)/(1-x)^(2n+1) and x*d/dx(G(2n,x)/(1-x)^(2n+1)) = G(2n+1,x)/(1-x)^(2n+2), for n = 1,2,3,... .
An easy induction argument now gives the Taylor series expansions: G(2n,x)/(1-x)^(2n+1) = sum {m = 1..inf} m*((m+1)*(m+2)*...*(m+n-1))^2*(m+n)*x^m (note: there is a typo in proposition 3.3 of [Jansson]); G(2n+1,x)/(1-x)^(2n+2) = sum {m = 1..inf} (m*(m+1)*...*(m+n-1))^2*(m+n)*x^m.
For example, when n = 3 we have for row 6 the expansion (144x+432x^2+144x^3)/(1-x)^7 = 144x + 1440x^2+ 7200x^3 + ... = 1*(2*3)^2*4*x + 2*(3*4)^2*5*x^2 + 3*(4*5)^2*6*x^3 + ... and for row 7 the expansion (144x + 1728x^2 + 2592x^3 + 576x^4)/(1-x)^8 = 144x + 2880x^2 + 21600x^3 + ... = (1.2.3)^2*4*x + (2.3.4)^2*5*x^2 + (3.4.5)^2*6*x^3 + ... .
Relation with the Jacobi polynomials P_n(a,b,x): G(2n+2,x) = n!*(n+2)!*x*(1-x)^n*P_n(1,1,(1+x)/(1-x)), G(2n+1,x) = n!*(n+1)!*x*(1-x)^n *P_n(0,1,(1+x)/(1-x)).
Worpitzky-type identities:
Sum {k = n..2n-1} T(2n,k)*C(x+k,2n) = x*((x+1)*(x+2)*...*(x+n-1))^2*(x+n);
sum {k = n..2n} T(2n+1,k)*C(x+k,2n+1) = x*((x+1)*(x+2)*...*(x+n))^2; and for the odd numbered rows read in reverse order, sum {k = n..2n} T(2n+1,3n-k)*C(x+k,2n+1) = (x*(x+1)*(x+2)*...*(x+n-1))^2*(x+n).
EXAMPLE
T(3,2) = 4; the four permutations of the set {1,3,5} with 2 excedances are (1,3,5), (3,1,5), (3,5,1) and (5,3,1).
Triangle starts
n\k|..0....1....2....3....4....5
--------------------------------
1..|..1
2..|..0....2
3..|..0....2....4
4..|..0....0...12...12
5..|..0....0...12...72...36
6..|..0....0....0..144..432..144
CROSSREFS
KEYWORD
AUTHOR
Peter Bala, Jan 22 2008
STATUS
approved