login
Triangle T(n,k), 0 <= k < n, read by rows: T(n,k) is the number of permutations of the set O_n = {1,3,5,...,2n-1} with k excedances.
1

%I #7 Jun 01 2018 01:52:23

%S 1,0,2,0,2,4,0,0,12,12,0,0,12,72,36,0,0,0,144,432,144,0,0,0,144,1728,

%T 2592,576,0,0,0,0,2880,17280,17280,2880,0,0,0,0,2880,57600,172800,

%U 115200,14400,0,0,0,0,0,86400,864000,1728000,864000,86400

%N Triangle T(n,k), 0 <= k < n, read by rows: T(n,k) is the number of permutations of the set O_n = {1,3,5,...,2n-1} with k excedances.

%C 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).

%C 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}.

%C 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].

%C 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.

%C 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).

%C 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.

%C 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.

%H Fredrik Jansson, <a href="http://www.math.chalmers.se/~einar/exjobb/fredrik-jansson.pdf">Variations on the excedance statistic in permutations</a>.

%H S. Kitaev and J. Remmel, <a href="http://arXiv.org/abs/math/0508570">Classifying descents according to parity</a>, Annals of Combinatorics, 11, 2007, 173-193.

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

%F 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)).

%F Also T(2n,n+k) = n!*(n+1)!*N(n,k+1), where N(n,k) denotes the Narayana number A001263 (n,k).

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

%F 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,... .

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

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

%F 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)).

%F Worpitzky-type identities:

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

%F 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).

%e 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).

%e Triangle starts

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

%e --------------------------------

%e 1..|..1

%e 2..|..0....2

%e 3..|..0....2....4

%e 4..|..0....0...12...12

%e 5..|..0....0...12...72...36

%e 6..|..0....0....0..144..432..144

%Y Cf. A000142 (row sums), A001263, A008292, A134435, A136715, A136717.

%K easy,nonn,tabl

%O 1,3

%A _Peter Bala_, Jan 22 2008