Difference between revisions of "Ball-and-urn"

m
(LaTeX)
Line 9: Line 9:
 
For a simple example, consider <math>4</math> balls and <math>5</math> 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 <math>2</math> balls in urn <math>1, 1</math> in urn <math>2,</math> and <math>1</math> in urn <math>4.</math> The same is true for the "repeat" urns options but I use the notation <math>r_1</math> etc.
 
For a simple example, consider <math>4</math> balls and <math>5</math> 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 <math>2</math> balls in urn <math>1, 1</math> in urn <math>2,</math> and <math>1</math> in urn <math>4.</math> The same is true for the "repeat" urns options but I use the notation <math>r_1</math> etc.
  
*1,2,3,4 <-> 1,2,3,4 (no repeats).
+
*<math>1,2,3,4 \leftrightarrow 1,2,3,4</math> (no repeats).
*1,1,2,4 <-> 1,2,4, <math>r_1</math>.
+
*<math>1,1,2,4 \leftrightarrow 1,2,4,</math> <math>r_1</math>.
*1,2,2,2 <-> 1,2, <math>r_2</math>, <math>r_3</math>.
+
*<math>1,2,2,2 \leftrightarrow 1,2,</math> <math>r_2</math>, <math>r_3</math>.
*4,4,5,5 <-> 4,5, <math>r_1</math>, <math>r_2</math>.
+
*<math>4,4,5,5 \leftrightarrow 4,5,</math> <math>r_1</math>, <math>r_2</math>.
  
 
Since the re-framed version of the problem has <math>n+k-1</math> urns, and <math>k</math> balls that can each only go in one urn, the number of possible scenarios is simply <math>{n+k-1  
 
Since the re-framed version of the problem has <math>n+k-1</math> urns, and <math>k</math> balls that can each only go in one urn, the number of possible scenarios is simply <math>{n+k-1  

Revision as of 16:14, 5 July 2019

The ball-and-urn technique, also known as stars-and-bars, 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$ bins? We can imagine this as finding the number of ways to drop $k$ balls into $n$ urns, or equivalently to drop $k$ balls amongst $n-1$ dividers. The number of ways to do such is ${n+k-1 \choose k}$.


Reasoning (One of Several)

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}.$

Problems