Counting Methods (1.7)
Suppose that the following conditions are met:
■ Each element of a set consists of k distinguishable parts.
■ There are n i possibilities for the first part.
■Foreachi=2,...,kandeachcombinationofthefirsti—1parts,therearen, possibilities for the /th part.
Under these conditions, there are tii •■■ elements of the set. The third condition requires only that the
number of possibilities for part i be n,- no matter what the earlier
partsare.Forexample,for/=2,itdoesnotrequirethatthesame
^2
possibilitiesbe available for part 2 regardless of
what part 1 is. It only requires that the number of possibilities be n
2
no matter what part 1 is. In this way, the
general rule includes the multiplication rule, the calculation of permutations, and sampling with replacement
as special cases. For permutations of m items k at a time, we have n,- = m —/ + 1 for / = 1,. . ., and the n,
possibilities for part i are just the n, items that have not yet appeared in the first i — 1parts. For sampling
with replacement from m items, we have n,- = m for all /, and the m possibilities are the same for every part.
In the next section, we shall consider how to count elements of sets in which the parts of each element are
not
distinguishable.