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

1, 2, 2, 4, 12, 12, 72, 48, 72, 456, 192, 960, 3120, 960, 10800, 23760, 5760, 10800, 133920, 183600, 34560, 241920, 1572480, 1572480, 241920, 4233600, 18869760, 14878080, 1935360, 4233600, 84309120, 233331840, 141644160, 15482880

Offset: 1

Author

Peter Bala, Jan 23 2008

Keywords

• easy
• nonn
• tabf

Comments

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.

Examples

			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.
Table starts
n\k|..0....1....2
-----------------
1..|..1
2..|..2
3..|..2....4
4..|.12...12
5..|.72...48
6..|.72..456..192
		

Links

• S. Kitaev and J. Remmel, Classifying descents according to equivalence mod k, arXiv:math/0604455 [math.CO], 2006.

Crossrefs

Cf. A000142 (row sums), A008292, A134434, A136717.

Programs

Mathematica

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[1, 0] = 1; T[, ] = 0;
Table[T[n, k], {n, 1, 12}, {k, 0, Floor[n/3]}] // Flatten (* Jean-François Alcover, Nov 12 2019 *)

Formula

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.

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

Extensions

Keyword corrected by Peter Bala, Oct 30 2008