cp's OEIS Frontend

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.

%I A136715 #7 Jun 01 2018 01:52:13
%S A136715 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,
%T A136715 1728,144,0,0,0,576,9216,20736,9216,576,0,0,0,0,14400,115200,172800,
%U A136715 57600,2880,0,0,0,0,14400,360000,1440000,1440000,360000,14400
%N 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.
%C A136715 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}.
%C A136715 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.
%C A136715 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.
%C A136715 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.
%C A136715 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.
%H A136715 Fredrik Jansson, <a href="http://www.math.chalmers.se/~einar/exjobb/fredrik-jansson.pdf">Variations on the excedance statistic in permutations</a>
%F A136715 Recurrence relations:
%F A136715 T(2n,k) = (k+1-n)*T(2n-1,k) + (3n-k)*T(2n-1,k-1) for n >= 1;
%F A136715 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.
%F A136715 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).
%F A136715 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.
%F A136715 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.
%F A136715 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 + ... .
%F A136715 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)).
%F A136715 Worpitzky-type identities:
%F A136715 Sum {k = n..2n} T(2n,k)*C(x+k,2n) = ((x+1)*(x+2)*...*(x+n))^2;
%F A136715 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);
%F A136715 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.
%e A136715 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.
%e A136715 Triangle starts
%e A136715 n\k|..1....2....3....4....5....6
%e A136715 --------------------------------
%e A136715 1..|..1
%e A136715 2..|..1....1
%e A136715 3..|..0....4....2
%e A136715 4..|..0....4...16....4
%e A136715 5..|..0....0...36...72...12
%e A136715 6..|..0....0...36..324..324...36
%Y A136715 Cf. A000142 (row sums), A008292, A008459, A103371, A120434, A134434, A136716, A136717.
%K A136715 easy,nonn,tabl
%O A136715 1,5
%A A136715 _Peter Bala_, Jan 18 2008