cp's OEIS Frontend

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.

%I A136717 #14 Nov 12 2019 04:14:59
%S A136717 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,
%T A136717 960,0,0,0,0,0,10800,23760,5760,0,0,0,0,0,10800,133920,183600,34560,0,
%U A136717 0,0,0,0,0,241920,1572480,1572480,241920
%N 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.
%C A136717 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.
%C A136717 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.
%C A136717 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.
%C A136717 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.
%C A136717 (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.)
%C A136717 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].
%C A136717 A137593 = A000012 * this triangular matrix. A137594 = A007318 * this triangular matrix. - _Gary W. Adamson_, Jan 28 2008
%H A136717 Fredrik Jansson, <a href="https://www.researchgate.net/publication/233732425_Variations_on_the_Excedance_Statistic_in_Permutations">Variations on the excedance statistic in permutations</a>, Thesis, Stockholm University, 2006.
%H A136717 S. Kitaev and J. Remmel, <a href="http://arXiv.org/abs/math/0604455">Classifying descents according to equivalence mod k</a>, arXiv:math/0604455 [math.CO], 2006.
%F A136717 Recurrence relations (apply proposition 2.2 of [Jansson]):
%F A136717 T(3n,k) = (k+1-2n)*T(3n-1,k) + (5n-k)*T(3n-1,k-1) for n >= 1;
%F A136717 T(3n+1,k) = (k-2n)*T(3n,k) + (5n+2-k)*T(3n,k-1) for n >= 0;
%F A136717 T(3n+2,k) = (k-1-2n)*T(3n+1,k) + (5n+4-k)*T(3n+1,k-1) for n >= 0.
%F A136717 Boundary conditions: T(0,k) = 0 all k; T(n,0) = 0 all n; T(1,1) = 1.
%F A136717 Define the shifted row polynomials R(n,x) by
%F A136717 R(n,x) := x^(1+floor(n/3)-n)* sum {k = n-floor(n/3)..n} T(n,k)*x^k.
%F A136717 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.
%F A136717 The recurrence relations yield the identities:
%F A136717 x*d/dx(1/x*R(3n,x)/(1-x)^(3n+1)) = R(3n+1,x)/(1-x)^(3n+2);
%F A136717 x*d/dx(1/x*R(3n+1,x)/(1-x)^(3n+2)) = R(3n+2,x)/(1-x)^(3n+3);
%F A136717 x*d/dx(R(3n+2,x)/(1-x)^(3n+3)) = R(3n+3,x)/(1-x)^(3n+4).
%F A136717 An easy induction argument now gives the Taylor series expansions:
%F A136717 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;
%F A136717 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.
%F A136717 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.
%F A136717 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 + ... .
%e A136717 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.
%e A136717 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.
%e A136717 Triangle starts
%e A136717 n\k|..1....2....3....4....5....6
%e A136717 ---+----------------------------
%e A136717 1..|..1
%e A136717 2..|..0....2
%e A136717 3..|..0....2....4
%e A136717 4..|..0....0...12...12
%e A136717 5..|..0....0....0...72...48
%e A136717 6..|..0....0....0...72..456..192
%Y A136717 Cf. A000142 (row sums), A008292, A136718, A136715.
%Y A136717 Cf. A137593, A137594.
%K A136717 easy,nonn,tabl
%O A136717 1,3
%A A136717 _Peter Bala_, Jan 23 2008