# How do I approach this combinatorics problem about composition?

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.?

• 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? – user2093 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

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.