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.