OT: Math help. Permutations and Combinations

[Will]

Another way to think of it (and this is probably how the guy in your study group got C(8,3)):

You have twelve books in a row, and are choosing five. To find the combinations, change the problem slightly to having a row of seven books, and inserting another five such that none of the inserted books are adjacent. Find the number of ways you can insert the books.

I will use the problem's analogy of bars and stars, except I'll be using $ instead of * to avoid confusion with multiplication:

$ $ $ $ $ $ $

Now, you have five bars to insert into this sequence somehow. There are a total of eight slots to possibly add a bar to:

1 $ 2 $ 3 $ 4 $ 5 $ 6 $ 7 $ 8

To insert the first bar, you have 5 bars to choose from to insert into 8 slots. For the second bar, you have 4 bars to choose from to insert into 7 slots... and for the nth bar, you have (5-n) bars to choose from to insert into (8-n) slots. This gives you:

(8*7*6*5*4) / (5*4*3*2*1)

You can multiply this by 1 = 3!/3! to get:

8! / (5! * 3!) = C(8,3)

For the general solution of fitting X bars into a sequence of Y stars, such that no two bars are adjacent, you then have:

(Y+1)*Y* ... *(Y-X+2) / X!

Which you can then multiply by 1 = (Y-X+1)!/(Y-X+1)! to get:

(Y+1)! / X! * (Y-X+1)! = C(Y+1, Y-X+1)

Plugging in the values of 7 stars for Y and 5 bars for X, it is easy to see that we get C(8,3), just like we should.