1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are you sure that no perm of length less than 4 is both 312- and 213- avoiding? 123, 132, 231 and 321 avoid both. $\endgroup$ – Parcly Taxel Dec 10 '17 at 7:04
  • $\begingroup$ 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 $\endgroup$ – Boots Dec 10 '17 at 7:07
2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Just to solidify your example here, where are the possible placements for 2? The 2nd spot or the 2nd to last spot? $\endgroup$ – Boots Dec 10 '17 at 7:12
  • $\begingroup$ @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. $\endgroup$ – Parcly Taxel Dec 10 '17 at 7:14
  • $\begingroup$ Ah so then when we are placing 3 there is a row of $n-2$ spaces, and 3 gets placed there, etc. $\endgroup$ – Boots Dec 10 '17 at 7:15
  • $\begingroup$ @Boots Yes. And the last, greatest element is forced into the one space at the end. $\endgroup$ – Parcly Taxel Dec 10 '17 at 7:16
  • $\begingroup$ Very cool, thank you so much! $\endgroup$ – Boots Dec 10 '17 at 7:16
1
$\begingroup$

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$....

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.