Theorem Two
If, one can apply theorem one to n + k objects, giving configurations with at least one object in each bin, and then remove one object from each bin to obtain a distribution of k objects into n bins, in which some bins may be empty. For example, placing 10 objects in 5 bins, allowing for bins to be empty, is equivalent to placing 15 objects in 5 bins and forcing something to be in each bin. An alternative way to arrive directly at the binomial coefficient: in a sequence of symbols, one has to choose k of them to be stars and the remaining to be bars (which can now be next to each other).
The case n = 0 (no bins at all) allows 0 configurations, unless k = 0 as well (no objects to place), in which there is one configuration (since an empty sum is defined to be 0). In fact the binomial coefficient takes these values for n = 0 (since by convention (unlike, which by convention takes value 0 when, which is why the former expression is the one used in the statement of the theorem).
Read more about this topic: Stars And Bars (combinatorics), Proofs
Famous quotes containing the word theorem:
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (19131960)