|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
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
|
| |
|
|
