Difference between revisions of "Ball-and-urn"
(→Problems) |
m (→Reasoning (One of Several): Many grammatical errors.) |
||
| Line 5: | Line 5: | ||
== Reasoning (One of Several) == | == Reasoning (One of Several) == | ||
| − | If you could only put one ball in each urn, then there would be <math>{n \choose k}</math> 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 <math>n</math> urns (numbered 1 through <math>n</math>) and then you also have <math>k-1</math> urns labeled "repeat 1st", "repeat 2nd", ..., "repeat <math>k-1</math> | + | If you could only put one ball in each urn, then there would be <math>{n \choose k}</math> 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 <math>n</math> urns (numbered 1 through <math>n</math>) and then you also have <math>k-1</math> urns labeled "repeat 1st", "repeat 2nd", ..., and "repeat <math>k-1</math>-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 <math>n</math> 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 <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) | + | *1,2,3,4 <-> 1,2,3,4 (no repeats). |
| − | *1,1,2,4 <-> 1,2,4, <math>r_1</math> | + | *1,1,2,4 <-> 1,2,4, <math>r_1</math>. |
| − | *1,2,2,2 <-> 1,2, <math>r_2</math>, <math>r_3</math> | + | *1,2,2,2 <-> 1,2, <math>r_2</math>, <math>r_3</math>. |
| − | *4,4,5,5 <-> 4,5, <math>r_1</math>, <math>r_2</math> | + | *4,4,5,5 <-> 4,5, <math>r_1</math>, <math>r_2</math>. |
| − | Since the | + | 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 |
| − | \choose k}</math> | + | \choose k}.</math> |
== Problems == | == Problems == | ||
Revision as of 16:54, 10 March 2018
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 
indistinguishable objects into 
bins? We can imagine this as finding the number of ways to drop balls into urns, or equivalently to drop balls amongst 
dividers. The number of ways to do such is 
.
Reasoning (One of Several)
If you could only put one ball in each urn, then there would be 
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 urns (numbered 1 through ) and then you also have 
urns labeled "repeat 1st", "repeat 2nd", ..., and "repeat -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 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 
balls and 
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 
balls in urn 
in urn 
and 
in urn 
The same is true for the "repeat" urns options but I use the notation 
etc.
- 1,2,3,4 <-> 1,2,3,4 (no repeats).
- 1,1,2,4 <-> 1,2,4,
. - 1,2,2,2 <-> 1,2,
, 
. - 4,4,5,5 <-> 4,5, , .
, 
.Since the re-framed version of the problem has 
urns, and balls that can each only go in one urn, the number of possible scenarios is simply 
