$312$-avoiding and $213$-avoiding

I have to describe the permutations which are both $312$-avoiding and $213$-avoiding, and then count how many there are of length $n$. So I found that when $n<4$ that the there are clearly no permutations which have both $213$ and $312$ patterns.

My problem is that this is not simply counting the permutations with $312$ and $213$ encoded into them. Because you can have something like $2413$ which has a subsequence $213$ and another subsequence $413$ which corresponds to the pattern $312$. I think it is possible to describe one type of permutation for any $n$ that avoids both but how is it possible to describe them all?

• Are you sure that no perm of length less than 4 is both 312- and 213- avoiding? 123, 132, 231 and 321 avoid both. – Parcly Taxel Dec 10 '17 at 7:04
• Sorry I meant we don't have to worry about a perm that has both 312 and 213 patterns at that length, because it's not possible – Boots Dec 10 '17 at 7:07

In the permutation, 1 cannot go anywhere but the ends, since if it was in the middle it would be surrounded by two distinct and greater elements, thereby forming a 213 or 312 pattern. Similar reasoning then applies for elements 2, 3 and so on with the remaining space of the permutation.

For each element except the last, 2 choices are possible; the number of 213- and 312-avoiding permutations on $n$ elements is thus $2^{n-1}$.

• Just to solidify your example here, where are the possible placements for 2? The 2nd spot or the 2nd to last spot? – Boots Dec 10 '17 at 7:12
• @Boots Regardless of which end 1 gets placed in, there remains a single row of $n-1$ spaces. Then 2 can go only at the ends of this row. – Parcly Taxel Dec 10 '17 at 7:14
• Ah so then when we are placing 3 there is a row of $n-2$ spaces, and 3 gets placed there, etc. – Boots Dec 10 '17 at 7:15
• @Boots Yes. And the last, greatest element is forced into the one space at the end. – Parcly Taxel Dec 10 '17 at 7:16
• Very cool, thank you so much! – Boots Dec 10 '17 at 7:16

Consider a permutation which is both $213$- and $312$-avoiding. Where can $1$ go? Clearly not anywhere in the middle: only in the first and last place. So (for $n\ge2$) you have two choices. Apart from the $1$ what is left? A both $213$- and $312$-avoiding permutation of $2,3,\ldots,n$....

• So we're going to break down each number and figure out where it can go? – Boots Dec 10 '17 at 7:11
• @Boots Or we could observe the number of admissible permutations on $n$ numbers is twice that for $n-1$ numbers. – Lord Shark the Unknown Dec 10 '17 at 8:03