I've found this enigma in a french book and I've tried using combinatorics to find the answer but I've been unsuccessful, could you help me out?
Here's what's given: "A child wants to build "houses" using identical cubes. For him, making a house is just building the front wall, by juxtaposing "towers" of 1,2,3... floors, i.e. columns that are only limited in height by the number of cubes available. Thus, with 3 cubes, he can build 4 different "houses". And with 4 cubes? Without building them all, can you find out how many houses he can build with 10 cubes?"
Here's a link to the original problem with a helpful image so you can visualize the problem: The french puzzle
The comment by sku already gives an answer: given $n$ cubes, each house corresponds to an ordered partitioning of $n$, ie $n_1+\cdots+n_k=n$ where the $n_i$ are ordered and positive. So $3$ can be partitioned in 4 different ways: $3$, $2+1$, $1+2$, and $1+1+1$.
There are several ways to derive the number of ordered partitions for general $n$. However, here's a particularly simple one which nicely translates to building the house.
Start by placing a single cube. For each subsequent cube, either stack it on top of the last one building the tower taller, or place it to the left starting a new tower. Ie, for each cube except the first, you have two choices. Every house can be built in this way, and every sequence of choices gives rise to a different house.
Hence, there are $2^{n-1}$ different houses that can be built from $n$ cubes.
Actually, the above was not my original way to solve this. To intrigue those not familiar with generating functions, here is my initial approach:
A house consists of a sequence of towers, each tower consisting of 1 or more cubes. The number of towers with $n\ge1$ cubes is 1, and we can represent this by a power series: $$ T(x) = \sum_{n=0}^\infty \#(\text{towers with $n$ cubes})\cdot x^n = x + x^2 + x^3 + \cdots = \frac{x}{1-x}. $$ Note that for $n=0$, the coefficient will be zero.
If we do the same with $k$ towers, we get $$ \sum_{n=0}^\infty \#(\text{$k$ tower houses with $n$ cubes in total}) \cdot x^n = T(x)^k $$ and we sum this for $k=1,2,\ldots$ towers to count all possible houses, we get $$ \sum_{n=0}^\infty \#(\text{houses with $n$ cubes}) \cdot x^n = \sum_{k=1}^\infty T(x)^k = \frac{T(x)}{1-T(x)} = \frac{x}{1-2x} = \sum_{n=1}^\infty 2^{n-1}x^n $$ from which we can read the number of houses with $n$ cubes as $2^{n-1}$. Seeing this, I realised there had to be a simpler proof.