Number of Ways to arrange things

Question

Please help me with this question because i just don't understand it.

A panel is conducting an interview on six candidates of different heights. If they are to put them in line, in how many ways can they arrange them in line such that no three consecutive candidates are in increasing order of height from front to back?

Answer 1

Use inclusion/exclusion principle.

---

If you mean "exact increasing order":

• Include the total number of arrangements, which is $6!=720$
• Exclude the number of arrangements containing "123", which is $4\cdot3!=24$
• Exclude the number of arrangements containing "234", which is $4\cdot3!=24$
• Exclude the number of arrangements containing "345", which is $4\cdot3!=24$
• Exclude the number of arrangements containing "456", which is $4\cdot3!=24$
• Include the number of arrangements containing "1234", which is $3\cdot2!=6$
• Include the number of arrangements containing "2345", which is $3\cdot2!=6$
• Include the number of arrangements containing "3456", which is $3\cdot2!=6$
• Exclude the number of arrangements containing "12345", which is $2\cdot1!=2$
• Exclude the number of arrangements containing "23456", which is $2\cdot1!=2$
• Include the number of arrangements containing "123456", which is $1\cdot0!=1$

The total amount is therefore $720-24-24-24-24+6+6+6-2-2+1=639$.

---

If you mean "any increasing order":

• Include the total number of arrangements, which is $6!=720$
• Exclude the number of arrangements containing a sequence of at least $\color\red3$ candidates in increasing order, which is $\binom{6}{\color\red3}\cdot(6-\color\red3+1)\cdot(6-\color\red3)!=480$
• Include the number of arrangements containing a sequence of at least $\color\red4$ candidates in increasing order, which is $\binom{6}{\color\red4}\cdot(6-\color\red4+1)\cdot(6-\color\red4)!=90$
• Exclude the number of arrangements containing a sequence of at least $\color\red5$ candidates in increasing order, which is $\binom{6}{\color\red5}\cdot(6-\color\red5+1)\cdot(6-\color\red5)!=12$
• Include the number of arrangements containing a sequence of at least $\color\red6$ candidates in increasing order, which is $\binom{6}{\color\red6}\cdot(6-\color\red6+1)\cdot(6-\color\red6)!=1$

The total amount is therefore $720-480+90-12+1=319$.