Test your permutation skills! (And help me with a problem)

Test Preparation
1

<p>Heres the problem... I found a way to do it myself, but I'm not sure of the answer, and I have no way of verifying the actual answer:</p>

<p>Five people are to be seated in a row of 12 chairs, with no two sitting next to each other. How many ways can this be done, assuming the order of the people doesn't matter, only the position?</p>

<p>If you want to try yourself, don't scroll down... but for the rest of you... here's how I did it, tell me if it's stupid/wrong?</p>

<p>E=Empty, F=Filled.
Separate chairs into groups of E's next to F's: |FE|FE|FE|FE|F|
There are three empty chairs left over: E, E, E
The three empty chairs can each go where any of the six bars are: 6<em>6</em>6 = 216.</p>

<p>Yes or no?</p>

2

<p>
[quote]
tell me if it's stupid/wrong?

[/quote]

It's quite smart :cool:; unfortunately it's wrong. :(</p>

<p>A universal math advice: try playing with manageable numbers: 2 people, 6 chairs, for example. List all the good arrangements. Does your formula work?</p>

<p>Your question probably belongs to Art</a> of Problem Solving Forum.</p>

3

<p>You have a nice construction; it just needs to be improved a tad bit.</p>

<p>Imagine the chairs as a row from left to right. We split the problem into two cases:</p>

<p>(1) The last chair is empty. Using your notation, each of the five people will have an empty chair to the right of them and we have five groups of FE.</p>

<p>Therefore, if we view FE as a single unit, we only need to find combinations of FE, FE, FE, FE, FE, E, E and there are 7<em>C</em>2 of these (we choose two spaces to put empty slots and the others we fill with FE)</p>

<p>(2) The last chair is filled. Similarly, we find combinations of FE, FE, FE, FE, E, E, E which is 7<em>C</em>3.</p>

<p>Therefore, there are 21+35=56 possibilities.</p>

4

<p>I'm sorry, but I don't understand this answer. Your math sems right, if I'm understanding correctily, but... I'm trying to picture 35 ways to place 5 people in 12 chairs with none of them sitting next to each other. If all of them are sitting, I don't think it's possible. I've even taken out a peice of paper and started drawing it out. Maybe it's just my grogginess not letting me think straight... But could you explain this in simpler terms?</p>

5

<p>Okay running through the example with 6 chairs and 2 people.</p>

<p>(1) Suppose the last chair is empty. Then we can imagine four slots _ _ _ _ where we insert FE, FE, E, E. We choose two of these slots to fill in the two E's which is 4<em>C</em>2=6. For example, if we choose slots 1 and 3 we have EFEEFE And indeed there are 6 of these (note that the last slot is E)</p>

<p>FEFEEE
FEEFEE
FEEEFE
EFEFEE
EFEEFE
EEFEFE</p>

<p>(2) Say the last slot is filled. Then imagine four slots _ _ _ _ F and we have to insert FE, E, E, E into the four slots. There are 4<em>C</em>3=4 spaces we can put the E's:</p>

<p>FEEEEF
EFEEEF
EEFEEF
EEEFEF</p>

<p>So there are 10 possibilities. Hope that helps!</p>

6

<p>OK, now I understand. Thanks</p>

7

<p>Proceed only if you want to learn (or already know) Euler’s formula for combinations with repetitions.</p>

<p>Very long explanations, but they can be condensed to just a few lines.</p>

<p>1.
6 chairs, 2 people.</p>

<p>Let’s mark a filled chair V, an empty one <em>.
All possible allowed (no sitting next to each other!!) arrangements can be obtained from
V</em>V (Filled chair, Empty chair, Filled chair)
by putting any of 3 Remaining Empty Chairs (REC) into three possible places:
in front of V<em>V (place 1),
or between V and V (place 2) – in addition to the Empty chair already in that place,
or after V</em>V (place 3).
So, there are three places where REC can be dumped.</p>

<p>All three REC must be used.
If all three go in place 1, then 111 corresponds to this arrangement.
If two go in place 1 and one goes in place 2, then 112 corresponds.</p>

<p>We need to find the number of 3-digit combinations of digits 1, 2, and 3 with repetition, that is, any digit can be used more than once.
Combinations, of course, are unordered: 112 is the same as 121.</p>

<p>According to Euler the number of k-combinations with repetitions from n objects is
C(n+k-1, k).
In our case k = 3, n = 3.
C(3+3-1, 3) = C(5, 3) = 10.
There are 10 ways to seat 2 people in a row of 6 chairs, with no two sitting next to each other.</p>

<p>2.
12 chairs, 5 people.</p>

<p>V<em>V</em>V<em>V</em>V – at least one empty chair has to be between these 5 unfriendlies.
There are 3 REC: 12 – 9 = 3.
Possible places where REC can be moved:
1 V 2 V 3 V 4 V 5 V 6.
6 places altogether.
A couple of examples:
113 – two of REC in place 1, one in place 3,
666 – all three REC in place 6.</p>

<p>We are looking for 3-digit combinations of digits 1, 2, 3, 4, 5, and 6 with repetition.
k = 3, n = 6.
C(6+3-1, 3) = C(8, 3) = 56.
There are 56 ways to seat 5 people in a row of 6 chairs, with no two sitting next to each other.</p>

<p>3.
Condensed.
10 chairs, 5 people.
(5)2 – 1 = 9 Filled and separating chairs.
10 – 9 = 1 REC.
5 + 1 = 6 places to put REC.
k = 1, n = 6.
C(6+1-1, 1) = C(6, 1) = 6.
The only REC can be placed in front of the row, or to the left of it, or in any of the 4 gaps between 5 people:
1 + 1 + 4 = 6. It works!</p>

8

<p>Just to close this SAT unrelated thread.</p>

<p>Not an accidental connection with isomorphism's solution:
6 chairs, 2 people:
4<em>C</em>2 + 4<em>C</em>3 = 5<em>C</em>3</p>

<p>12 chairs, 5 people:
7<em>C</em>2 + 7<em>C</em>3 = 8<em>C</em>3</p>

<p>It's not hard to prove that
n<em>C</em>k + n<em>C</em>(k+1) = (n+1)<em>C</em>(k+1)</p>

9

<p>gcf101 is correct.</p>