Number of permutations where $621$ and $231$ are subsequences

70 Views Asked by At

Given $S_6$, I want to find how many elements contain $621$ or $231$ as subsequences, meaning that the numbers come one after another in the permutation. For example $632541$ is a valid permutation, but $615432$ is not.

I proved that there are 120 permutations, where one of both holds and found computationally that the number for the intersection is 30, but I can't prove it.

1

There are 1 best solutions below

8
On BEST ANSWER

The number of permutations in $S_6$ which contain $621$ as a subsequence is $\binom{6}{3}\cdot 3!=120$. The same for $231$. In the intersection we find the permutations which contain $6231$ as a subsequence and their number is $\binom{6}{4}\cdot 2!=30$. Therefore the answer is $120+120-30=210$.