Block houses
Each student gets n cubic inch blocks (n = 10 is a reasonable number). To build a "house" you put down a row of blocks and then build up. One block must be put exactly on top of a block below (no overlap is allowed).
Here is an example of a line of eight different houses built from 6 blocks.
Notice that the fourth and fifth houses are considered different even if they can be viewed as the same building seen from the front and from the rear.
Two questions.
How many different houses can one build using exactly n blocks? How many houses built from n blocks are k blocks wide?
Solutions.
A house built from n blocks that is k blocks wide can be viewed as being built from k towers, each tower being one block wide. If these towers have heights h1, h2, ..., hk, then we have h1 + h2 + ... + hk = n. So the number of different houses of width k is the same as the number of ways the whole number n can be presented as a sum of k positive whole numbers.
This is the same as the number of ways a stick of n cubes can be cut into k shorter sticks (the cubes cannot be broken). In order to do, so we need to choose k out of n-1 possible cut points. So the number of ways of doing it is (n - 1) choose (k - 1), or
To build any house made of n blocks, we need to choose any number of cut points from 0, for building a one-floor house, to n-1, for building a tower. So the number of ways of doing it is
2n-1.
So, for example, from 10 blocks we can build a house in 29 = 512 different ways, and 9 choose 2 = 36 of them would be 3 blocks wide.
Here are the 8 towers made from 4 blocks (23), and 3 of them (3 choose 2) are two blocks wide:
