Welcome to our community

Be a part of something great, join today!

Count the arrangements

CStudent

New member
Nov 16, 2018
15
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 have to insert at first 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.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,490
The number of ways $k$ indistinguishable balls can be put into $n$ drawers is equal to the number of multisets of cardinality, or size, $k$ consisting of $n$ distinct elements. (I explain why below.) This number is often denoted by \(\displaystyle \left(\!\!\!\binom{n}{k}\!\!\!\right)\) and is called a multiset coefficient. Just like the binomial coefficient \(\displaystyle \binom{n}{k}\) equals the number of subsets, or combinations in combinatorics parlance, of size $k$ taken from a set of size $n$, the multiset coefficient \(\displaystyle \left(\!\!\!\binom{n}{k}\!\!\!\right)\) equals the number of multisets, or combinations with repetitions, of size $k$ whose elements come from a set of size $n$. Note that unlike the number of combinations, in the latter case $k$ can be greater than $n$ because elements in a multiset can be repeated.

There is a one-to-one correspondence between multisets of size $k$ drawn from a set of size $n$ and $n$ drawers that have $k$ balls combined inside them. For example, if $n=4$ and $k=5$, the multiset $\{1,1,3,4,4\}$ corresponds to the situation where drawer 1 has two balls, drawer 3 has one ball and drawer 4 has two balls.

Finally, \(\displaystyle \left(\!\!\!\binom{n}{k}\!\!\!\right)=\binom{n+k-1}{k}\). This is explained in Wikipedia and in the linked article there.