1
$\begingroup$

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

  • 1
    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?2012-02-15
  • 0
    Hmm OK, so pigeonhole theory? Or, maybe something else.. Let me review some more then. Thank You,2012-02-15
  • 1
    Yes, the integer $k$ by itself qualifies as a composition.2012-02-16
  • 0
    Thank You Very Much! Ok I'm getting this better now2012-02-16

1 Answers 1

2

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.