# Thread: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

1. ## Combination Problem Involving Numbers 1-9 to Form a Sum of 10

I received a word problem that goes like this.
A local kindergarten is thinking of making posters that show all the different ways of adding two or more integers from 1 to 9 to get a sum of 10. If there is enough space on each poster for up to 50 possible solutions, how many posters will the school need to make?
(Note: sums that contain the same number but in a different order are considered to be different; for example, 1 + 9 and 9 + 1 are two different solutions.)
What is the answer to this problem, and more importantly, how do I solve it?

To make clear, a solution such as, "1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1," is a valid one.

2. ## Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

Originally Posted by JollyJack
I received a word problem that goes like this.
A local kindergarten is thinking of making posters that show all the different ways of adding two or more integers from 1 to 9 to get a sum of 10. If there is enough space on each poster for up to 50 possible solutions, how many posters will the school need to make?
(Note: sums that contain the same number but in a different order are considered to be different; for example, 1 + 9 and 9 + 1 are two different solutions.) What is the answer to this problem, and more importantly, how do I solve it?
To make clear, a solution such as, "1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1," is a valid one.
Consider $3 + 2 + 2 + 1 + 1 + 1 + 1 + 1$ that sum is $10$.
But those eight digits can be arranged in $\dfrac{8!}{(5!)(2!)}=168$ ways.
Personally I doubt that your idea that order makes a difference is correct.

This general question is well known as integer partitions into sums.
But order makes no difference.

3. ## Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

Originally Posted by Plato
Consider $3 + 2 + 2 + 1 + 1 + 1 + 1 + 1$ that sum is $10$.<br>
But those eight digits can be arranged in $\dfrac{8!}{(5!)(2!)}=168$ ways.

That accidental sum is 12 instead of the intended 10. I was wondering what you intended the actual addends to be for your example.

4. ## Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

Originally Posted by greg1313
That accidental sum is 12 instead of the intended 10. You are a combinations expert,
so I was wondering what you intended the actual addends to be for your example.
No you are correct. I JUST CAN'T ADD. I wanted $3+2+2+1+1+1$

5. ## Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

Originally Posted by JollyJack
I received a word problem that goes like this.
A local kindergarten is thinking of making posters that show all the different ways of adding two or more integers from 1 to 9 to get a sum of 10. If there is enough space on each poster for up to 50 possible solutions, how many posters will the school need to make?
(Note: sums that contain the same number but in a different order are considered to be different; for example, 1 + 9 and 9 + 1 are two different solutions.)
What is the answer to this problem, and more importantly, how do I solve it?

To make clear, a solution such as, "1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1," is a valid one.
Suppose there is exactly 1 plus sign. We will use dots and a single plus sign. A valid configuration would be something like this:
.+......... (which represents 1+9)
We know there must be at least one dot to the right of the plus, so we will treat +. as a single symbol. We cannot start the pattern with a +, so we will place a single . to the far left. That leaves 8 dots and the +. We permute everything but the left-most dot (which is fixed). There are $\dbinom{9}{1} = 9$ such permutations.

Suppose there are exactly 2 plus signs. We place the left-most . again. Then, we have +. and +. along with seven other .'s. We permute everything but the left-most .: $\dbinom{9}{2}$ ways.

Suppose there are exactly 3 plus signs. We place the left-most . again. Then we have 3x '+.' and 6x '.' for which there are $\dbinom{9}{3}$ permutations of these nine symbols (we do not permute the left-most .).

We see the pattern and get:

$$\sum_{i=1}^9 \dbinom{9}{i} = 2^9-1 = 511$$

I believe that is the correct number of sums, but I have not double-checked my work.

It would then take 11 posters.

6. ## Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

I still doubt that the OP means to ask the question that implies that order makes a difference.
This is a well known question about integer partitions.
Look at this webpage.
Now my subscription is for WolframalphaPro. So I hope all can see that there are 42 partitions of 10.
But for this problem, using only single digits there would be only 41.
Here they are:
If from that list we choose $3+2+2+1+1+1=10$ and order makes a difference, then there are $\dfrac{6!}{(2!)(3!)}=60$ in that count.
So we would need to do that for each of the 41 cases.

7. ## Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

Originally Posted by Plato
I still doubt that the OP means to ask the question that implies that order makes a difference.
This is a well known question about integer partitions.
Look at this webpage.
Now my subscription is for WolframalphaPro. So I hope all can see that there are 42 partitions of 10.
But for this problem, using only single digits there would be only 41.
Here they are:
If from that list we choose $3+2+2+1+1+1=10$ and order makes a difference, then there are $\dfrac{6!}{(2!)(3!)}=60$ in that count.
So we would need to do that for each of the 41 cases.

This indicates that if order matters, my answer above was correct.

Also, there is a fairly straightforward combinatorial argument. Consider the initial string:

1+1+1+1+1+1+1+1+1+1

There are 9 pluses. If we remove a plus, we add the adjacent digits together. Example, if we remove the first plus, we get:
11+1+1+1+1+1+1+1+1
which becomes
2+1+1+1+1+1+1+1+1

So, if we consider the nine element set of positions of pluses, each ordered sum is in one-to-one bijection with a subset of this set of nine positions. The only subset that is not matched to a sum is the empty set (no pluses, which would just be the number 10). So, since there are $2^9$ subsets of the nine element set, and we remove the empty set, there are $2^9-1=511$ nonempty subsets, which is equal to the number of ordered sums.

8. ## Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

511 is the number I get as well.