Probability, Random Variables, Statistics, and Random Processes

3Counting Methods and Applications

Counting problems are ubiquitous. Enumeration, the counting of objects with certain properties one after another, can solve a variety of problems. In a random experiment with finite sample space and equiprobable outcomes, we need to know how many outcomes there are in the sample space, as the probability of an event is the ratio of the number of outcomes in the event to the total number of outcomes in the sample space. However, problems arise where direct counting becomes a practical impossibility. The mathematical theory of counting is formally known as combinatorial analysis. The counting methods can determine the number of outcomes in the sample space of a random experiment, without actually listing the outcomes. Overcounting is a common enumeration error, for sometimes counting is not straightforward. As a sanity check, it is thus important to use small numbers for which it is easy to find the answer to the counting problem, and then compare the count with the formulas using small numbers.

3.1 Basic Rules of Counting

Suppose a task (experiment) can be broken down into a sequence of k independent subtasks, where k is a positive integer. Any one subtask is thus done regardless of how the other k − 1 subtasks are done. Assuming n₁, n₂, …, n_k are all positive integers, the first subtask can be accomplished in n₁ ways, the second subtask in n₂ ways, …, and the kth subtask in n_k ways. The fundamental principle of counting, also known as the ...