Editing Combination (section)

== Number of ways to put objects into bins ==

A combination can also be thought of as a selection of ''two'' sets of items: those that go into the chosen bin and those that go into the unchosen bin. This can be generalized to any number of bins with the constraint that every item must go to exactly one bin. The number of ways to put objects into bins is given by the [[Multinomial theorem#Ways to put objects into bins|multinomial coefficient]]

<math display="block"> \binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!},</math>

where ''n'' is the number of items, ''m'' is the number of bins, and <math>k_i</math> is the number of items that go into bin ''i''.

One way to see why this equation holds is to first number the objects arbitrarily from ''1'' to ''n'' and put the objects with numbers <math>1, 2, \ldots, k_1</math> into the first bin in order, the objects with numbers <math>k_1+1, k_1+2, \ldots, k_2</math> into the second bin in order, and so on. There are <math>n!</math> distinct numberings, but many of them are equivalent, because only the set of items in a bin matters, not their order in it. Every combined permutation of each bins' contents produces an equivalent way of putting items into bins. As a result, every equivalence class consists of <math>k_1!\, k_2! \cdots k_m!</math> distinct numberings, and the number of equivalence classes is <math>\textstyle\frac{n!}{k_1!\, k_2! \cdots k_m!}</math>.

The binomial coefficient is the special case where ''k'' items go into the chosen bin and the remaining <math>n-k</math> items go into the unchosen bin:

<math display="block"> \binom nk = \binom{n}{k, n-k} = \frac{n!}{k!(n-k)!}. </math>