Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.