Calculate the number of ways to sort the numbers $1,2,...,n$ with $n\ge 4$ with the condition:

Question

Calculate the number of ways to sort the numbers $1,2,...,n$ with $n\ge 4$ with the condition:

$i)\space1$ goes before $2$, and $3$ goes before $4$

$ii)\space1$ goes before $2$ and $3$, and $3$ goes before $4$

So for solving $i)$ I tried writing the solutions for $n=4$ and I got out of the possible $24$ permutations only $6$ are working which are:

$1,2,3,4.$

$1,3,2,4.$

$1,3,4,2.$

$3,4,1,2.$

$3,1,4,2.$

$3,1,2,4.$

Now, if I have a bigger n, for example just $n=5$ I noticed that the 5 will only be able to go in 5 positions for each combination. For example in the $1,2,3,4:$

$*1*2*3*4* $ the 5 can just go in the $*$.

Therefore I figured that the formula for an n would be: $$6{n\choose4}$$ where $n$ is the total number of numbers in the set. For $ii)$ following the same method I got:

$$2{n\choose4}$$

Is this correct?

Answer 1

i) $$\frac{n!}{4}$$ There are only six possibilities of $S_4 = 4!$ to place the first $4$ numbers. $$ n! \frac{6}{4!} = n! \frac{6}{24} = \frac{n!}{4}$$

ii) $$\frac{n!}{8}$$ There are only three possibilities of $S_4 = 4!$ to place the first $4$ numbers. $$ n! \frac{3}{4!} = n! \frac{3}{24} = \frac{n!}{8}$$

Answer 2

I don't think so.

the answer might be $(n!/4!)\cdot6$

which doesn't equal to what you said. I guess your approach is correct but you mistakenly thought

$n!/4!=$$n\choose4$

and it's easy to get consfuse if you put values like for n=4 and 5 it will work ,try for n=6.

Answer 3

Calculate the number of ways to sort the numbers $1, 2, 3, \ldots, n$ with $n \geq 4$ if $1$ goes before $2$, and $3$ goes before $4$.

There are $n!$ arrangements of the first $n$ positive integers. By symmetry, in half of these arrangements, $1$ appears before $2$. By symmetry, in half of these arrangements, $3$ appears before $4$. Hence, the number of arrangements in which $1$ appears before $2$, and $3$ appears before $4$ is $$\frac{1}{2} \cdot \frac{1}{2} \cdot n! = \frac{1}{4}n!$$

Another way to see this is to choose two of the $n$ positions for the $1$ and $2$. There is only one way to arrange the $1$ and $2$ in these positions so that $1$ appears before $2$. Choose two of the $n - 2$ remaining positions for the $3$ and $4$. There is only one way to arrange the $3$ and $4$ in these two positions so that $3$ appears before $4$. Arrange the remaining $n - 4$ positive integers in the remaining $n - 4$ positions. We can do this in $$\binom{n}{2}\binom{n - 2}{2}(n - 4)! = \frac{n!}{2!(n - 2)!} \cdot \frac{(n - 2)!}{2!(n - 4)!} \cdot (n - 4)! = \frac{n!}{2!2!} = \frac{n!}{4}$$ ways.

Calculate the number of ways to sort the numbers $1, 2, 3, \ldots, n$ with $n \geq 4$ if $1$ goes before $2$ and $3$, and $3$ goes before $4$.

Of the four numbers $1$, $2$, $3$, and $4$, $1$ must appear first. By symmetry, this occurs in one fourth of the arrangements. We also require that $3$ appears before $4$, which occurs in half of the arrangements. Hence, the number of arrangements in which $1$ goes before $2$ and $3$, and $3$ goes before $4$ is $$\frac{1}{2} \cdot \frac{1}{4} \cdot n! = \frac{n!}{8}$$

Another way to see this is to choose four positions for the $1$, $2$, $3$, and $4$. We must place $1$ in the first of these positions. Choose one of the remaining three of these positions for the $2$. There is only one way to arrange the $3$ and $4$ in the remaining two of these positions so that $3$ appears before $4$. Arrange the remaining $n - 4$ numbers in the remaining $n - 4$ positions. This can be done in $$\binom{n}{4}\binom{3}{1}(n - 4)! = \frac{n!}{4!(n - 4)!} \cdot \frac{3!}{1!2!} \cdot (n - 4)! = \frac{n!3!}{4!2!} = \frac{n!}{4 \cdot 2!} = \frac{n!}{8}$$