1. ## combinatory question

Hi,

I have this problem i don't know how to solve.

Jeff, Mike and Sara are to divide 13 gold coins among them, in how many ways can they divide the thirteen coins if everyone gets at least one coin?

First i thought this was an ordinary easy $\displaystyle \binom{13}{3}$

But that gives ridiculously large numbers and i doubt it's correct =/

2. Originally Posted by Jones
Jeff, Mike and Sara are to divide 13 gold coins among them, in how many ways can they divide the thirteen coins if everyone gets at least one coin?
The number of ways to put K identical objects into N different cells is:
$\displaystyle \binom{K+N-1}{K}$.

In this problem we have 13 identical coins and 2 different people.
But there is a complication. The above formula allows for empty cells.
You want each cell to contain at least one coin.
So lets go ahead one put one coin in each cell and then count the ways to give out the other 11.
$\displaystyle \binom{11+2-1}{11}$.

3. Hm,

We have 11 coins and three cells, the first coin can be placed in three different ways, second in three different ways and so forth..

hence $\displaystyle 3^{11}$ why is that incorrect?

And what do you mean by 2 different people?
Mike, Jeff and Sara makes three people, Sara may be a girl but she still counts

make it $\displaystyle \binom{10+3-1}{10}$.

5. Originally Posted by Plato
make it $\displaystyle \binom{10+3-1}{10}$.
Hm, no

$\displaystyle \binom{12}{10} = \frac{12!}{10!\ast2!} = 66$

The answer is supposed to be 105

6. Originally Posted by Jones
Jeff, Mike and Sara are to divide 13 gold coins among them, in how many ways can they divide the thirteen coins if everyone gets at least one coin?
As the question is stated, 66 is the correct answer.

If you change 13 to 16, then 105 is the answer to that question.

7. Oh, sorry.

Thank you very much then

8. Originally Posted by Jones
Hm,

We have 11 coins and three cells, the first coin can be placed in three different ways, second in three different ways and so forth..

hence $\displaystyle 3^{11}$ why is that incorrect?

And what do you mean by 2 different people?
Mike, Jeff and Sara is three people, Sara may be a girl but she still counts
$\displaystyle 3^{11}$ is incorrect since the order in which you divide the coins does not count. For example, putting 6 coins in the first cell and then 5 coins in the second cell will count as one way, whereas putting 5 in the second one and only then 6 in the first one counts as another way, while in reality they are both the same.

9. Hello, Jones!

Jeff, Mike and Sara are to divide 13 gold coins among them.
In how many ways can they divide the thirteen coins if everyone gets at least one coin?
If one or more of the people may receive no coins, the answer is 105.

The various formulas seems to be causing confusion (to me, anyway).
So I made a Brute Force list . . .

We note the following:

If the partition has three distinct numbers, e.g. (3,4,6)
. . there are $\displaystyle 3! = 6$ ways in which the coins can be given to (J, M, S).

If the partition has two distinct numbers, e.g. (4,4,5)
. . there are $\displaystyle 3$ ways in which the coins can be given to (J, M, S).

. . $\displaystyle \begin{array}{cc}\text{Partition} & \text{Permutations} \\ \hline 1,1,11 & 3 \\ 1,2,10 & 6 \\ 1,3,9 & 6 \\ 1,4,8 & 6 \\ 1,5,9 & 6 \\ 1,6,6 & 3 \\ 2,2,9 & 3 \\ 2,3,8 & 6 \\ 2,4,7 & 6 \\ 2,5,6 & 6 \end{array}$
. . . $\displaystyle \begin{array}{cccccc} \\ 3,3,7 &\qquad \quad \;3 \\ 3,4,6 &\qquad\quad\; 6 \\ 3,5,5 &\qquad\quad\; 3 \\ 4,4,5 &\qquad\quad\; 3 \\ \hline \text{Total:} & \qquad\quad {\color{red}66}\end{array}$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If one or more can receive no coins, these cases are possible:

. . $\displaystyle \begin{array}{cc} \text{Partition} & \text{Permutations} \\ \hline 0,0,13 & 3 \\ 0,1,12 & 6 \\ 0,2,11 & 6 \\ 0,3,10 & 6 \\ 0,4,9 & 6 \\ 0,5,8 & 6 \\ 0,6,7 & 6 \\ \hline \text{Total:} & 39 \end{array}$

Note that: .$\displaystyle 66 + 39 \:=\:105$

"They" included these 39 cases.

10. Originally Posted by Plato
make it $\displaystyle \binom{10+3-1}{10}$.
So in your formula you disregarded the case where not everyone got a coin,
is that one case or three cases?

By the way what is that formula called?, i haven't seen it before.

11. Originally Posted by Jones
So in your formula you disregarded the case where not everyone got a coin,
is that one case or three cases?
By the way what is that formula called?, i haven't seen it before.
These are called by various names: occupancy problems or multi-selections.
The number of ways to put K identical objects into N different cells is:
If cells can be empty: $\displaystyle \binom{K+N-1}{K}$.

If no cell can be empty: $\displaystyle \binom{K-1}{K-N}$ (here of course $\displaystyle K\ge N$) .

That last one can be modified in case certain cells can be empty and others not.