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

A composition of the number $n$ with $k$ summands is the representation $$ n = a_1 + \cdots + a_k$$ with integers $a_i \geq 1, 1 \leq i \leq k$. The order of the summands is important.

Prove: There are as many compositions of n with k even summands as compositions of n-k with k odd summands exist.


I don't have any idea how to prove that as I don't know how to handle this "odd" and "even" stuff. Bijection? Induction?

Could you please help me to understand this?

Thanks in advance!

share|cite|improve this question
A bijection will do (subtract one from each $a_i$). – jspecter Jun 25 '11 at 23:32
@jspecter of course, I never thought it could be so simple, thanks! – muffel Jun 25 '11 at 23:56
up vote 3 down vote accepted

Hint: If $x$ is even then $x-1$ is odd, and vice versa.

share|cite|improve this answer
Filmus thanks! No idea why I missed that... – muffel Jun 25 '11 at 23:56

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.