login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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,...,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.

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

EXAMPLE

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 22:32 EDT 2019. Contains 328134 sequences. (Running on oeis4.)