Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Ball-and-urn"

(→‎Reasoning (One of Several): the aops book says it is choose k-1, not k)
(→‎Reasoning 1)
 
(43 intermediate revisions by 31 users not shown)
Line 1: Line 1:
−
The '''ball-and-urn''' technique, also known as '''stars-and-bars''', is a commonly used technique in [[combinatorics]].
+
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 drop <math>k</math> balls amongst <math>n-1</math> dividers. The number of ways to do such is <math>{n+k-1 \choose k}</math>.
+
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>.
  
−
== Reasoning (One of Several) ==
+
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>.
−
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>st". 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.
+
==Restrictions==
 +
<i> Main article: [[Distinguishability]] </i>
  
−
*1,2,3,4 <-> 1,2,3,4 (no repeats)
+
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.
−
*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>
 
−
*4,4,5,5 <-> 4,5, <math>r_1</math>, <math>r_3</math>
 
  
−
Since the reframed 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 <math>{n+k-1  
+
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]].
−
\choose k-1}</math>
+
 
 +
== 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]]
−
*[[2006 AMC 10B Problems/Problem 17]]
 
 
*[[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]]
−
*[[1986 AIME Problems/Problem 13]]
+
*[[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]]
 
[[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 $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 $k$ objects into $n$ bins is ${n+k-1 \choose n-1}$ or $\dbinom{n+k-1}k$.

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

Restrictions

Main article: Distinguishability

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}{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}\] 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, or equivalently, $n-1$ positions for the dividers out of $(n-1)+k$ total spots, 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.$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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Ball-and-urn&oldid=228960"