Combinatorics problem

Nov 2010
61
0
Problem: 15 books should be divided between two bookshelves, each shelf should at least have one book.
In how many ways could this be done?

I think I've solved the problem, but It's an ugly solution based on brute force observation and not really comprehension.
So I realized that if you take combinations of 1 book out of 15 and sum them with combinations of 2 out of 15 ... and so on until 14 out of 15, you will probably solve this problem. I tried and got 32766 combination by doing:

(15 over 1)+(15 over 2)+(15 over 3) +...+ (15 over 14) = 32766

This feels really dirty and there should be a much more elegant way of solving this and similar kind of problems.
 

romsek

MHF Helper
Nov 2013
6,838
3,079
California
Think of each book as a binary digit.

It's value is the shelf it gets assigned to.

There are 2 shelves, 15 books, i.e. a 15 bit binary number, so $2^{15}$ possible arrangements.

But there are two invalid arrangements. One with all books on shelf 1, and one with all books on shelf 2.

So there are $2^{15}-2 = 32766$ possible arrangements.

Your method is perfectly valid and there's nothing cheesy about it. Just remember that

$\displaystyle{\sum_{k=0}^n}\begin{pmatrix}n \\ k \end{pmatrix} = 2^n$
 
  • Like
Reactions: 1 person
Nov 2010
61
0
Oh that explains a lot, thank you very much!
 
Mar 2017
18
0
San Marino
I didn't want to start a new thread, so I'll use this one, I hope someone out there can help me out! I've been stuck with this:

How many paths on a 8x8 chess board can a rook take from square A1 to square H8 if it can only move one square at a time?