TABLE OF CONTENTS There are many probability problems, especially those concerned with gambling, that can ultimately be reduced to questions about cardinalities of various sets. We saw several examples in Section 1.3. Those examples were simple, and they were chosen so that it was easy to determine the cardinalities of the required sets. However, in more complicated problems, it is extremely helpful to have some systematic methods for finding cardinalities of sets. Combinatorics is the study of systematic counting methods, which we will be using to find the cardinalities of various sets that arise in probability. The four kinds of counting problems we discuss are:
ordered sampling with replacement;
ordered sampling without replacement;
unordered sampling without replacement; and
unordered sampling with replacement.
Of these, the first two are rather straightforward, and the last two are somewhat complicated.
Before stating the problem, we begin with some examples to illustrate the concepts to be used.
Let A, B, and C be finite sets. How many triples are there of the form ( a, b, c), where a ? A, b ? B,and c ? C?
Solution. Since there are A choices for a, B choices for b, and C choices for c, the total number of triples is A B C.
Similar reasoning...
