|
| |
|
|
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; 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 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.
|
|
|
LINKS
| S. Kitaev and J. Remmel, Classifying descents according to equivalence mod k.
|
|
|
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).
|
|
|
EXAMPLE
| 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
|
|
|
CROSSREFS
| Cf. A000142 (row sums), A008292, A134434, A136717.
Sequence in context: A059343 A112473 A134435 * A112362 A134720 A019225
Adjacent sequences: A136715 A136716 A136717 * A136719 A136720 A136721
|
|
|
KEYWORD
| easy,nonn,tabf
|
|
|
AUTHOR
| Peter Bala (pbala(AT)toucansurf.com), Jan 23 2008
|
|
|
EXTENSIONS
| Corrected keyword. - Peter Bala (pbala(AT)toucansurf.com), Oct 30 2008
|
| |
|
|
