Probability and Statistical Inference. Robert Bartoszynski

Чтение книги онлайн.

Chapter 3 Counting

      3.1 Introduction

In the classical interpretation of probability, all outcomes of the experiment are equally likely, and the probability of an event is obtained as the relative frequency of outcomes that favor this event (imply its occurrence). Simple enumeration of elements in these sets is often not feasible, and therefore practical implementation of this principle requires developing techniques for counting elements of certain sets (e.g., sets of all possible outcomes of an experiment). The branch of mathematics dealing with such methods is called combinatorics, or combinatorial analysis. In this chapter, we introduce some combinatorial principles and illustrate their use in computing probabilities.

      A much more complete presentation of combinatorial methods and their applications to probability can be found in Feller (1968).

3.2 Product Sets, Orderings, and Permutations

      Consider two operations of some sort, which can be performed one after another. Leaving the notion of “operation” vague at the moment, we can make two assumptions:

      We have the following theorem:

Theorem 3.2.1 Under assumptions 1 and 2, a two‐step procedure consisting of a first operation followed by the second operation can be performed in distinct ways.

      Proof: Observe that each way of performing the two operations can be represented as a pair with and , where is the th way of performing the first operation and is the th way of performing the second operation if the first operation was performed in th way. All such pairs can be arranged in a rectangular array with rows and columns.

We will now show some applications of Theorem 3.2.1.

Example 3.1 Cartesian Products

      One of the most common operations on sets is the Cartesian product. If and are two sets, their Cartesian product is defined as the set of all ordered pairs , where and . For instance, if consists of elements and , while consists of the digits 1, 2, and 3, then the Cartesian product contains the six pairs

      (3.1)

      Observe that the Cartesian product is an operation quite distinct from the set‐theoretical product . For instance, in the above case, , since and have no elements in common. Also, while , for Cartesian products in general. In cases when there is no danger of confusion, we will use the term product for Cartesian product.

      Identifying now the first and second operation with “choice of an element from set ” and “choice of an element from set ,” we obtain the following consequence of Theorem 3.2.1:

Theorem СКАЧАТЬ