7
$\begingroup$

Find all permutations of numbers from $1$ to $6$, where $5$ is always before $1$.

I'm trying to help my son with his homework, and I'm out of my depth :(

As the question states, it looks to me that I can concentrate on $5$ and $1$. So, it will look like this:

[5,1,X,X,X,X] => 4!
[5,X,1,X,X,X] => 4!
[5,X,X,1,X,X] => 4!
[5,X,X,X,1,X] => 4!
[5,X,X,X,X,1] => 4!

[X,5,1,X,X,X] => 4!
[X,5,X,1,X,X] => 4!
[X,5,X,X,1,X] => 4!
[X,5,X,X,X,1] => 4!

[X,X,5,1,X,X] => 4!
[X,X,5,X,1,X] => 4!
[X,X,5,X,X,1] => 4!

[X,X,X,5,1,X] => 4!
[X,X,X,5,X,1] => 4!

[X,X,X,X,5,1] => 4!

so we end up with $4! \cdot 15$.

Is this correct?

This is just me counting on my fingers ;), What would be the "Combinatorial" way of thinking and solving this kind of questions?

Thank you.

$\endgroup$
1
  • 7
    $\begingroup$ Hint: exactly half of the permutations have $5$ before $1$, by symmetry. $\endgroup$
    – lulu
    Feb 29 '20 at 15:28
14
$\begingroup$

Your approach is correct, but somewhat case-mongery. Observe that once you chose two places to put the $1$ and the $5$, there's only one way to arrange it so that $1$ is after $5$ (e.g. if you decided that $1$ and $5$ should be at 3rd and 4th spot, $1$ should be at 4th spot, and 5 at 3rd spot). So it's $\binom{6}{2}=15$ for the number of places to put $1$ and $5$, and $4!$ arrangements of the remaining numbers, giving you the final answer of $\binom{6}{2} \times 4!$.

Taking a somewhat different approach, you can convince yourself that there are equal number of arrangements where $5$ is after $1$ as the arrangements where $1$ is after $5$. Why? Because you can pair an arrangement where $5$ is after $1$ to the one where $1$ and $5$ is flipped (e.g. $[1,X,X,5,X,X] \leftrightarrow [5,X,X,1,X,X]$).

Since every arrangement has either $1$ after $5$ or a $5$ after $1$, you get $\frac{6!}{2}$ total arrangements.

$\endgroup$
1
4
$\begingroup$

We can think of the problems in two subsets. Cases where the 5 comes before the 1, and cases where the 1 comes before the 5. Since we can compliment each case with another case by flipping the 5 and the 1 (for example: 652134 can be complimented with 612534). Then the compliments have a 1:1 correspondence and the total number of ways of ordering the numbers is 6!, so the answer will be 6!/2 or 360.

$\endgroup$
1
  • $\begingroup$ "compliment" ≠ "complement". And neither word is what you want. You want "put in correspondence with". $\endgroup$
    – user21820
    Mar 1 '20 at 2:47
1
$\begingroup$

Yes, this is correct. There are $\binom{6}{2}=15$ choices for 5 and 1, and then $4!$ ways to permute the rest. Equivalently, there is a one-to-one correspondence between permutations that have 5 before 1 and those that have 1 before 5, so there are $6!/2$ of each.

$\endgroup$
0
1
$\begingroup$

Yes, it is correct because just think $ 5 \ \& \ 1 $ have fixed positions and thus total number of arrangements would be

$$ \displaystyle \frac {6!}{2!} = 360 $$

This is because there will be $ 2! $ arrangements of $ 5 \ \& \ 1 $ and only one of them is correct, so just divide the total number of arrangements of numbers $ 1 \ to \ 6 $ i.e ( $ 6! $ ) by $ 2! $.

$\endgroup$
2
  • $\begingroup$ Nicola, thank you very much. reading all the answers helps me to build the correct mental model on how to approach those kind of questions. $\endgroup$
    – Nafas
    Feb 29 '20 at 18:38
  • $\begingroup$ You're welcome. $\endgroup$ Feb 29 '20 at 18:43
1
$\begingroup$

(basic) ways to do this that give the same answers.

1) Symmetry: Line up all the permutations with $5$ before the $1$ along the east wall of the gym, and line up all the permutations with $1$ before the $5$ along the west wall of the gym. Tell all the permutations along the east wall to find a partner along the west wall where there $2,3,4,6$ are all in the exact same position but the $5$s and $1$s are in opposite positions.

Convince yourself that all the permutations will have exactly one partner and no permutations will be left out.

Therefor it seems, it must be that the number of permutations with the $5$ before the $1$ is exatly the same as then number of permutation with the $1$ before the five and that number is exactly half the number of permutations, namely $\frac {6!}2$.

2) Choice 1: Dress the $5$ and $1$s in matching burkas. Have them find two places to occupy and occupy them. There we ${6\choose 2}$ ways to do that. Have them remove their burkas and if the $1$ is before the $5$ have them switch places. Have the rest of numbers find their spots. That ${6\choose 2}4!$.

3) Choice 2: Have the numbers $2,3,4,6$ choose their spots first. There are $6*5*4*3 = \frac {6!}{2!}$ ways to do that. The $5$ must choose the first available spot and the $1$ must choose the last.

.....

Extra Credit: Why does the following not work?

Z) Take a needle and thread and sew $1$ and $5$ and call it a new number "wive" or "fun". You now have $5$ numbers. Have them choose five spots. There are $6*5*4*3*2 = 6!$ ways to do that. Cut "wive" or "fun" in two. Have the appropriate one of them move to the remaining spot. So there are $6!$ ways to do it.

It's subtle but important to see why that way doesn't work.

Hint: Think what happens when "fun" is the last number to choose and has two choices. What happens if they (literally a they) make one choice and what happens when they make the other.

Hint: Think what happens if "wive" is the second to last to choose and she has three choices A,B,C and as they are thinking the last number says "please don't choose C; it's my favorite". And "wive" thinks about their two options A or B or whether they will pick C for spite and mulls the options....

$\endgroup$
1
  • $\begingroup$ Thank you for your elaborate answer, helped me a lot to understand how to think $\endgroup$
    – Nafas
    Feb 29 '20 at 18:38

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.