Difference between revisions of "Ball-and-urn"
Mathboy282 (talk | contribs) (→Reasoning 1) |
|||
(48 intermediate revisions by 33 users not shown) | |||
Line 1: | Line 1: | ||
− | The | + | 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 <math>k</math> indistinguishable objects into <math>n</math> bins? We can imagine this as finding the number of ways to drop <math>k</math> balls into <math>n</math> urns, or equivalently to | + | It is used to solve problems of the form: how many ways can one distribute <math>k</math> indistinguishable objects into <math>n</math> distinguishable bins? We can imagine this as finding the number of ways to drop <math>k</math> balls into <math>n</math> urns, or equivalently to arrange <math>k</math> balls and <math>n-1</math> dividers. For example, <cmath>****||</cmath><cmath>***|*|</cmath><cmath>*|**|*</cmath><cmath>...</cmath> represent the ways to put <math>4</math> objects in <math>3</math> bins. The number of ways to do such is <math>{4+3-1 \choose 3-1} = {6 \choose 2} = 15</math>. |
+ | |||
+ | More generally, the number of ways to put <math>k</math> objects into <math>n</math> bins is <math>{n+k-1 \choose n-1}</math> or <math>\dbinom{n+k-1}k</math>. | ||
+ | |||
+ | The number of ways to put <math>k</math> objects into <math>n</math> bins, where each bin must have at least 1 object in it, is <math>{k-1 \choose n-1}</math>. | ||
+ | |||
+ | ==Restrictions== | ||
+ | <i> Main article: [[Distinguishability]] </i> | ||
+ | |||
+ | 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}{m} \binom{N-m(k+1)+n-1}{n-1} = \sum_{m=0}^{\left\lfloor\frac{N}{k+1}\right\rfloor}(-1)^{m} \binom{n}{m} \binom{N-m(k+1)+n-1}{n-1}</cmath> This can be derived using the [[Principle of Inclusion-Exclusion]]. | ||
+ | |||
+ | == Reasoning 1 == | ||
+ | |||
+ | Arranging <math>k</math> *'s and <math>n-1</math> |'s is the same as saying there are <math>k+n-1</math> positions: <cmath>\underbrace{\_~~ \_~~ \_~~ \_~~ \_~~ \_~~}_{k+n-1}</cmath> and you want to fill <math>k</math> of them with *'s and the rest of them with |'s. Thus you are choosing <math>k</math> positions out of <math>n+k-1</math> total positions, or equivalently, <math>n-1</math> positions for the dividers out of <math>(n-1)+k</math> total spots, resulting in a total of <math>{n+k-1\choose n-1}</math> ways. | ||
+ | |||
+ | == Reasoning 2 == | ||
+ | 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.<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 <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. | ||
+ | |||
+ | *<math>1,2,3,4 \leftrightarrow 1,2,3,4</math> (no repeats). | ||
+ | *<math>1,1,2,4 \leftrightarrow 1,2,4,</math> <math>r_1</math>. | ||
+ | *<math>1,2,2,2 \leftrightarrow 1,2,</math> <math>r_2</math>, <math>r_3</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 | ||
+ | \choose k}.</math> Note: Due to the principle that <math>{a \choose b}={a \choose a-b}</math>, we can say that <math>{n+k-1 \choose k}={n+k-1 \choose n-1}</math>. | ||
== Problems == | == Problems == | ||
+ | *[[1986 AIME Problems/Problem 13]] | ||
+ | *[[2001 AMC 10 Problems/Problem 19]] | ||
*[[2003 AMC 10A Problems/Problem 21]] | *[[2003 AMC 10A Problems/Problem 21]] | ||
− | |||
*[[Mock AIME 3 Pre 2005 Problems/Problem 2]] | *[[Mock AIME 3 Pre 2005 Problems/Problem 2]] | ||
*[[2007 AIME I Problems/Problem 10]] | *[[2007 AIME I Problems/Problem 10]] | ||
− | *[[ | + | *[[2018 AMC 8 Problems/Problem 23]] |
− | [[ | + | *[[2019 AMC 8 Problems/Problem 25]] |
− | + | *[[2018 AMC 10A Problems/Problem 11]] | |
− | + | *[[2020 AMC 10B Problems/Problem 25]] | |
− | [[ | + | [[Category:Combinatorics]] |
Latest revision as of 00:11, 5 October 2024
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 indistinguishable objects into distinguishable bins? We can imagine this as finding the number of ways to drop balls into urns, or equivalently to arrange balls and dividers. For example, represent the ways to put objects in bins. The number of ways to do such is .
More generally, the number of ways to put objects into bins is or .
The number of ways to put objects into bins, where each bin must have at least 1 object in it, is .
Contents
[hide]Restrictions
Main article: Distinguishability
Let's say that we want to put objects in bins, but there must be at least objects in each bin. Without the restriction, we can set the following equation up: . We know that each (the bins) must have at least objects in them, so we can subtract from , since that's how many objects are left. This means that there are ways to distribute the objects.
Well, what if we can have at most objects in each bin? We can use the following formula to find this: This can be derived using the Principle of Inclusion-Exclusion.
Reasoning 1
Arranging *'s and |'s is the same as saying there are positions: and you want to fill of them with *'s and the rest of them with |'s. Thus you are choosing positions out of total positions, or equivalently, positions for the dividers out of total spots, resulting in a total of ways.
Reasoning 2
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. 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.
- (no repeats).
- .
- , .
- , .
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 Note: Due to the principle that , we can say that .