Difference between revisions of "Ball-and-urn"

Revision as of 17:12, 30 December 2022

The ball-and-urn technique, also known as stars-and-bars, sticks-and-stones, or dots-and-dividers, is a commonly used technique in combinatorics.

It is used to solve problems of the form: how many ways can one distribute $k$ indistinguishable objects into $n$ distinguishable bins? We can imagine this as finding the number of ways to drop $k$ balls into $n$ urns, or equivalently to arrange $k$ balls and $n-1$ dividers. For example, $****||$ $***|*|$ $*|**|*$ $...$ represent the ways to put $4$ objects in $3$ bins. The number of ways to do such is ${4+3-1 \choose 3-1} = {6 \choose 2} = 15$ .

More generally, the number of ways to put $n$ objects into $k$ bins is ${n+k-1 \choose k-1}$ .

The number of ways to put $n$ objects into $k$ bins, where each bin must have at least 1 object in it, is ${n-1 \choose k-1}$ .

Restrictions

Let's say that we want to put $N$ objects in $n$ bins, but there must be at least $k$ objects in each bin. Without the restriction, we can set the following equation up: $a_1+a_2+a_3+\dots+a_n=N$ . We know that each $a_i$ (the bins) must have at least $k$ objects in them, so we can subtract $nk$ from $N$ , since that's how many objects are left. This means that there are $\binom{N-nk+n-1}{n-1}$ ways to distribute the objects.

Well what if we can have at most $k$ objects in each bin? We can use the following formula to find this: $\binom{N+n-1}{n-1} - \sum_{m=1}^{\left\lfloor\frac{N}{k+1}\right\rfloor}(-1)^{m+1} \binom{n}{k+1} \binom{N-m(k+1)+n-1}{n-1} = \sum_{m=0}^{\left\lfloor\frac{N}{k+1}\right\rfloor}(-1)^{m} \binom{n}{k+1} \binom{N-m(k+1)+n-1}{n-1}$ This can be derived using the Principle of Inclusion-Exclusion.

Reasoning 1

Arranging $k$ *'s and $n-1$ |'s is the same as saying there are $k+n-1$ positions: $\underbrace{\_~~ \_~~ \_~~ \_~~ \_~~ \_~~}_{k+n-1}$ and you want to fill $k$ of them with *'s and the rest of them with |'s. Thus you are choosing $k$ positions out of $n+k-1$ total positions, resulting in a total of ${n+k-1\choose n-1}$ ways.

Reasoning 2

If you could only put one ball in each urn, then there would be ${n \choose k}$ possibilities; the problem is that you can repeat urns, so this does not work. You can, however, reframe the problem as so: imagine that you have the $n$ urns (numbered 1 through $n$ ) and then you also have $k-1$ urns labeled "repeat 1st", "repeat 2nd", ..., and "repeat $k-1$ -th". After the balls are in urns you can imagine that any balls in the "repeat" urns are moved on top of the correct balls in the first $n$ urns, moving from left to right. There is a one-to-one correspondence between the non-repeating arrangements in these new urns and the repeats-allowed arrangements in the original urns.

For a simple example, consider $4$ balls and $5$ urns. The one to one correspondence between several of the possibilities and the "repeated urns" version is shown. Since there are 4 balls, these examples will have three possible "repeat" urns. For simplicity, I am listing the numbers of the urns with balls in them, so "1,1,2,4" means $2$ balls in urn $1, 1$ in urn $2,$ and $1$ in urn $4.$ The same is true for the "repeat" urns options but I use the notation $r_1$ etc.

$1,2,3,4 \leftrightarrow 1,2,3,4$ (no repeats).
$1,1,2,4 \leftrightarrow 1,2,4,$ $r_1$ .
$1,2,2,2 \leftrightarrow 1,2,$ $r_2$ , $r_3$ .
$4,4,5,5 \leftrightarrow 4,5,$ $r_1$ , $r_2$ .

Since the re-framed version of the problem has $n+k-1$ urns, and $k$ balls that can each only go in one urn, the number of possible scenarios is simply ${n+k-1 \choose k}.$ Note: Due to the principle that ${a \choose b}={a \choose a-b}$ , we can say that ${n+k-1 \choose k}={n+k-1 \choose n-1}$ .

Problems

@@ Line 6: / Line 6: @@
 The number of ways to put <math>n</math> objects into <math>k</math> bins, where each bin must have at least 1 object in it, is <math>{n-1 \choose k-1}</math>.
+==Restrictions==
+Let's say that we want to put <math>N</math> objects in <math>n</math> bins, but there must be at least <math>k</math> objects in each bin. Without the restriction, we can set the following equation up: <math>a_1+a_2+a_3+\dots+a_n=N</math>. We know that each <math>a_i</math> (the bins) must have at least <math>k</math> objects in them, so we can subtract <math>nk</math> from <math>N</math>, since that's how many objects are left. This means that there are <math>\binom{N-nk+n-1}{n-1}</math> ways to distribute the objects.
+Well what if we can have at most <math>k</math> objects in each bin? We can use the following formula to find this: <cmath>\binom{N+n-1}{n-1} - \sum_{m=1}^{\left\lfloor\frac{N}{k+1}\right\rfloor}(-1)^{m+1} \binom{n}{k+1} \binom{N-m(k+1)+n-1}{n-1} = \sum_{m=0}^{\left\lfloor\frac{N}{k+1}\right\rfloor}(-1)^{m} \binom{n}{k+1} \binom{N-m(k+1)+n-1}{n-1}</cmath> This can be derived using the [[Principle of Inclusion-Exclusion]].
 == Reasoning 1 ==

Page

Toolbox

Search