Number of permutations of $1,2,3,4,5,6,7,8,9$ taken all at a time for the following constraints.

Question

Number of permutations of $1,2,3,4,5,6,7,8,9$ taken all at a time are such that

$1$ appearing somewhere to the left of $2$

$3$ appearing to the left of $4$

$5$ somewhere to the left of $6$, is (e.g. $815723946$ would be one such permutation)

My attempt is as follows:-

Let's say we select 6 positions for $\{1,2,3,4,5,6\}={9\choose 6}=84$

Now we have to figure out the no of ways in which we can place $1,2,3,4,5,6$ per position. Let's see how we can do it.

Let's assume $1$ and $2$ are already placed where $1$ is to the left of $2$. These two numbers will leave $3$ gaps.

Now let's try to place $3$ and $4$, they can be placed in $(3+2+1)=6$ possible ways.

$$3412,3142,3124,1342,1324,1234$$

Now let's try to place $5$ and $6$. Four numbers which have been placed till now will leave $5$ gaps, so $5$ and $6$ can be placed in $(5+4+3+2+1)=15$ ways.

So in total there will be $6\cdot 15=90$ ways to place $\{1,2,3,4,5,6\}$ per position for the given constraints.

So there are total $84\cdot 90=7560$ arrangements in which we can place $\{1,2,3,4,5,6\}$

Now for each such arrangement, we can place remaining numbers $\{7,8,9\}$ in $3!$ ways in $3$ leftover positions.

So there will be total $7560\cdot 6=45360$ ways to place $\{1,2,3,4,5,6,7,8,9\}$ for the given constraints.

Is there any better way to do this, my approach got too long?

Answer 1

I would solve this in the following way:

The question has been changed, so here is the new result:

We have $9!$ permutations in total. In half of the permutations $1$ is to the right of $2$ leaving us with $\frac{9!}{2}$. In half of the remaining permutations $3$ is to the right of $4$ leaving us with $\frac{9!}{4}$. In half of the remaining permutations $5$ is to the right of $6$ leaving us with $\frac{9!}{8}$.

Answer 2

You can choose the positions for the 1,2 pair (their relative order is set). And then choose two of the remaining 7 positions for the 3,4 pair. Then the 5,6 pair. Then order the rest:

$${9\choose 2} * {7 \choose 2} * { 5 \choose 2} * 3!$$

Answer 3

This answers the corrected question that considers $3$ to the left of $4$.

For each permutation, it is equally likely that $1$ is to the left of $2$ and that $1$ is to the right of $2$. The same holds for $3$ and $4$, and for $5$ and $6$.

By swapping positions of each pair, each permutation belongs to an equivalence class of exactly $8$ permutations, and each class contains exactly one permutation which satisfies the requirements.

The answer is hence simply $9!/8$.

---

Notice that $8=2^3$. In general, for $k$ pairs with no intersecting elements, we'd have $2^k$.