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

 

Logo

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

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

License Agreements, Terms of Use, Privacy Policy. .

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