OT: Math help. Permutations and Combinations

[geoschmo]

Here's the question in my math homework this week.

A shelf holds 12 books in a row. How many ways are there to choose 5 books so that no two adjacent books are chosen? [Hint: Represent the books that are chosen by bars and the books that are not chosen by stars. Count the number of sequences of five bars and seven stars so that no two bars are adjacent.]

I could not figure out how to present this in one of the formulae we studied in this chapter. The hint was no help to me at all. I did a brute force method approach and counted the possible combinations.

Since the selections must be non-consecutive the longest we can wait to pick our first selection is book 4 and every other book after gives us:
4,6,8,10,12
Now working backwards on the shelf if our first book selected is 3 we get:
3,5,7,9,11
We can pick the same first four and choose 12 for our last books instead of 11 giving us:
3,5,7,9,12
With 3,5, and 7 picked we can also take 10 and 12 giving us:
3,5,7,10,12
With 3, and 5 we can take 8 as our third book giving us:
3,5,8,10,12
And our final pick with 3 as the first choice is:
3,6,8,10,12

Following an identical process and working through all the other options and tabulating the totals I came up with the following:
1 sequence with 4 as the first book selected
5 sequences with 3 as the first book selected
15 sequences with 2 as the first book selected
35 sequences with 1 as the first book selected
Total = 56 sequences

Is there a more elegant way to approach this problem? If we were talking about a shelf with 100 books and choosing 25 my solution would not be very practical.

A guy in my study group came up with C(8,3) which by formula is 8!/(3!5!) which does equal 56, so I suspect he's got the correct idea. I just can't see how he jumped to the formula from the given information since he didn't show any of his work. I've asked him to explain his process, but it's an online class and and I don't know how long it will take him to respond.

Anyone care to give me some help? Anyone, anyone? Buehler?

[Suicide Junkie]

What if you think of it in terms of the required block of 8 alternating... then choosing spots for the four remaining unchosen books?

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

[capnq]

narf poit chez BOOM said: I'm not sure whether to laugh maniacally or run...

Why not do both?