The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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, arXiv:math/0604455 [math.CO], 2006. 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 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 *) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 9 07:53 EST 2021. Contains 349627 sequences. (Running on oeis4.)