OT: Math help. Permutations and Combinations

[douglas]

Five bars, seven stars, no two bars can be adjacent. The adjacency requirement is equivalent to every bar must have either a star or nothing to its left. Let's introduce a new term, foo, that is a star on the left and a bar on the right. If the leftmost book is a bar, then you have four foos and three stars to arrange, which is a simple problem of C(7, 3). Otherwise, there are five foos and two stars, with C(7, 2) combinations. The solution is the sum of these.

C(7,3) + C(7,2)
7!/(4!*3!) + 7!/(5!*2!)
7*6*5/(3*2) + 7*6/2
7*5 + 7*3
35 + 21 = 56

For the problem of picking 25 non-adjacent books from 100, it would be C(75, 51) + C(75, 50) = 78367246720143449328.

More generally, picking A non-adjacent books from B total is: C(B-A, B-2A+1) + C(B-A, B-2A). Incidentally, this is the same as C(B-A+1, B-2A+1) though I don't feel like going through the proof of that. I just remembered that the two combinations added together above are adjacent numbers in Pascal's Triangle, and their sum is the number right below them, which is given by the other combination.

[capnq]

Stuff like this is why I failed three different probability and statistics courses in college.

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

[narf poit chez BOOM]

What's that '!' ?

[Suicide Junkie]

! = factorial.

For nice positive integers, you start with the number, and multiply it by all the numbers below it until you get to 1.

5! = 5x4x3x2x1 = 120

It gets uglier when you throw in negatives, or fractional numbers.

[Cipher7071]

I vote for the "foos."

[narf poit chez BOOM]

Why? Do you pity the foo?

Oh man...I'm not sure whether to laugh maniacally or run...