Difference between revisions of "Ball-and-urn"

(Reasoning (One of Several))
(Problems)
Line 2: Line 2:
  
 
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>.
 
 
== 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 19:46, 8 February 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}$.