cp's OEIS Frontend

Right border = A004527: (1, 2, 4, 12, 48, 192, ...).

Row sums = A007489 starting (1, 3, 9, 33, 153, ...).

Row sums = A001339: (1, 3, 11, 49, 261, ...).

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.

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.

Define a permutation (p(1),p(2),...,p(n)) in the symmetric group S_n to have a multiplicative 3-descent at position i, 1 <= i <= n-1, if p(i) > p(i+1) and 3|p(i). The (n,k)-th entry in this array gives the number of permutations in S_n with k multiplicative 3-descents.

Compare with A008292, the triangle of Eulerian numbers, which enumerates permutations by the usual descent number and A134434, which enumerates permutations by multiplicative 2-descents. This multiplicative 3-descent statistic is equidistributed on the symmetric group S_n with a multiplicative 3-excedance statistic - see A136717 for details.