Difference between revisions of "Ball-and-urn"
m |
|||
| Line 1: | Line 1: | ||
| − | The [[ball-and-urn]] technique, also known as | + | 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>. | 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>. | ||
| Line 10: | Line 10: | ||
*[[1986 AIME Problems/Problem 13]] | *[[1986 AIME Problems/Problem 13]] | ||
| − | {{wikify}} | + | {{wikify}}{{stub}} |
| − | [[Category:Combinatorics]] | + | [[Category:Combinatorics]][[Category:Geometry]] |
Revision as of 23:04, 19 June 2013
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 
.
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
Template:WikifyThis article is a stub. Help us out by expanding it.
