Counting Techniques
Counting is fundamental to mathematics but more so in statistics and probability. Understanding counting techniques is useful in solving both simple and complex problems.
Multiplication
Suppose we want to number the total possible number of outcomes from a triple coin toss. We can do this manually and it will work well when $n$ tosses are small. The actual result is:
$$hhh, hht, hth, thh, tht, tth, htt, ttt $$
We can employ the multiplicative rule and compute the total possible outcomes by computing the two possible outcomes for every position given the number of toses. For three coin tosses:
$$ 2 * 2 * 2 = 8$$
We multiply by 2 because there are two possible outcomes for every coin toss and we are tossing the coin three times.
Permutation
Permutations are a way to calculate the total outcomes of an an event in instances where the order of the events matters. This is often used in cases where a specific ordering is imperative to the experient for example the sequence of passwords or arrangements of items.
Suppose we have 5 people on a shelf, how many ways can 5 books be arranged on the shelf? To answer this question, we need to define the factorial concept. Factorial (symbolized with an exclamation mark !) is mathematically expresses as:
$$n! = n*(n-1)*(n-2)*(n-3)*...*1$$
Solution:
In this case, the solution to our problem is:
$$5! = 5*4*3*2*1 = 120$$
In python we can compute the factorial as follows:
from scipy.special import factorial
factorial(5, exact=True)Combinations
Combinations are a way to calculate the total outcomes of an an event in instances where the order of the events does not matter. Unlike permutations where order matters, combinations disregards this and just computes the possible outcomes of the event.
Suppose that we have 4 tickets to a football game and have 7 employees that can attend the game. How many ways can we select 4 individuals for the tickets from a group of 7 employees?
This is an example of a combination question
Mathematically, combination is defined as:
$$ _nC_{r} = {n \choose r} = \frac {n!} {(n-r)!(r)!}$$
Solution:
$$ _{7}C_{4} = {7 \choose 4} = \frac {7!} {(7-4)!(4)!} = \frac {7!} {(3)!(4)!} = \frac {7*6*5} {3*2*1} = 7*5 =35 $$
To implement this in python, we use the comb method from scipy.special class
from scipy.special import comb
comb(7,4)Practice Problem
Suppose we have a class of total 7 boys and 6 girls. How many way can a subset of 7 students such that 4 are boys and 3 are girls?
comb(7,6)