1
$\begingroup$

I would like to know how to figure out the following problem using a combination formula: -How many ways are there of making a total of 15 using three different whole numbers?

Thank you,

Estella

$\endgroup$
  • $\begingroup$ see the Wikipedia entry on Partition to help you get started. $\endgroup$ – jlovegren Dec 31 '13 at 19:06
1
$\begingroup$

There are useful general techniques that apply to problems like these.

With distinct numbers, to do this fast, we should flip the picture around with the idea of Young diagrams. Three rows of different lengths, totalling 15 boxes is the same as a bunch of columns of lengths 1,2,3 with at least one of each length. Here's an example diagram for 10 (as opposed to 15) from Wikipedia:

Young diagram

Then we can break things down not by smallest number, but by number of threes.

  • Five 3s? No, you need at least one 1 and one 2.
  • Four 3s? 15-4*3=3, which you can only get as 1+2 with 1s and 2s. Thus, 1 possibility.
  • Three 3s? Then we need to make 6 out of 2s and 1s, which can be done with two 2s or one 2: 2 possibilities.
  • Two 3s? We need to make 9, so anywhere from one 2 to four 2s would be fine. So 4 possibilities.
  • One 3? Then we need to make 12 out of 2s and 1s. We could take anywhere from one 2 to five 2s, so 5 possibilities.
  • No 3s? Not allowed; we need at least one of each.

1+2+4+5=12, which is the answer if "whole numbers" means positive integers, as I think it does in this context.

And if "nonnegative integers" was meant, then we also need to include two-row Young diagrams. How can you build 15 out of 2s and 1s alone? You could have anywhere from one 2 to seven 2s, so you get 7 new things, so 12+7=19, as John found.

As an aside, if you weren't restricted to 2-3 minutes, and knew about generating functions, you could take this idea quite far.


If we didn't have the condition that the numbers were distinct, then the problem reduces to stars and bars: If the numbers $a$ $b$ and $c$ have to be positive integers, then $a-1$, $b-1$, and $c-1$ are nonnegative integers that sum to $15-3=12$, so that two bars and twelve stars should do it: ${14}\choose{2}$.

$\endgroup$
0
$\begingroup$

There is some subtlety in this problem. It's easy to double-count.

Try this: Start with the smallest whole number ($0$) and find all of the combinations of two different positive whole numbers that add up to $15$ given that $0$ is the third number.

Then, choose $1$ as your smallest whole number of the three, and find pairs of numbers for which the total adds up to $15$. This won't repeat any of the ones you found using $0$.

Then, start with $2$, and so forth. You won't have to go much farther. The number $4$ is the highest you'll need to start with.

$\endgroup$
  • $\begingroup$ Hello John, thank you for your input and help. Unfortunately, I am allowed only 2-3 min for this question, so I am trying to figure it out using a combination formula or some kind of a short cut. $\endgroup$ – Estella Doulis Dec 31 '13 at 19:12
  • $\begingroup$ Part of doing this question in 2-3 minutes is seeing how to solve it. The number of combinations for smallest number $0, 1, 2, 3, 4$ are $7, 5, 4, 2, 1$ for a total of $19$. The "real" answer would be to find a formula for the number of combinations of three whole numbers that add up to $n$, and that follows the same pattern. But I don't know if you ever would have learned a shortcut formula, unless you had done this specific problem. $\endgroup$ – John Dec 31 '13 at 19:26

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.