View source for Ball-and-urn

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> 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>k=4</math> objects in <math>n=3</math> bins. The number of ways to do such is <math>{n+k-1 \choose n}</math>, or <math>{n+k-1 \choose k-1}</math>.


== Reasoning (One of Two) ==

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, resulting in a total of <math>{n+k-1\choose k}</math> ways.

== Reasoning (One of Two) ==
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 <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 ==
*[[1986 AIME Problems/Problem 13]]
*[[2001 AMC 10 Problems/Problem 19]]
*[[2003 AMC 10A Problems/Problem 21]]
*[[Mock AIME 3 Pre 2005 Problems/Problem 2]]
*[[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]]