# Difference between revisions of "Ball-and-urn"

m |
Deathbymath (talk | contribs) 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) |
||

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>{ | + | 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> |

## Revision as of 01:45, 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 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 , given there can be 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