Introduction to Probability and Stochastic Processes with Applications

APPENDIX B

INTRODUCTION TO COMBINATORICS

In Chapter 1 we saw that probability in Laplace spaces reduces itself to counting the number of elements of a finite set. The mathematical theory dealing with counting problems of that sort is formally known as combinatorial analysis. All the counting techniques are based on the following fundamental principle.

Theorem B.l (The Basic Principle of Counting) Suppose that two experiments are carried out. The first one has m possible results and for each result of this experiment there are n possible results of the second experiment Then, the total number of possible results of the two experiments, when carried out in the indicated order, is mn.

Proof:   The basic principle of counting can be proved by enumerating all possible results in the following way:

This array consists of m rows and n columns and therefore has mn entries.  

EXAMPLE B.1

There are 10 professors in the statistics department of a University, each with 15 graduate students under their tutelage. If one professor and one of his students are going to be chosen to represent the department at an academic event, how many different ways can the selection be made?

In this case there ...