Example 4c Sheldon Ross

Consider a set of n antennas of which m are defective and n − m are functional and assume that all of the defectives and all of the functionals are considered indistinguishable. How many linear orderings are there in which no two defectives are consecutive?


Imagine that the n − m functional antennas are lined up among themselves.

Now, if no two defectives are to be consecutive, then the spaces between the functional antennas must each contain at most one defective antenna That is, in the n − m + 1 possible positions—represented in Figure 1.1 by carets—between the n − m functional antennas, we must select m of these in which to put the defective antennas. Hence, there are  \({n - m + 1 \choose m}\) possible orderings in which there is at least one functional antenna between any two defective ones.