# Thread: Count the arrangements

1. ## 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.

2. ## Re: Count the arrangements

Originally Posted by CStudent
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.

3. ## Re: Count the arrangements

Originally Posted by CStudent
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?

4. ## Re: Count the arrangements

Originally Posted by CStudent
* 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?
Originally Posted by Debsta
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}$.

5. ## Re: Count the arrangements

Originally Posted by Plato
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.
Originally Posted by Plato
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!

6. ## Re: Count the arrangements

Originally Posted by Plato
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!

7. ## Re: Count the arrangements

Originally Posted by CStudent
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.

8. ## Re: Count the arrangements

Originally Posted by Plato
That was a cut&paste error it should have been six balls.
Go stand in the corner for 5, no 6 minutes!

9. ## Re: Count the arrangements

Originally Posted by Plato
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?

10. ## Re: Count the arrangements

Originally Posted by CStudent
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$.

11. ## Re: Count the arrangements

Originally Posted by Plato
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.

12. ## Re: Count the arrangements

Originally Posted by Plato
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.

13. ## Re: Count the arrangements

Originally Posted by Plato
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!

14. ## Re: Count the arrangements

Originally Posted by CStudent
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.