Results 1 to 14 of 14
Like Tree7Thanks
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By DenisB
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By Plato

Thread: Count the arrangements

  1. #1
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Count the arrangements

    Hey.

    * How many ways we can insert 16 similar balls to 4 drawers such that in every drawer we have at least 3 balls?

    So I know we should insert at the beginning 3 balls to every drawer and the remainder is 4 balls.
    But how can I calculate the amount of possibilities to insert 4 balls to 4 drawers without any limit?

    Thanks.
    Last edited by CStudent; Nov 23rd 2018 at 09:39 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,150
    Thanks
    3042
    Awards
    1

    Re: Count the arrangements

    Quote Originally Posted by CStudent View Post
    Hey.
    * How many ways we can insert 16 similar balls to 4 drawers such that in every drawer we have at least 3 balls?

    So I know we should insert at the beginning 3 balls to every drawer and the remainder is 4 balls.
    But how can I calculate the amount of possibilities to insert 4 balls to 4 drawers without any limit?
    First a matter of vocabulary: These problems are called multi-selections; and we say the items are indistinguishable not similar.
    The number of ways to place $K$ indistinguishable items into $N$ distinct cells is $\dbinom{N+K-1}{N}=\dbinom{N+K-1}{K-1}$

    So the four remaining balls can be placed in $\dbinom{4+4-1}{4}$ ways.

    To see the logic, suppose we are to place six balls into three boxes, $A,~B,~C$ We could model it as:
    $\underbrace \bullet _{~A~}|\underbrace { \bullet \bullet \bullet }_B|\underbrace { \bullet \bullet }_C$ that ix one in A, three in B and two in C.

    $\underbrace {\color{white}{\_\_ \_}} _{~A~}|\underbrace { \bullet \bullet }_B|\underbrace { \bullet \bullet \bullet \bullet }_C$ that is none in A, two in B and four in C.

    $\underbrace {\color{white}{\_\_ \_}} _{~A~}| \underbrace {\color{white}{\_\_ \_}}_{~B~}|\underbrace { \bullet \bullet \bullet \bullet \bullet \bullet }_C$ ALL six in C.

    We see the we can with two 'bars' and six 'bullets' model any containment of six balls into three boxes.
    The string $\bullet\bullet\bullet\bullet\bullet \bullet~ |~|$ can be rearanged in $\dfrac{8!}{6!\cdot 2!}=\dbinom{6+3-1}{6}$ ways.

    P.S. You can also read this.
    Last edited by Plato; Nov 24th 2018 at 11:45 AM. Reason: P.S.
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    1,074
    Thanks
    317

    Re: Count the arrangements

    Quote Originally Posted by CStudent View Post
    Hey.

    * How many ways we can insert 16 similar balls to 4 drawers such that in every drawer we have at least 3 balls?

    So I know we should insert at the beginning 3 balls to every drawer and the remainder is 4 balls.
    But how can I calculate the amount of possibilities to insert 4 balls to 4 drawers without any limit?

    Thanks.
    Just to clarify: Do all of the 16 balls have to end up in a drawer? That is 3,3,3,3, is not an option, but 3,3,3,7 is?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,150
    Thanks
    3042
    Awards
    1

    Re: Count the arrangements

    Quote Originally Posted by CStudent View Post
    * How many ways we can insert 16 similar balls to 4 drawers such that in every drawer we have at least 3 balls?
    So I know we should insert at the beginning 3 balls to every drawer and the remainder is 4 balls.
    But how can I calculate the amount of possibilities to insert 4 balls to 4 drawers without any limit?
    Quote Originally Posted by Debsta View Post
    Just to clarify: Do all of the 16 balls have to end up in a drawer? That is 3,3,3,3, is not an option, but 3,3,3,7 is?
    Each drawer contains at least three balls; $3\cdot 4=12,~\&~16-12=4$ that means that now that leaves four balls to put into any of the four drawers.
    $\dbinom{4+4-1}{4}=\dbinom{7}{4}=35$.

    Here is another solution.

    ${\left( {\sum\limits_{k = }^7 {{x^k}} } \right)^4}$=Attachment 39136SEE HEREhttps://www.wolframalpha.com/input/?...%3D3,7%5D)%5E4

    Either click upon the image or go to the website to see the expansion. In the expanded generating function you see the term:
    $35x^{16}$ that tells us that there are there are thirty-five ways to do the selections.

    Because I have been writing several of these for tests considerations. Here is a variation on this one.
    We want to put twenty-five indistinguishable balls into four numbered boxes.
    If we want at least $k$ balls in box $k$ how many ways can that be done?
    Well because $1+2+3+4=10$. if we go ahead and put $k$ balls into box $k$ then we have fifteen balls left to place into four numbered boxes.
    That means doing it in $\dbinom{15+4-1}{15}=816$ ways to do that.

    Now lets check it with a generating see here. SEE HERE
    YES indeed that it is in the expansion: $816x^{25}$.
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Count the arrangements

    Quote Originally Posted by Plato View Post
    First a matter of vocabulary: These problems are called multi-selections; and we say the items are indistinguishable not similar.
    The number of ways to place $K$ indistinguishable items into $N$ distinct cells is $\dbinom{N+K-1}{N}=\dbinom{N+K-1}{K-1}$

    So the four remaining balls can be placed in $\dbinom{4+4-1}{4}$ ways.

    To see the logic, suppose we are to place six balls into three boxes, $A,~B,~C$ We could model it as:
    $\underbrace \bullet _{~A~}|\underbrace { \bullet \bullet \bullet }_B|\underbrace { \bullet \bullet }_C$ that ix one in A, three in B and two in C.

    $\underbrace {\color{white}{\_\_ \_}} _{~A~}|\underbrace { \bullet \bullet }_B|\underbrace { \bullet \bullet \bullet \bullet }_C$ that is none in A, two in B and four in C.

    $\underbrace {\color{white}{\_\_ \_}} _{~A~}| \underbrace {\color{white}{\_\_ \_}}_{~B~}|\underbrace { \bullet \bullet \bullet \bullet \bullet \bullet }_C$ ALL six in C.

    We see the we can with two 'bars' and six 'bullets' model any containment of six balls into three boxes.
    The string $\bullet\bullet\bullet\bullet\bullet \bullet~ |~|$ can be rearanged in $\dfrac{8!}{6!\cdot 2!}=\dbinom{6+3-1}{6}$ ways.

    P.S. You can also read this.
    Quote Originally Posted by Plato View Post
    Each drawer contains at least three balls; $3\cdot 4=12,~\&~16-12=4$ that means that now that leaves four balls to put into any of the four drawers.
    $\dbinom{4+4-1}{4}=\dbinom{7}{4}=35$.

    Here is another solution.

    ${\left( {\sum\limits_{k = }^7 {{x^k}} } \right)^4}$=Attachment 39136SEE HEREhttps://www.wolframalpha.com/input/?...%3D3,7%5D)%5E4

    Either click upon the image or go to the website to see the expansion. In the expanded generating function you see the term:
    $35x^{16}$ that tells us that there are there are thirty-five ways to do the selections.

    Because I have been writing several of these for tests considerations. Here is a variation on this one.
    We want to put twenty-five indistinguishable balls into four numbered boxes.
    If we want at least $k$ balls in box $k$ how many ways can that be done?
    Well because $1+2+3+4=10$. if we go ahead and put $k$ balls into box $k$ then we have fifteen balls left to place into four numbered boxes.
    That means doing it in $\dbinom{15+4-1}{15}=816$ ways to do that.

    Now lets check it with a generating see here. SEE HERE
    YES indeed that it is in the expansion: $816x^{25}$.
    Hey thanks.

    I almost understand the logic of this formula N+K-1 above N but not absolutely.

    I catched what you had explained with your example but I noticed that one bullet has "disappeared", you now have 5 bullets instead of 6, why?

    Thank you!
    Last edited by Plato; Nov 24th 2018 at 11:47 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Count the arrangements

    Quote Originally Posted by Plato View Post
    Each drawer contains at least three balls; $3\cdot 4=12,~\&~16-12=4$ that means that now that leaves four balls to put into any of the four drawers.
    $\dbinom{4+4-1}{4}=\dbinom{7}{4}=35$.

    Here is another solution.

    ${\left( {\sum\limits_{k = }^7 {{x^k}} } \right)^4}$=Attachment 39136SEE HEREhttps://www.wolframalpha.com/input/?...%3D3,7%5D)%5E4

    Either click upon the image or go to the website to see the expansion. In the expanded generating function you see the term:
    $35x^{16}$ that tells us that there are there are thirty-five ways to do the selections.

    Because I have been writing several of these for tests considerations. Here is a variation on this one.
    We want to put twenty-five indistinguishable balls into four numbered boxes.
    If we want at least $k$ balls in box $k$ how many ways can that be done?
    Well because $1+2+3+4=10$. if we go ahead and put $k$ balls into box $k$ then we have fifteen balls left to place into four numbered boxes.
    That means doing it in $\dbinom{15+4-1}{15}=816$ ways to do that.

    Now lets check it with a generating see here. SEE HERE
    YES indeed that it is in the expansion: $816x^{25}$.
    Yes, but I want the understand the logic of this formula N+K-1 ... To identify cases where I have to use that.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,150
    Thanks
    3042
    Awards
    1

    Re: Count the arrangements

    Quote Originally Posted by CStudent View Post
    I catched what you had explained with your example but I noticed that one bullet has "disappeared", you now have 5 bullets instead of 6, why?
    That was a cut&paste error it should have been six balls.
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    2,070
    Thanks
    413

    Re: Count the arrangements

    Quote Originally Posted by Plato View Post
    That was a cut&paste error it should have been six balls.
    Go stand in the corner for 5, no 6 minutes!
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Count the arrangements

    Quote Originally Posted by Plato View Post
    That was a cut&paste error it should have been six balls.
    Thank you all!

    What if I would like to insert 16 indistinguishable balls into 4 drawers such that every drawer has and odd number of balls?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,150
    Thanks
    3042
    Awards
    1

    Re: Count the arrangements

    Quote Originally Posted by CStudent View Post
    Thank you all!

    What if I would like to insert 16 indistinguishable balls into 4 drawers such that every drawer has and odd number of balls?
    What if I would like to insert 16 indistinguishable balls into 4 drawers such that every drawer has and odd number of balls?
    Realize that zero is not odd. So no drawer can be empty. For me I would use generating functions. SEE HERE
    $\displaystyle {\left( {\sum\limits_{k = 1}^9 {{x^{2k - 1}}} } \right)^4}$ Note that each exponent is odd and the least is one. So no drawer is empty.
    The term $84x^{16}$ tells us that your answer is $84$.
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,150
    Thanks
    3042
    Awards
    1

    Re: Count the arrangements

    Quote Originally Posted by Plato View Post
    What if I would like to insert 16 indistinguishable balls into 4 drawers such that every drawer has and odd number of balls?
    Realize that zero is not odd. So no drawer can be empty. For me I would use generating functions. SEE HERE
    $\displaystyle {\left( {\sum\limits_{k = 1}^9 {{x^{2k - 1}}} } \right)^4}$ Note that each exponent is odd and the least is one. So no drawer is empty.
    The term $84x^{16}$ tells us that your answer is $84$.
    This is really a P.S. to the above. After coffee it occurred to me an elementary way to do this.
    The trick is that any odd number added to an even gives an odd. As you have done before think on putting one ball in each drawer.
    That leaves twelve. Now 'glue' the twelve together in pairs, giving six pairs. Now distribute the six into the four drawers:
    $\dbinom{6+4-1}{6}=84$ SEE HERE
    No drawer is empty because we started with one ball in each & each drawer contains an odd number of balls.
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Count the arrangements

    Quote Originally Posted by Plato View Post
    What if I would like to insert 16 indistinguishable balls into 4 drawers such that every drawer has and odd number of balls?
    Realize that zero is not odd. So no drawer can be empty. For me I would use generating functions. SEE HERE
    $\displaystyle {\left( {\sum\limits_{k = 1}^9 {{x^{2k - 1}}} } \right)^4}$ Note that each exponent is odd and the least is one. So no drawer is empty.
    The term $84x^{16}$ tells us that your answer is $84$.
    I don't really understand this way of using Sigma to solve this kind of exercises. Moreover, don't know why it runs from 1 to 9.

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Count the arrangements

    Quote Originally Posted by Plato View Post
    This is really a P.S. to the above. After coffee it occurred to me an elementary way to do this.
    The trick is that any odd number added to an even gives an odd. As you have done before think on putting one ball in each drawer.
    That leaves twelve. Now 'glue' the twelve together in pairs, giving six pairs. Now distribute the six into the four drawers:
    $\dbinom{6+4-1}{6}=84$ SEE HERE
    No drawer is empty because we started with one ball in each & each drawer contains an odd number of balls.
    Amazing, thank you!
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,150
    Thanks
    3042
    Awards
    1

    Re: Count the arrangements

    Quote Originally Posted by CStudent View Post
    I don't really understand this way of using Sigma to solve this kind of exercises. Moreover, don't know why it runs from 1 to 9.
    List $2k-1$ for $k=1,\cdots,9$. we get $1,~3,~5,~7,~9,~11,~13,~15,~17$ .
    You wanted odd numbers in each drawer, moreover we want up to fifteen.
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How to count effectiveness
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Dec 17th 2017, 05:35 AM
  2. Where do the Numbers we count with come from?
    Posted in the Math Philosophy Forum
    Replies: 9
    Last Post: Nov 3rd 2014, 01:15 AM
  3. What does 3^n count?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 7th 2011, 02:59 AM
  4. triangular count
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 27th 2010, 07:22 AM
  5. How to count?
    Posted in the Math Challenge Problems Forum
    Replies: 3
    Last Post: Oct 7th 2008, 05:17 AM

/mathhelpforum @mathhelpforum