

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



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Define a permutation (p(1),p(2),...,p(n)) in the symmetric group S_n to have a multiplicative 3descent at position i, 1 <= i <= n1, if p(i) > p(i+1) and 3p(i). The (n,k)th entry in this array gives the number of permutations in S_n with k multiplicative 3descents.
Compare with A008292, the triangle of Eulerian numbers, which enumerates permutations by the usual descent number and A134434, which enumerates permutations by multiplicative 2descents. This multiplicative 3descent statistic is equidistributed on the symmetric group S_n with a multiplicative 3excedance statistic  see A136717 for details.


LINKS

Table of n, a(n) for n=1..34.
S. Kitaev and J. Remmel, Classifying descents according to equivalence mod k, arXiv:math/0604455 [math.CO], 2006.


FORMULA

Recurrence relations: T(3n+1,k) = (k+1)*T(3n,k+1) + (3n+1k)*T(3n,k); T(3n+2,k) = (k+1)*T(3n+1,k+1) + (3n+2k)*T(3n+1,k); T(3n+3,k) = (k+1)*T(3n+2,k) + (3n+3k)*T(3n+2,k1); 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) = (1x)*d/dx(A(3n,x)) + (3n+1)*A(3n,x); A(3n+2,x) = (1x)*d/dx(A(3n+1,x)) + (3n+2)*A(3n+1,x); A(3n+3,x) = (xx^2)*d/dx(A(3n+2,x)) + ((3n+2)x+1)*A(3n+2,x).


EXAMPLE

T(3,1) = 4; the four permutations in the group S_3 with a single multiplicative 3descent 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 3descents.
Table starts
n\k..0....1....2

1....1
2....2
3....2....4
4...12...12
5...72...48
6...72..456..192


MATHEMATICA

T[n_?Positive, k_] /; 0 <= k <= Floor[n/3] := T[n, k] = Switch[Mod[n, 3], 12, (k+1)T[n1, k+1] + (nk)T[n1, k], 0, (k+1)T[n1, k] + (nk)T[n1, k1]];
T[1, 0] = 1; T[_, _] = 0;
Table[T[n, k], {n, 1, 12}, {k, 0, Floor[n/3]}] // Flatten (* JeanFrançois Alcover, Nov 12 2019 *)


CROSSREFS

Cf. A000142 (row sums), A008292, A134434, A136717.
Sequence in context: A285944 A112473 A134435 * A112362 A134720 A019225
Adjacent sequences: A136715 A136716 A136717 * A136719 A136720 A136721


KEYWORD

easy,nonn,tabf


AUTHOR

Peter Bala, Jan 23 2008


EXTENSIONS

Keyword corrected by Peter Bala, Oct 30 2008


STATUS

approved



