3  The Basic Principle of Counting

3.1 Basic Rules

3.1.1 Counting Measure

We define the counting measure \(|A| =\) the number of elements in the set (or event) \(A\).

Example: A neighborhood association has 100 families on its membership list. 78 of the families have a credit card and 50 of the families are currently paying off a car loan. 41 of the families have both a credit card and a car loan. A financial planner intends to call on one of the 100 families today. The planner’s sample space consists of the 100 families in the association. The events of interest to the planner are the following: * \(C\): the family has a credit card * \(L\): the family has a car loan

We are given: \(|C| = 78, |L| = 50, |L\cap C|=41\). The planner is interested in: - How many families do not have credit card: \(|C^c| = |\Omega| - |C| = 100 - 78 = 22\) - How many families have either a credit card or a car loan: \(|L\cup C| = |L| + |C| - |L \cap C| = 78 + 50 - 41 = 87\)

We have come to the following two rules:

Proposition: For any sets \(A, B \subset \Omega\), where the sample space \(\Omega\) is finite, we have: \[\begin{align} |A^c| &= |\Omega| - |A|\\ |A \cup B| &= |A| + |B| - |A\cap B|\end{align}\] ### Empty Set The empty set is the set which has no elements, denote by the symbol \(\emptyset\).

3.1.2 Mutual Exclusivity

Two events \(A\) and \(B\) are mutually exclusive if \(A \cup B = \emptyset\).
If \(A\) and \(B\) are mutually exclusive, then \[|A\cup B|= |A| + |B|\] ## The Multiplication Principle for Counting Proposition: Suppose that the outcomes of an experiment consist of a combination of two separate tasks or actions. Suppose there are \(n\) possibilities for the first task, and that for each of these \(n\) possibilities there are \(k\) possible ways to perform the second task. Then there are \(nk\) possible outcomes for the experiment.

Task 1	Task 2	Total Outcome
\(n\) ways	\(k\) ways	\(nk\) ways

The multiplication principle also applies to combined experiments consisting of more than two tasks. A generalization is the following:

Proposition (Multiplication Principle for Counting): Suppose that the outcomes of an experiment consist of a combination of \(k\) separate tasks or actions. If task \(i\) can be performed in \(n_i\) ways for each combined outcome of the remaining tasks, for \(i=1,..,k\), then the total number of outcomes for the experiment is \(n_1 \times n_2 \times ... \times n_k\).

Task 1	…	Task k	Total Outcome
\(n_1\) ways		\(n_k\) ways	\[n_1 \times n_2 \times ... \times n_k\] ways

Example: In how many ways can the 24 members of a faculty senate of a college choose a president, a vice-president, a secretary, and a treasurer?

Solution: Number of ways = \(24 \times 23 \times 22 \times 21 = 255024\)

Example: How many different 7-place license plates are possible if the first 3 places are to be occupied by letters and the final 4 by numbers, and repetition among letters or numbers were prohibited?

Solution: Number of license plates = \(26 \times 25 \times 24 \times 10 \times 9 \times 8 \times 7 = 78,624,000\)