Combinatorics helps us to count things. A simple operation of counting things can have several aspects such as orderings, combinations and other concepts. Within this field of Combinatorics, "Permutation" concept exists. Permutation is a way of ordering things. The notation P(n) denotes total possible orderings for "n" things. Following understanding of concepts and ideas are adapted from
"Probability: For the Enthusiastic Beginner by David Morin." Please purchase his book for good reference on these concepts and encourage him. He is awesome!
General ordering of n items:
Consider a case study of alphabet arrangement.
Case-1:
There is only one way to arrange a single alphabet A.
So, the total number of Permutations for 1 entity is P(1) = 1 as { A }
Case-2:
Two alphabets A &B can be arranged in 2 ways: AB & BA
So, the total number of Permutations for 2 entities is P(2) = 2 as { AB, BA }
For each alphabet, there is only way to arrange the other alphabet. There are 2 alphabets in total. So it is 2xP(1). Using dot notation, case-2 is written as P(2) = 2.P(1).
Case-3:
The total Permutations of 3 alphabets are :
P(3) = 6 as { ABC, ACB, BAC, BCA, CAB, CBA }.
For each alphabet, rest of the alphabets can be arranged in 2 ways. For A, BC & CA are possible orderings for left out alphabets B &C just as Case-2 which further leads to Case-1. So ABC, ACB are possible permutations if A is the first selected alphabet. For B as the first alphabet, CA & AC are possible orderings for left out alphabets C & A. So BCA, BAC permutations are possible. Similarly we get CAB & CBA if we select C as first alphabet. Thus, we got 6 in total. Thus, Case-3 can be written as P(3) = 3 times Case-2 = 3.P(2) = 3.2.P(1) = 3.2.1.
If we expand this to dataset of 4 alphabets A,B,C & D, we get P(4) = 4.P(3). For 5, we get 5.P(4). To generalize, we have
P(n) = n.P(n-1)
n.P(n-1) is mathematically notated as factorial of first n numbers, n!
1! = 1
2! = 2.1=2
3!=3.2.1=6
4!=4.3.2.1=24
5!=5.4.3.2.1=120 & so on.
So we write above equation as
P(n) = n.P(n-1)=n!
Analogy wise, this experiment of arranging numbers or items can be questioned in another way: Calculate the number of way you can pickup n objects from n available objects.
Ordering of outcomes of identical trials:
Let us consider drawing a ball from a bag as a trial. Trial. Both of these trials are called identical trials as configuration and sequence of actions doesn't vary.
Ordered sets with replacement & repetition allowed:
After picking up a ball from bag, I shall note down the alphabet on it & return the ball back to its bag. This is called replacement. While writing down outcomes from both trials, if I get A from trial 1 and another A from trial 2, I shall allow it and write down as {A,A}. This is called repetition allowed. Let us say I drew the ball A in trial 1 and the ball B in trial 2. I got {A,B}. Consider another combination {B,A}. I shall write down these outcomes as distinct sets wherein order mattered and both these outcome sets are considered. Following is the complete set of all possible outcomes, noted down as ordered sets (order matters for distinction) for n=2 trials. That means trial 1 has a ball picked up from the bag, noted down & placed back into bag for subsequent repetition. For each ball drawn from bag, there are 5 possibilities ( equal to total number of distinct balls in bag ). As there are 5 balls, it boils down to 5.5=5²=25 ordered outcomes.
{A,A} {A,B} {A,C} {A,D} {A,E}
{B,A} {B,B} {B,C} {B,D} {B,E}
{C,A} {C,B} {C,C} {C,D} {C,E}
{D,A} {D,B} {D,C} {D,D} {D,E}
{E,A} {E,B} {E,C} {E,D} {E,E}
If I arranged a third trial, we get a total of 5.5.5=125 ordered outcomes. They look something {A,B,D} , {A,C,E}, {B,B,B} and so on. So the total combinations of N unique objects in n trials can be given as Nⁿ.
If you think this in terms of slots to be filled, the result is the same. For example, I have 2 slots:
X1 X2
These 2 slots can be filled by any of those alphabets {A,B,C,D,E}. X1 if filled by A, can have 5 possible combinations of X2 being filled by either of A or B or C or D or E. Now rotate the chance of X1 being filled by other alphabets other than A and repeat the same possible combinations for X2. You find yourself in 25 (Nⁿ, N=5 & n=2) outcomes.
Side notes:
Inherently, you can see if A & B are chosen to fill these slots, we have {A,B} & {B,A}. This is again similar to general ordering of 2 objects in 2!. Every outcome has its mirror reflection due to this inherent 2! ordering of 2 slots. If you exclude repeated outcomes ( {A,A}, {B,B}, {C,C}, {D,D}, {E,E} ), you have 20 outcomes which include mirror copies of unique outcomes. So if you divide 20 by 2!, you get 10 unique outcomes which you would see later. Repeated outcomes can't be consider mirror duplicates because both {A,A} of left-to-right orientation & {A, A} of right-to-left orientation are not visibly distinguishable and thus only a single copy of them is maintained.
Number of possible outcomes = Nⁿ
You can also treat Nⁿ outcomes for possible ways to pick up n objects from complete set of N objects, if you think n objects as equal to slots to be filled as per previous slot analogy.
Ordered sets with NO repetition allowed:
In this case, we are saying that we will not tolerate exact same outcome seen in trial 1 for subsequent trials. Meaning, if trial 1 witnessed A then trial 2 and further trials shouldn't get A as outcome. We do this by not replacing the picked up ball in any trial. So for picking up ball A from the bag in trial 1, there are only 4 ( which is 5-1) combinations possible from the same bag in next trial. So if N objects (outcomes) are possible in trial 1, (N-1) outcomes are possible in trial 2 for each of N in trial 1. Mathematically, this is summarized for 2 trials as N(N-1) total possible outcomes WITHOUT repetitions. In terms of slot analogy, if first slot is filled with A, 2nd slot has to be filled by either B, C or D but NOT A which is N-1 possible combinations. Repeat this for rest of alphabets and we have N.(N-1) combinations.
{A,A} {A,B} {A,C} {A,D} {A,E}
{B,A} {B,B} {B,C} {B,D} {B,E}
{C,A} {C,B} {C,C} {C,D} {C,E}
{D,A} {D,B} {D,C} {D,D} {D,E}
{E,A} {E,B} {E,C} {E,D} {E,E}
So for 3 trials, we get 5.4.3 = 60 outcomes. This is generalized as N.(N-1).(N-2). For 4 trials, we have N.(N-1).(N-2).(N-3) = 5.4.3.2 = 120 ordered sets with replacement and NO repetitions allowed. This goes on for n trials as N.(N-1).(N-2).(N-3).....(N-(n-1)) where n = number of trials and n<N. The last trial (n) has N-(n-1) because (n-1) objects have to be eliminated from total N due to its preceding (n-1) trials to eliminate redundancy.
Let us try to derive a general formula for this expression. If you recollect earlier n! definition for first n things, it is applicable for any non negative number. Even for 0, it has output 1 (just go with for now without thinking much). For n=5, 5! = 5x4x3x2x1=120
Now for 4 trials of above experiment, we have 5.4.3.2 outcomes. 3 trials resulted in 5.4.3 outcomes. What can be done to 5! (which is a 5x4x3x2x1 product) to give correct outcomes for n=4 trials and n=3 trials? The answer is division. If 5! is divided by 2! (which is 5-3) to indicate 3 trials, we have 5x4x3 = 60. Similarly, if 5! is divided by (5-4)! indicate 4 trials, we have 5x4x3x2 = 120.So N! must be divided by (N-n)! to give total outcomes for n identical trials for N objects with no repetitions allowed.
Number of possible outcomes =N!/(N-n)!
This also means that there are N!/(N-n)! ways to pickup n objects from N total objects to have ordered set outcomes with no repetitions.
Unordered sets with NO repetition allowed:
Unordered sets are those which treat {A,B} and {B,A} of equal value. This means we shouldn't account {B,A} outcome if {A,B} already occurred. If you take above total outcomes for N=5 objects and n=2 trials for ordered sets with NO repetitions allowed, we would eliminate more outcomes to avoid double counting for Unordered sets. This gives us 10 outcomes.
{A,A} {A,B} {A,C} {A,D} {A,E}
{B,A} {B,B} {B,C} {B,D} {B,E}
{C,A} {C,B} {C,C} {C,D} {C,E}
{D,A} {D,B} {D,C} {D,D} {D,E}
{E,A} {E,B} {E,C} {E,D} {E,E}
We have already considered this unique outcome derivation from sides notes in "Ordered set with replacement and repetition allowed" category above. As the number of slots (trials) to be filled are 2 and these slots can be arranged in 2! as per our first section on general ordering of n items, we need to divide the Ordered set outcomes without repetition by 2! to get Unordered set outcomes (all unique with no repetition) . For n trials wherein each trial can be visualized as a slot which should be filled with an object or a ball to be picked up, the division happens by n!
Number of possible outcomes =N!/(N-n)!/n!=N!/n!(N-n)!
This also means that there are N!/n!(N-n)! ways to pickup n objects from N total objects to have unordered (unique) set outcomes with no repetitions.
Probability:
Probability states the chance or "how likely?" a desired outcome can happen out of all possible outcomes of an event. The event in context can be something as trivial as tossing coins, rolling a die, picking up a playing card from a deck and so on. Probability concepts are expanded into more intricate concepts which are vital to Machine Learning.
Probability of a desired outcome = (total number of possible desired outcomes of an event)/(total number of all possible outcomes of an event)
Yes, it is expressed as a fraction. Take a coin for instance. There are two possible outcomes. "Heads" & "Tails". Let us pick "Heads" as our desired outcome. Then by formula, Probability (P) of Heads can be given as:
P(Heads) = 1/2
There can be only one Head in a single coin toss. Same goes for Tails.
P(Tails) = 1/2
Let us take another example. A dice has 6 upward facing sides, each with distinct number of dots. When dots are counted, these faces can be called as {1,2,3,4,5,6} outcomes. Total possible outcomes as "6".
Here the probability of occurrence of any of these outcomes in a single event "rolling the dice for once" is 1/6. This is because there are no duplicate numbers/faces on the dice. This explanation can be summarized as
P(1) = P(2) = P(3) = P(4) = P(5) = P(6) = 1/6
If we combine probability of each of possible outcomes, we get "1".
P(1)+P(2)+P(3)+P(4)+P(5)+P(6) = 1/6+1/6+1/6+1/6+1/6+1/6=1
"1" denotes the completeness that accounts the occurrence of all possible outcomes. We can think that each of possible outcome owns a probability slice in this large pizza, denoted as "1".
Apply the same to a "Single toss of a coin" event. We get:
P(Heads)+P(Tails)=1/2+1/2=1
If Heads show up in a coin toss, we say "Heads" outcome occurred & "Tails" outcome didn't occur. The probability of an outcome to NOT occur is derived by subtracting the probability of that outcome from "1", the completeness. This gives the probability of occurrence of this event to NOT produce your interested outcome from the set of all outcomes. Mathematically,
P(NO Tails)=1-P(Tails)
Let us pick the probability of "3" not occurring in an event "Single roll of dice". We get as below:
P(NO 3) = 1-(Probability of outcome "3") = 1-P(3) = 1-(1/6) = 5/6
Literally, it says the chance of "3" NOT occurring is "5 out of 6 TIMES".
Normal Distribution:
Consider an event of flipping a single coin 5 times. Each flip outcome has 2 possible outcomes: a Head or a Tail. So this event can produce a total of 2 to power of 5 = 32 possible outcomes. In order to store the probability of occurrence of desired outcome, we select a variable called "Random Variable (X)".
Let us select Heads as our desired outcome. The probability of Heads not occurring at all can be given as P(X=0) = (Probability of no Heads (or) all Tails)/(Probability of all possible outcomes) = 1/32
We can visualize the slots to be filled with individual outcomes of flips in this event as below:
X1 X2 X3 X4 X5
If you think of no Heads at all, all these slots have to be filled by tails as T T T T T which is just a single possible rare outcome with a probability of 1 out of 32 outcomes of flipping a coin 5 times. Let us now consider probability of occurrence of 1 Head out of 5 flips, indicated by P(X=1). That can be either X1, X2, X3, X4 or X5 slots bearing the Heads and rest are tails. For instance, we can pick X3 slot witnessing Heads as outcome and rest of slots are all tails. This is visualized as below:
T T H T T
X1 as Tails has probability of (1/2). Other slots X2, X4 X5 have same probability (1/2) as coin flip in each turn is not affected with earlier outcome and each flip is an independent event. However, if you like to have the sequence in this exact manner but order not mattered, you need to multiple all these individual probabilities together as : (1/2).(1/2).X3.(1/4).(1/5). X3 is also (1/2) as probability of Heads occurring out of Head & Tails outcome of single coin flip is again a (1/2). So,
P(X=1) = (1/2).(1/2).(1/2).(1/2).(1/2) = 1/32
.png)
.png)
