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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – user2093 Feb 15 '12 at 15:18
  • $\begingroup$ Hmm OK, so pigeonhole theory? Or, maybe something else.. Let me review some more then. Thank You, $\endgroup$ – Adel Feb 15 '12 at 15:19
  • 1
    $\begingroup$ Yes, the integer $k$ by itself qualifies as a composition. $\endgroup$ – Gerry Myerson Feb 16 '12 at 3:19
  • $\begingroup$ Thank You Very Much! Ok I'm getting this better now $\endgroup$ – Adel Feb 16 '12 at 4:28
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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