OT: Math help. Permutations and Combinations
 

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

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? http://forum.shrapnelgames.com/images/smilies/happy.gif

Re: OT: Math help. Permutations and Combinations
 

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

Re: OT: Math help. Permutations and Combinations
 

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.

Re: OT: Math help. Permutations and Combinations
 

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

Re: OT: Math help. Permutations and Combinations
 

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.

Re: OT: Math help. Permutations and Combinations
 

What's that '!' ?

Re: OT: Math help. Permutations and Combinations
 

! = 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.

Re: OT: Math help. Permutations and Combinations
 

I vote for the "foos."

Re: OT: Math help. Permutations and Combinations
 

Why? Do you pity the foo?

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

Re: OT: Math help. Permutations and Combinations
 

Why not do both?