Results 1 to 11 of 11

Math Help - combinatory question

  1. #1
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170

    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 \binom{13}{3}

    But that gives ridiculously large numbers and i doubt it's correct =/
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Jones View Post
    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:
    \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.
    \binom{11+2-1}{11}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    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 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
    Last edited by Jones; October 14th 2009 at 06:12 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Sorry about that! I miss read. I read only two people.
    make it \binom{10+3-1}{10}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Quote Originally Posted by Plato View Post
    Sorry about that! I miss read. I read only two people.
    make it \binom{10+3-1}{10}.
    Hm, no

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

    The answer is supposed to be 105
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Jones View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Oh, sorry.

    Thank you very much then
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Jones View Post
    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 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
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,904
    Thanks
    765
    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 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 3 ways in which the coins can be given to (J, M, S).


    . . \begin{array}{cc}\text{Partition} & \text{Permutations} \\ \hline<br />
1,1,11 & 3 \\ 1,2,10 & 6 \\ 1,3,9 & 6 \\ 1,4,8 & 6 \\ 1,5,9 & 6 \\ 1,6,6 & 3 \\<br />
2,2,9 & 3 \\ 2,3,8 & 6 \\ 2,4,7 & 6 \\ 2,5,6 & 6 \end{array}
    . . . \begin{array}{cccccc}<br />
\\ 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<br />
\text{Total:} & \qquad\quad {\color{red}66}\end{array}


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


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

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


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

    "They" included these 39 cases.

    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Quote Originally Posted by Plato View Post
    Sorry about that! I miss read. I read only two people.
    make it \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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Jones View Post
    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: \binom{K+N-1}{K}.

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

    That last one can be modified in case certain cells can be empty and others not.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatory optimization problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 2nd 2010, 01:54 PM
  2. Combinatory Counting help
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: February 14th 2009, 10:07 AM
  3. Combinatory problem
    Posted in the Statistics Forum
    Replies: 3
    Last Post: November 28th 2008, 06:36 PM

Search Tags


/mathhelpforum @mathhelpforum