1

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?

Asaf Karagila
  • 393,674
Mapoz
  • 9
  • 1
  • First, you should show some kind of effort. But let me give you a starting push- since all of the candidates have different height, we can enumerate them $1, 2, 3, 4, 5,$ and $6$ from shortest to tallest. So we want to count all arrangementa $abcdef$ where each letter represents a place for a candidate such that for any three consecutive letters, say $xyz$, we do not have $x<y<z$. – Kevin Long Oct 05 '16 at 17:24

1 Answers1

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$.

barak manos
  • 43,109