login
A299927
Number of permutations of length n that avoid the patterns 213 and 312 and have k double ascents, read by rows.
1
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
KEYWORD
easy,nonn,tabf
AUTHOR
Lara Pudwell, Dec 15 2018
STATUS
approved