1
$\begingroup$

This combinatorics problem arose from a question in physics: when excited from the 1st to the nth energy level, how many ways are there of making the path back to the 1st, allowing any combination of downwards jumps.

After enumeration, it seemed that it should be the sum of the $(n-1)th$ row in Pascal's triangle (that is, $\sum_{k=0}^{n-1}\binom{n-1}{k}$).

How do I prove this, and what is wrong with the below attempted proof?:

Represent the spaces between energy levels by ($n-1$) dots , and the energy level(s) that the electron rests on by a |. The number of these energy levels =k.

So for n=4 the possibilities are (k=0) ... , (k=1) .|.. , ..|. and (k=2) .|.|.

Note that $k \le n-2 $.

So for $k=k$ there are $\large \frac{((n-1)+k)!}{(n-1)!k!}=\binom{n-1+k}{k}$

So $ Possibilities = \sum_{k=0}^{n-2} \frac{((n-1)+k)!}{(n-1)!k!} =\sum_{k=0}^{n-2} \binom{n-1+k}{k}$. Which is irritatingly similar to the earlier formula, but evidently something's gone wrong in the proof.

1 Answers 1

3

The stops along the way from level $n$ to level $1$ can be any subset of $\{2,3,\ldots,n-1\}$, therefore there are $2^{n-2}$ ways.