|
%I #9 Nov 12 2019 03:44:09
%S 1,2,2,4,12,12,72,48,72,456,192,960,3120,960,10800,23760,5760,10800,
%T 133920,183600,34560,241920,1572480,1572480,241920,4233600,18869760,
%U 14878080,1935360,4233600,84309120,233331840,141644160,15482880
%N Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k entries divisible by 3 that are followed by a smaller entry (n>=1, k>=0).
%C 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.
%C 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.
%H 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 Recurrence relations: T(3n+1,k) = (k+1)*T(3n,k+1) + (3n+1-k)*T(3n,k); T(3n+2,k) = (k+1)*T(3n+1,k+1) + (3n+2-k)*T(3n+1,k); T(3n+3,k) = (k+1)*T(3n+2,k) + (3n+3-k)*T(3n+2,k-1); with boundary conditions T(n,-1) = 0 for all n, T(1,0) = 1, T(1,k) = 0 for k > 0.
%F The row polynomials A(n,x) := sum {k = 0..floor(n/3)} T(n,k)*x^k satisfy the recursion relations: A(3n+1,x) = (1-x)*d/dx(A(3n,x)) + (3n+1)*A(3n,x); A(3n+2,x) = (1-x)*d/dx(A(3n+1,x)) + (3n+2)*A(3n+1,x); A(3n+3,x) = (x-x^2)*d/dx(A(3n+2,x)) + ((3n+2)x+1)*A(3n+2,x).
%e T(3,1) = 4; the four permutations in the group S_3 with a single multiplicative 3-descent are (1,3,2), (3,1,2), (2,3,1) and (3,2,1). The remaining two permutations in S_3, namely (1,2,3) and (2,1,3), have no multiplicative 3-descents.
%e Table starts
%e n\k|..0....1....2
%e -----------------
%e 1..|..1
%e 2..|..2
%e 3..|..2....4
%e 4..|.12...12
%e 5..|.72...48
%e 6..|.72..456..192
%t T[n_?Positive, k_] /; 0 <= k <= Floor[n/3] := T[n, k] = Switch[Mod[n, 3], 1|2, (k+1)T[n-1, k+1] + (n-k)T[n-1, k], 0, (k+1)T[n-1, k] + (n-k)T[n-1, k-1]];
%t T[1, 0] = 1; T[_, _] = 0;
%t Table[T[n, k], {n, 1, 12}, {k, 0, Floor[n/3]}] // Flatten (* _Jean-François Alcover_, Nov 12 2019 *)
%Y Cf. A000142 (row sums), A008292, A134434, A136717.
%K easy,nonn,tabf
%O 1,2
%A _Peter Bala_, Jan 23 2008
%E Keyword corrected by _Peter Bala_, Oct 30 2008
|
