A136715 -id:A136715 - cp's OEIS frontend

A134434 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k even entries that are followed by a smaller entry (n>=0, k>=0).

1, 1, 1, 1, 4, 2, 4, 16, 4, 36, 72, 12, 36, 324, 324, 36, 576, 2592, 1728, 144, 576, 9216, 20736, 9216, 576, 14400, 115200, 172800, 57600, 2880, 14400, 360000, 1440000, 1440000, 360000, 14400, 518400, 6480000, 17280000, 12960000, 2592000, 86400

Offset: 0

Emeric Deutsch, Nov 22 2007

Row n has 1+floor(n/2) entries. T(2n-1,0) = T(2n,0) = T(2n,n) = (n!)^2 = A001044(n).

This descent statistic is equidistributed on the symmetric group S_n with a multiplicative 2-excedance statistic - see A136715 for details. - Peter Bala, Jan 23 2008

			T(4,2) = 4 because we have 2143, 4213, 3421 and 4321.
Triangle starts:
   1;
   1;
   1,   1;
   4,   2;
   4,  16,   4;
  36,  72,  12;
  36, 324, 324, 36;
  ...

S. Kitaev and J. Remmel, Classifying descents according to parity, Annals of Combinatorics, 11, 2007, 173-193.

Bisection of column k=0 gives A001044 (even part).
Row sums give A000142.
Cf. A134435, A136715.

R[0]:=1:R[1]:=1: R[2]:=1+t: for n to 5 do R[2*n+1]:=sort(expand((1-t)* (diff(R[2*n], t))+(2*n+1)*R[2*n])): R[2*n+2]:=sort(expand(t*(1-t)*(diff(R[2*n+1], t))+(1+(2*n+1)*t)*R[2*n+1])) end do: for n from 0 to 11 do seq(coeff(R[n], t, j), j=0..floor((1/2)*n)); end do; # yields sequence in triangular form

T[n_,k_]:=If[EvenQ[n],Floor[(n/2)!Binomial[n/2,k]]^2, Floor[((n+1)/2)!Binomial[(n-1)/2,k]]^2/(k+1)]; Table[T[n,k],{n,11},{k,0,Floor[n/2]}]//Flatten (* Stefano Spezia, Jul 12 2024 *)

T(2n,k) = [n!*C(n,k)]^2; T(2n+1,k) = [(n+1)!*C(n,k)]^2/(k+1). See the Kitaev & Remmel reference for recurrence relations (Sec. 3).

T(0,0)=1 prepended by Alois P. Heinz, Jul 12 2024

A136717 Triangle T(n,k), 1 <= k <= n, read by rows: T(n,k) is the number of permutations in the symmetric group S_n having k multiplicative 3-excedances. Equivalently, the number of permutations of the set {3,6,9,...,3n} with k excedances.

Original entry on oeis.org

1, 0, 2, 0, 2, 4, 0, 0, 12, 12, 0, 0, 0, 72, 48, 0, 0, 0, 72, 456, 192, 0, 0, 0, 0, 960, 3120, 960, 0, 0, 0, 0, 0, 10800, 23760, 5760, 0, 0, 0, 0, 0, 10800, 133920, 183600, 34560, 0, 0, 0, 0, 0, 0, 241920, 1572480, 1572480, 241920

Offset: 1

Peter Bala, Jan 23 2008

A permutation (p(1),p(2),...,p(n)) in the symmetric group S_n has a multiplicative 3-excedance at position i, 1 <= i <= n, if 3*p(i) > i. The (n,k)-th entry in this array gives the number of permutations in S_n with k multiplicative 3-excedances.
Compare with A008292, the triangle of Eulerian numbers, which enumerates permutations by the usual excedance number and with A136715, which enumerates permutations by multiplicative 2-excedances.
Let e(p)= |{i | 1 <= i < = n, 3*p(i) > i}| denote the number of multiplicative 3-excedances in the permutation p. This 3-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 multiplicative 3-descent at position i, 1 <= i <= n-1, if p(i) is divisible by 3 and p(i) > p(i+1). For example, the permutation (4,1,6,5,3,2) in S_6 has two multiplicative 3-descents (at position 3 and position 5). Array A136718 records the number of permutations of S_n with k multiplicative 3-descents.
Let d(p) = |{i | 1 <= i <= n-1, p(i) is divisible by 3 & p(i) > p(i+1)}| count the multiplicative 3-descents in the permutation p. Comparison of the recursion relations for the entries of this table with the recursion relations for the entries of A136718 shows that e(p) and d(p) are related by sum {p in S_n} x^e(p) = x^ceiling(2*n/3)* sum {p in S_n} x^d(p). Thus the shifted multiplicative 3-excedance statistic e(p) - ceiling(2*n/3) and the multiplicative 3-descent statistic d(p) are equidistributed on the symmetric group S_n.
(Note: There is also an additive r-excedance statistic on the symmetric group, due to Riordan, where the condition r*p(i) > i is replaced by p(i) >= i+r. See A120434 for the r = 2 case.)
An alternative interpretation of this array is as follows: Let T_n denote the set {3,6,9,...,3n} and let now p denote a bijection p:T_n -> T_n. We say the permutation p has an excedance at position i, 1 <= i <= n, if p(3i) > i. For example, if we represent p in one line notation by the vector (p(3),p(6),...,p(3n)), then the permutation (9,18,3,12,15,6) of T_6 has four excedances in total (at positions 1, 2, 4 and 5). This array gives the number of permutations of the set T_n with k excedances. This is the viewpoint taken in [Jansson].
A137593 = A000012 * this triangular matrix. A137594 = A007318 * this triangular matrix. - Gary W. Adamson, Jan 28 2008

			T(3,3) = 4; the four permutations in S_3 with three multiplicative 3-excedances are (1,2,3), (1,3,2), (2,1,3) and (3,1,2). The remaining two permutations (2,3,1) and (3,2,1) each have two multiplicative 3-excedances.
Equivalently, the four permutations of the set {3,6,9} with 3 excedances are (3,6,9), (3,9,6), (6,3,9) and (9,3,6). The remaining two permutations (6,9,3) and (9,6,3) each have 2 excedances.
Triangle starts
n\k|..1....2....3....4....5....6
---+----------------------------
1..|..1
2..|..0....2
3..|..0....2....4
4..|..0....0...12...12
5..|..0....0....0...72...48
6..|..0....0....0...72..456..192

Fredrik Jansson, Variations on the excedance statistic in permutations, Thesis, Stockholm University, 2006.
S. Kitaev and J. Remmel, Classifying descents according to equivalence mod k, arXiv:math/0604455 [math.CO], 2006.

Cf. A000142 (row sums), A008292, A136718, A136715.

Cf. A137593, A137594.

Recurrence relations (apply proposition 2.2 of [Jansson]):
T(3n,k) = (k+1-2n)*T(3n-1,k) + (5n-k)*T(3n-1,k-1) for n >= 1;
T(3n+1,k) = (k-2n)*T(3n,k) + (5n+2-k)*T(3n,k-1) for n >= 0;
T(3n+2,k) = (k-1-2n)*T(3n+1,k) + (5n+4-k)*T(3n+1,k-1) for n >= 0.
Boundary conditions: T(0,k) = 0 all k; T(n,0) = 0 all n; T(1,1) = 1.
Define the shifted row polynomials R(n,x) by
R(n,x) := x^(1+floor(n/3)-n)* sum {k = n-floor(n/3)..n} T(n,k)*x^k.
The first few values are R(1,x) = x, R(2,x) = 2x, R(3,x) = 2x+4x^2 and R(4,x) = 12x+12x^2.
The recurrence relations yield the identities:
x*d/dx(1/x*R(3n,x)/(1-x)^(3n+1)) = R(3n+1,x)/(1-x)^(3n+2);
x*d/dx(1/x*R(3n+1,x)/(1-x)^(3n+2)) = R(3n+2,x)/(1-x)^(3n+3);
x*d/dx(R(3n+2,x)/(1-x)^(3n+3)) = R(3n+3,x)/(1-x)^(3n+4).
An easy induction argument now gives the Taylor series expansions:
R(3n,x)/(1-x)^(3n+1) = sum {m = 1..inf} m^2*(m+1)*(m+2)^2*(m+3)*...* (m+2n-2)^2*(m+2n-1)*x^m;
R(3n+1,x)/(1-x)^(3n+2) = sum {m = 1..inf} m*((m+1)^2*(m+2)*(m+3)^2*(m+4) *...*(m+2n-1)^2*(m+2n))*x^m.
R(3n+2,x)/(1-x)^(3n+3) = sum {m = 1..inf} m*((m+1)*(m+2)^2*(m+3)*(m+4)^2 *...*(m+2n-1)*(m+2n)^2)*(m+2n+1)*x^m.
For example, for row 6 (n = 2) we have the expansion (72x+456x^2+192x^3)/(1-x)^7 = 72x + 960x^2 + 5400x^3 + ... = (1^2*2*3^2*4)*x + (2^2*3*4^2*5)*x^2 + (3^2*4*5^2*6)*x^3 + ... .

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

Original entry on oeis.org

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, 2592, 576, 0, 0, 0, 0, 2880, 17280, 17280, 2880, 0, 0, 0, 0, 2880, 57600, 172800, 115200, 14400, 0, 0, 0, 0, 0, 86400, 864000, 1728000, 864000, 86400

Offset: 1

Peter Bala, Jan 22 2008

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.

			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

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.

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

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

cp's OEIS Frontend

A134434 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k even entries that are followed by a smaller entry (n>=0, k>=0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A136717 Triangle T(n,k), 1 <= k <= n, read by rows: T(n,k) is the number of permutations in the symmetric group S_n having k multiplicative 3-excedances. Equivalently, the number of permutations of the set {3,6,9,...,3n} with k excedances.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula