Chapter 3 Counting Methods
3.1 Counting Principal
The Fundamental Counting Principle states that the number different possible outcomes for a sequence of \(n\) stages is the product of the number of different ways each event can occur. This principal is known by name alternate names such as also the generalized counting principal, the rule of product, the multiplication principal, and the multiplication rule.
\[ \text{Let }E_1, E_2, ..., E_k \text{ be sets of events, where each set has }n_1,n_2, ...,n_k \text{ respective elements.} \\ \text{Then there are }n_1×n_2×n_3×···×n_k \text{ combinations in which we, first,} \\ \text{choose an element of }E_1, \text{then choose element of }E_2, \text{ ... , ending with } E_k. \]
This principal is one of a few Combinatorial principles.
The counting principal can be visualized with a tree graph.
There are some immediate rules that can be followed from the counting principal. It is fair to say that this intutive rule serves as a building block for introductory combinatorical problems. Below is a table rules that are all derived from the counting principal.
| Rule | Equation |
|---|---|
| Permutations, w/ Replacement | \(n^k\) |
| Permutations w/o Replacement | \(\frac{n!}{(n-r)!}\) |
| Combinations, w/o Replacement | \(\frac{n!}{r!(n-r)!}\) |
| Combinations w/ Replacement | \(\binom{n+r-1}{r}\) |
| Number of Possible Subsets in a Set | \(2^n\) |
3.2 Permutations
A permutation is the number of ways we can order \(n\) distinct objects. From the generalized counting principle we know that if we have \(n\) ways to make the first selection, then we will have one fewer (\(n-1\)) ways to make our next selection, \(n-2\) ways to make the third selection, and so on… until we only have one option for the last selection.
This results in the factorial equation
\[ (n)(n−1)(n−2)···(1)=n! \]
We use the notation \(_nP_r\) to denote the number of permutations of a set \(A\) containing \(n\) elements taken \(r\) at a time where \(1 ≤ r ≤ n\)
The number of \(r\)-element permutations of a set containing \(n\) objects is given by
\[ _nP_r = \frac{n!}{(n-r)!} \]
Note: To avoid division by zero when \(n=r\) we define \(0! = 1\)
To derive the formula for \(_nP_r\) we consider the number of choices for each selection. This is the same things as the factorial equation above, only with one small difference. We are now considering an \(r\)-element permutation, instead of an \(n\)-element permutation. In this case, the \(r\)th outcome can take on \(n − (r − 1)\) possible choices, as opposed to the case before where we had only one option for the last selection.
_____ _____ _____ ... _____
(n) (n-1) (n-2) ... (n-(r-1)) We accounting for the ways you can permeate \(r\) objects, the result \(n - (r - 1)\) is the number of objects taken into account.
This leads us to the equation
\[ _nP_r =n(n−1)(n−2)···(n−r+1) \]
Aside: Permutations with \(_nP_n\) equate to
\[ _nP_n =n(n−1)(n−2)···(n−n+1)=n! \]
Manipulating the equation \(n(n−1)(n−2)···(n−r+1)\) leads us to the general formula
\[ _nP_r = \frac{n!}{(n-r)!} \]
3.2.1 Permutations with Replacement
By applying the counting principle, we can observe that the number of permutations in replacement sampling is equivalent to
\[ n^k = (n)(n)....(n_k) \]
3.2.2 Permutations with distinguished elements
The formulas above are valid only if all of the objects of the set are distinguishable from each other. If there are repeated elements then we must divide to cancel out the permutations that result from repeated elements like so:
\[ \frac{n!}{n_1! × n_2 ! × · · · × n_k!} \]
Consider the names Brungard and Karapanian. If for some reason we wanted to know the possible ways to rearrange the letters of each of word we would have
Brungard
\[ \frac{8!}{2!} = 20,160 \]
Karapanian
Here are ten letters, but only six are distinct
\[ \frac{10!}{4! *2!}= 75,600 \]
While there are still more ways to permute the longer last name, consider that if you did not account for repeated characters, the overcount will exceed three million.
factorial(10) - factorial(10)/(factorial(4)*factorial(2))[1] 35532003.3 Combinations
we have for \(r \le n\)
\[ \binom{n}{r}=\frac{n!}{r!(n-r)!} \]
We are calculating the number of \(r\)-element subsets from a \(n\)-element set, where order matters. This is the number of all r-element combinations of n objects, where we only use valid non-negative integers (e.g. 0,1,2, …) where \(r \le n\).
[need add derivation]
3.3.2 Useful Relations
Choosing all and choosing nothing
There is only one combination to choose all elements in a set. Similarly, there is only one way to choose nothing.
\[ \binom{n}{n}=1 \qquad \& \qquad \binom{n}{0}=1 \] Both relations can be easily be shown algebraically
\[ \binom{n}{n}=\frac{n!}{n!(n-n)!}=1 \]
Choosing 1 from n objects is the same as choosing n-1 fron n objects
\[ \binom{n}{1}=\binom{n}{n-1} \]
consider this generalization
where \(0 \le r \le n\)
\[ \binom{n}{r}=\binom{n}{n-r} \]
and
\[ \binom{n+1}{r}=\binom{n}{r}+\binom{n}{r-1} \]