Combination help please! (1 Viewer)

goobi

Member
Joined
Oct 6, 2010
Messages
196
Gender
Male
HSC
2012
In how many ways can 4 boys, including John and Matthew, and 4 girls, including Sally, be arranged in a line if Matthew is between, but not necessarily adjacent to John and Sally?

The solution in the back of the book:

"The total number of ways to sit 8 people if John, Matthew and Sally stay in alphabetical order is 8!/3!=6720. But John and Sally can swap seats. Therefore, 6720*2=13440 ways."

The problem is I don't quite understand the solution, especially the "8!/3!" bit.
Can anyone please explain that to me?
Thanks in advance! :)
 

johnpap

New Member
Joined
Aug 7, 2011
Messages
16
Gender
Male
HSC
2012
All they're really doing is finding a nice way to encode the restraint of the problem in steps:

So first given you have 8 people, and the order in which you put them in a line matters, it's clear that there are 8! arrangements possible, since you have 8 people to put first, 7 to put second and so on.

Then think about Matthew, John and Sally (M/J/S for short) - in any configuration of the people in the line, if we read left to right in the line they can fall in 6 possible configurations:
MJS, MSJ, JMS, JSM, SMJ or SJM. I.e. we just note all the possible lines each of them could form if we get rid of everyone else in whatever 8 person line they fall in.

Now think about those 6 configurations, since we wanted Matthew to be in the middle, only the orderings SMJ and SJM will work, so the total amount of lines that work is 8!/3 = 13440, since only 1/3 of the total orderings of M, J and S lead to valid lines. And it's clear that we can just divide out like this, since all the possible lines come in groups of 6 defined by just permuting S, M and J in their positions in their lines.

What they're done in the worked answer is actually to add in a step where they say - let's remove the factor that S, M and J are in some order, i.e divide 8! by 3! to say we have 8!/3! groups of lines from which we might find some valid ordering - and then noted that since for every such group 2 orderings of S, M and J work we have to multiply the number of line groups by 2 to find the total lines.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top