Stars and Bars (combinatorics) - Proofs - Theorem Two

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 (1913–1960)