A304429 Triangle read by rows: T(n,k) (for 0 <= k <= floor(n/2)) is the number of permutations of length n that have k descents and avoid the patterns 321 and 2341.

1, 1, 1, 1, 1, 4, 1, 10, 2, 1, 20, 13, 1, 35, 49, 4, 1, 56, 140, 36, 1, 84, 336, 181, 8, 1, 120, 714, 670, 92, 1, 165, 1386, 2035, 578, 16, 1, 220, 2508, 5368, 2625, 224, 1, 286, 4290, 12727, 9633, 1688, 32, 1, 364, 7007, 27742, 30303, 9080, 528, 1, 455, 11011, 56485, 84721, 39041, 4640, 64

Offset

0,6

Links

Table of n, a(n) for n=0..63.

Formula

T(n, k) = Sum_{j=0..n-2k} (-1)^(n-j)*2^(3k-n+j-1)*binomial(3k+j, 3k)*binomial(k-1, n-2k-j) for k > 0.

G.f.: Sum_{n>=0} Sum_{k=0..floor(n/2)} T(n, k)*x^n*y^k = ((1-x)^2-x^2*y)/((1-x)^3-x^2(2-x)*y).

Example

For n = 4 and k = 2, the T(4,2) = 2 permutations are 2143 and 3142.
Triangle T(n,k) begins:
  1;
  1;
  1,   1;
  1,   4;
  1,  10,    2;
  1,  20,   13;
  1,  35,   49,    4;
  1,  56,  140,   36;
  1,  84,  336,  181,   8;
  1, 120,  714,  670,  92;
  1, 165, 1386, 2035, 578, 16;

Mathematica

T[n_, k_] :=
  If[k == 0, 1,
   Sum[(-1)^(n - j)*2^(3 k - n + j - 1)*Binomial[j + 3 k, 3 k]*
     Binomial[k - 1, n - 2 k - j], {j, 0, n - 2 k}]];
Flatten[Table[Table[T[n, k], {k, 0, Floor[n/2]}], {n, 0, 14}]]

Crossrefs

Row sums give A001519.

Sequence in context: A138775 A209385 A121529 * A347115 A006370 A262370

Adjacent sequences: A304426 A304427 A304428 * A304430 A304431 A304432

Keyword

nonn,tabf

Author

Colin Defant, May 12 2018

Status

approved