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

The question is from Bogart's

A composition of the integer k into n parts is a list of n positive integers that add to k. How many compositions are there of an integer k into n parts.

To begin, does the integer k itself qualify as a composition? i.e., if we look at 5, then one answer is 5... then 1 & 4, 2 & 3, etc.?

share|cite|improve this question
Well, first we need to assume that $n \leq k$. Now think of $n$ bins among which you want to distribute $k$ objects. Does this ring any bells as to standard theorems/formulas that you probably learned in class/homework/from textbook? – William Feb 15 '12 at 15:18
Hmm OK, so pigeonhole theory? Or, maybe something else.. Let me review some more then. Thank You, – Adel Feb 15 '12 at 15:19
Yes, the integer $k$ by itself qualifies as a composition. – Gerry Myerson Feb 16 '12 at 3:19
Thank You Very Much! Ok I'm getting this better now – Adel Feb 16 '12 at 4:28
up vote 2 down vote accepted

Here's a hint to get you started. Write a list of $k$ $1$s with a space between each term. Using only two symbols, a comma and a plus sign, count the number of ways to distribute these two symbols among the $k-1$ spaces.

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.