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"

m (n is the number of bins, and k is the number of objects. For the second case, k >= n so it must be k - 1 choose n -1)
(restored to January 27)
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''', 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>, given there can be <math>0</math> balls in an urn. However, if there can only be a positive amount of balls in an urn, then the number of ways to do such is <math>{k-1 \choose n-1}</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> 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>.
 +
 
 +
 
 +
== 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>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.
 +
 
 +
*1,2,3,4 <-> 1,2,3,4 (no repeats)
 +
*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_2</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  
 +
\choose k}</math>
 +
 
 +
== Problems ==
 +
*[[2003 AMC 10A Problems/Problem 21]]
 +
*[[2006 AMC 10B Problems/Problem 17]]
 +
*[[Mock AIME 3 Pre 2005 Problems/Problem 2]]
 +
*[[2007 AIME I Problems/Problem 10]]
 +
*[[1986 AIME Problems/Problem 13]]
 +
 
 +
[[Category:Combinatorics]]

Revision as of 08:02, 30 November 2016

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", ..., "repeat $k-1$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 $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 <-> 1,2,3,4 (no repeats)
  • 1,1,2,4 <-> 1,2,4, $r_1$
  • 1,2,2,2 <-> 1,2, $r_2$, $r_3$
  • 4,4,5,5 <-> 4,5, $r_1$, $r_2$

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 ${n+k-1 \choose k}$

Problems

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