A299927 Number of permutations of length n that avoid the patterns 213 and 312 and have k double ascents, read by rows.

1, 1, 2, 3, 1, 4, 3, 1, 5, 6, 4, 1, 6, 10, 10, 5, 1, 7, 15, 20, 15, 6, 1, 8, 21, 35, 35, 21, 7, 1, 9, 28, 56, 70, 56, 28, 8, 1, 10, 36, 84, 126, 126, 84, 36, 9, 1, 11, 45, 120, 210, 252, 210, 120, 45, 10, 1, 12, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1

Offset

0,3

Comments

In a permutation avoiding 213 and 312, all digits before n are increasing and all digits after n are decreasing. If k=0, either n is the first digit or the second digit of the permutation. If k >= 1, there are binomial(n-1, k+1) ways to choose k+1 digits before n; these digits together with n account for k double ascents.

For n >= 1, the sum of row n is 2^(n-1).

Links

Michael De Vlieger, Table of n, a(n) for n = 0..11176 (rows 0 <= n <= 150, flattened).

M. Bukata, R. Kulwicki, N. Lewandowski, L. Pudwell, J. Roth, and T. Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv preprint arXiv:1812.07112 [math.CO], 2018.

Paul M. Rakotomamonjy, Sandrataniaina R. Andriantsoa, Arthur Randrianarivony, Crossings over permutations avoiding some pairs of three length-patterns, arXiv:1910.13809 [math.CO], 2019.

Formula

If k=0 and n>0, a(n,k)=n.

If k >= 1, a(n,k) = binomial(n-1,k+1).

Example

a(5,0)=5.  This counts the permutations 15432, 25431, 35421, 45321, and 54321.
a(5,1)=6.  This counts the permutations 12543, 13542, 14532, 23541, 24531, and 34521.
Triangle begins:
   1;
   1;
   2;
   3,  1;
   4,  3,   1;
   5,  6,   4,   1;
   6, 10,  10,   5,   1;
   7, 15,  20,  15,   6,   1;
   8, 21,  35,  35,  21,   7,   1;
   9, 28,  56,  70,  56,  28,   8,   1;
  10, 36,  84, 126, 126,  84,  36,   9,  1;
  11, 45, 120, 210, 252, 210, 120,  45, 10,  1;
  12, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1;

Maple

f:= proc(n, k)
if n = 0 and k = 0 then return 1:
elif k = 0 then return n:
else return binomial(n-1, k+1):
fi: end:
f(0, 0), f(1, 0), seq(seq(f(i, j), j = 0 .. i-2), i = 2 .. 12)

Mathematica

Table[Which[And[n > 0, k == 0], n, k >= 1, Binomial[n - 1, k + 1], True, 1], {n, 0, 12}, {k, 0, If[n < 2, 0, n - 2]}] // Flatten (* Michael De Vlieger, Feb 07 2019 *)

Crossrefs

Sequence in context: A255054 A011857 A242360 * A006021 A002186 A125936

Adjacent sequences: A299924 A299925 A299926 * A299928 A299929 A299930

Keyword

easy,nonn,tabf

Author

Lara Pudwell, Dec 15 2018

Status

approved