A counting problem is the task of finding the number of elements of some set with a particular property. Such counting problems are usually encountered in combinatorics.
Many important decisions, whether from business, government, science, recreation or even one’s personal life must be made with incomplete information or some degree of uncertainty. Hence, a formalized study of uncertain or random outcomes occupies an important role in modern society. In situations where one of any number of possible outcomes may occur, the mathematical model of probability theory offers methods for quantifying the likelihoods associated with those outcomes.
Probability also provides tools which allow us to move beyond simply describing the information contained within a set of data (descriptive statistics) to actually inferring further information from that data (inferential statistics).
Many of the early attempts to model likelihood arose from games of chance.
An experiment is any action or process whose outcome is subject to uncertainty or randomness.
Here the term experiment is used in a wider sense than its usual connotation with controlled laboratory situations. Further clarification on experiments will be given later, but for now the following examples of experiments will suffice:
Assuming that an experiment can be repeated under identical conditions, then each repetition of an experiment is called a trial.
\({\displaystyle \Omega }=\{{\text{H}},{\text{T}}\}}{\displaystyle \Omega =\{{\text{H}},{\text{T}}\}}.\)
An event is any subset of zero or more outcomes contained in a given sample space. A simple event consists of exactly one outcome and a compound event consists of more than one outcome. For example, when tossing a single coin \({\displaystyle \Omega =\{{\text{H}},{\text{T}}\}}\), possible events are \({\displaystyle \{\}}\{\}, {\displaystyle \{H\}}{\displaystyle \{H\}}, {\displaystyle \{T\}}{\displaystyle \{T\}}\), and \({\displaystyle \{H,T\}}{\displaystyle \{H,T\}}\).
For example, when the trial consists of throwing two dice, the set of all outcomes with a sum of 7 pips may constitute an event, whereas outcomes with an odd number of pips may constitute another event.
If the outcome is the element of the elementary event of two pips on the first die and five on the second, then both of the events, “7 pips” and “odd number of pips”, are said to have occurred. Modeling events as sets of outcomes in a sample space \(\Omega\) allows us to leverage all of the regular set operations:
Given two events \(A\) and \(B\):
The null subset \({\displaystyle \emptyset }\) in a sample space \(\Omega\) is called an impossible event.
The union of two events \({\displaystyle A\cup B}\) consists of all outcomes that are in \(A\) or in \(B\) or in both,
The intersection {AB}AB consists of all outcomes that are both in \(A\) and \(B\).
The complement \({\displaystyle A^{c}}\) of an event \(A\) in a sample space \(\Omega\) consists of all outcomes not in \(A\), but in \(\Omega\) , i.e. \({\displaystyle A\cup A^{c}=\Omega }\).
What Are the Rules of Probability in Math?
1. Addition Rule
Whenever an event is the union of two other events, say A and B, then \(P(A \text { or } B)=P(A)+P(B)-P(A \cap B)\)
\(\mathrm{P}(\mathrm{A} \cup \mathrm{B})=\mathrm{P}(\mathrm{A})+\mathrm{P}(\mathrm{B})-\mathrm{P}(\mathrm{A} \cap \mathrm{B})\)
2. Complementary Rule
Whenever an event is the complement of another event, specifically, if A is an event, then P(not A)=1−P(A) or P(A') = 1 - P(A').
\(P(A)+P\left(A^{\prime}\right)=1\)
3. Conditional Rule
When event A is already known to have occurred and probability of event
B is desired, then P(B, given A)=P(A and B)P(A, given B). It can be vica
versa in case of event B.
\(\mathrm{P}(\mathrm{B} \mid
\mathrm{A})=\mathrm{P}(\mathrm{A} \cap \mathrm{B})
\mathrm{P}(\mathrm{A})\)
4. Multiplication Rule
Whenever an event is the intersection of two other events, that is, events A and B need to occur simultaneously. Then P(A and B)=P(A)⋅P(B).
\(\mathrm{P}(\mathrm{A} \cap \mathrm{B})=\mathrm{P}(\mathrm{A}) \cdot \mathrm{P}(\mathrm{B} \mid \mathrm{A})\)
In this section we look at counting problems, including combinations and permutations.
Pascal’s identity, first derived by Blaise Pascal in 19th century, states that the number of ways to choose k elements from n elements is equal to the summation of number of ways to choose (k-1) elements from (n-1) elements and the number of ways to choose elements from n-1 elements.
Mathematically, for any positive integers k and n: \[ nCk=n−1Ck−1+n−1CknCk=n−1Ck−1+n−1Ck \] Proof −
\[\begin{eqnarray} { n\choose k} n−1Ck−1+n−1Ck n−1Ck−1+n−1Ck &=& (n−1)!(k−1)!(n−k)!+(n−1)!k!(n−k−1)! \\ &=& (n−1)!(k−1)!(n−k)!+(n−1)!k!(n−k−1)!\\ &=&(n−1)!(kk!(n−k)!+n−kk!(n−k)!)\\ &=&(n−1)!(kk!(n−k)!+n−kk!(n−k)!)\\ &=&(n−1)!nk!(n−k)!=(n−1)!nk!(n−k)!\\ &=& n!k!(n−k)! \\ &=&n!k!(n−k)!\\ &=&nCkll\\ &=&nCk\\ \end{eqnarray}\]
In 1834, German mathematician, Peter Gustav Lejeune Dirichlet, stated a principle which he called the drawer principle. Now, it is known as the pigeonhole principle.
Pigeonhole Principle states that if there are fewer pigeon holes than total number of pigeons and each pigeon is put in a pigeon hole, then there must be at least one pigeon hole with more than one pigeon. If n pigeons are put into m pigeonholes where n > m, there’s a hole with more than one pigeon.
Ten men are in a room and they are taking part in handshakes. If each person shakes hands at least once and no man shakes the same man’s hand more than once then two men took part in the same number of handshakes.
There must be at least two people in a class of 30 whose names start with the same alphabet.
The Inclusion-exclusion principle computes the cardinal number of the union of multiple non-disjoint sets. For two sets A and B, the principle states −
\[|A∪B|=|A|+|B|−|A∩B||A∪B|=|A|+|B|−|A∩B|\] For three sets A, B and C, the principle states −
\[|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C||A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|\] The generalized formula -
\[ |⋃ni=1Ai|=∑1≤i<j<k≤n|Ai∩Aj|+∑1≤i<j<k≤n|Ai∩Aj∩Ak|−⋯+(−1)π−1|A1∩⋯∩A2||⋃i=1nAi|=∑1≤i<j<k≤n|Ai∩Aj|+∑1≤i<j<k≤n|Ai∩Aj∩Ak|−⋯+(−1)π−1|A1∩⋯∩A2| \]
How many integers from 1 to 50 are multiples of 2 or 3 but not both?
From 1 to 100, there are 50/2=2550/2=25 numbers which are multiples of 2.
There are 50/3=1650/3=16 numbers which are multiples of 3.
There are 50/6=850/6=8 numbers which are multiples of both 2 and 3.
So, |A|=25|A|=25, |B|=16|B|=16 and |A∩B|=8|A∩B|=8.
|A∪B|=|A|+|B|−|A∩B|=25+16−8=33|A∪B|=|A|+|B|−|A∩B|=25+16−8=33
\[\frac{n!}{n-k!}\]
\[ {n \choose r} = \frac{n!}{(n-r)! r!} \]
\[ {6 \choose 3} = \frac{6!}{(6-3)! 3!} = \frac{6!}{3! \times 3!}\]
\[ \frac{6!}{3! \times 3!} = \frac{6 \times 5 \times 4 \times 3!}{3! \times 3!} = \frac{120}{6} = 120\] \end{itemize}
\({6 \choose 2} = 15\)
\({5 \choose 2} = 10\)
\({4 \choose 0} = 1\)
\({4 \choose 3} = 4\)
A permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements.
The word “permutation” also refers to the act or process of changing the linear order of an ordered set.
Videos
% http://www.mathsisfun.com/combinatorics/combinations-permutations.html
| ### *{Session 09: Probability} |
| [9A.1] Counting Methods [9A.2] Counting using Sets [9A.3] Probability [9A.4] Independent Events |
| [9B.1] Permutation |
| \[ {n \choose r} = \frac{n!}{(n-r)! r!} \] |
| \[ {6 \choose 3} = \frac{6!}{(6-3)! 3!} = \frac{6!}{3! \times 3!}\] |
| \[ \frac{6!}{3! \times 3!} = \frac{6 \times 5 \times 4 \times 3!}{3! \times 3!} = \frac{120}{6} = 120\] |
| %\begin{multicol}{2} |
| * \({6 \choose 2} = 15\) * \({5 \choose 2} = 10\) * \({4 \choose 0} = 1\) * \({4 \choose 3} = 4\) |
| %\end{multicol} |
| * pairwise disjoint sets * The addition principle |
| #### *{Theorem} \[ |A \cup B| = |A| + |B| - |A \cap B| \] |
| #### *{Probability} |
| [9B.2] The sample space of an experiment (\(S\)) [9B.3] The size of a sample space [9B.4] Indepedent Events (9.3.1) |
| ### *{Combinations} |
| #### *{Formula} \[ \binom nk = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots 1},\] which can be written using factorials as whenever \(k\leq n\) |
| #### *{Example 1} |
| \[ \binom 5 2 = \frac{5!}{2!(5-2)!} = \frac{5.4.3!}{2! .3!} = \frac{5.4}{2.1} = 10\] |
| #### *{Example 2} |
| \[ \binom 5 0 = \frac{5!}{0!(5-0)!} = \frac{5!}{0! .5!} = \frac{5!}{2!} = 1\] Recall \(0! =1\) |
| #### Permutations |
| * The notion of permutation relates to the act of permuting (rearranging) objects or values. * Informally, a permutation of a set of objects is an arrangement of those objects into a particular order. |
| * For example, there are six permutations of the set \(\{1,2,3\}\), namely (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). * As another example, an anagram of a word is a permutation of its letters. |
| ### {Session 9 Probability} #### {Binomial Coefficients} |
| * factorials \[ n! = (n)\times (n-1)\times(n-2) \times \ldots \times 1 \] |
| * $5! = 5 = 120 $ * \(3! = 3 \times 2 \times 1\) |
| * Zero factorial \[ 0! = 1 \] |
% \[P(A |B = \frac{P(A \cap B)}{P(B)})\]
The complement rule in Probability
\(P(C^{\prime}) = 1- P(C)\)
If the probability of C is \(70 \%\) then the probability of \(C^{\prime}\) is \(30\%\)
The factorial function (symbol: !) just means to multiply a series of descending natural numbers. Examples:
Importantly \[n! = n \times (n-1)! = n \times (n-1) \times (n-2)! \] For Example \[6! = 6 \times 5! = 6 \times 5 \times 4! \] ### *{Combinations} In mathematical terms, a combination is an subset of items from a larger set such that the order of the items does not matter.
If the order doesn’t matter, it is a Combination.
If the order does matter it is a Permutation.
Permutations where repetition is allowed: \[ n! \]
Permutations where repetition is not allowed [ /]
| [1] Choose Operator \[ {n \choose k} = \frac{n!}{k! \times (n-k)!} \] Evaluate the following: |
|---|
| %Page 29 [2] In how many ways can a group of four people be selected from three men and four women? In how many of these groups are there more women than men? |
%PAGE 66 [3] In how many ways can a group of five be selected from ten people How many groups can be selected if two particular people from the ten can not be selected in the same group?\ \ [4] %http://www.mathsireland.com/LCHGeneralNotes/PermCombProb/5_5_Prob_MultAnd/Q_5_5_Prob_MultAnd.html The Venn Diagram shows the number of elements in each subset of set \(S\). If \(P(A) = 3/10\) and \(P(B) = 1/2\), find the values of \(x\) and \(y\) %Page 27 [5] How many different four digit numners greater than 5000 can be formed from the digits if each digit can only be used once in any given number. How many of these numbers are odd?
| #### {Permutation Formula} A formula for the number of possible permutations of k objects from a set of n. This is usually written \(^nP_k\) . \[ ^nP_k = \frac{n!}{(n-k)!} = n.(n-1).(n-2).\ldots(n-k+1) \] |
|---|
| #### {Permutation Formula} \ How many ways can 4 students from a group of 15 be lined up for a photograph?\ |
\ There are \(^{15}P_4\) possible permutations of 4 students from a group of 15. \[ ^{15}P_4 = \frac{15!}{11!} = 15\times 14\times 13\times 12 = 32760 \] There are 32760 different lineups.
| #### { Permutations} Given a set of distinct numbers, \(\{1, 2, 3, 4 \}\), find all permutations containing 2 numbers. \[\{1,2\},\{1,3\},\{1,4\}, \{2,1\}, \{2,3\}, \{2,4\}, \] \[\{3,1\},\{3,2\},\{3,4\}, \{4,1\}, \{4,2\}, \{4,3\}, \] When all the permutations have to be in ascending order. \[\{1,2\},\{1,3\},\{1,4\}, \phantom{\{2,1\}}, \{2,3\}, \{2,4\}, \] |
| \[\phantom{\{3,1\},\{3,2\}},\{3,4\}, \phantom{\{4,1\}, \{4,2\}, \{4,3\}}\] |
\[\{1,2\},\{1,3\},\{1,4\}, \{2,1\},
\{2,3\}, \{2,4\}, \] \[\{3,1\},\{3,2\},\{3,4\}, \{4,1\}, \{4,2\},
\{4,3\}, \] \[ ^4P_2 = \frac{4!}{2!} =
12 \; \] \[\{1,2\},\{1,3\},\{1,4\},
\phantom{\{2,1\}}, \{2,3\}, \{2,4\}, \] \[\phantom{\{3,1\},\{3,2\}},\{3,4\},
\phantom{\{4,1\}, \{4,2\}, \{4,3\}}\] \[ ^4C_2 = \frac{4!}{2!\times 2!} = 6 \]
#### { Permutations} Given a set of distinct numbers, \(\{1, 2, 3, 4 \}\), find all permutations
containing 3 numbers. (Strictly ascending permutations in red). \[\boldsymbol{ extbf{\{1,2,3\}}}, \boldsymbol{
extbf{\{1,2,4\}}}, \{1,3,2\},\boldsymbol{ extbf{\{1,3,4\}}},
\{1,4,2\},\{1,4,3\}, \] \[\{2,1,3\},
\{2,1,4\}, \{2,3,1\},\boldsymbol{ extbf{\{2,3,4\}}},
\{2,4,1\},\{2,4.3\}, \] \[\{3,1,2\},
\{3,1,4\}, \{3,2,1\},\{3,2,4\}, \{3,4,1\},\{3,4,2\}, \] \[\{4,1,2\}, \{4,1,3\}, \{4,2,1\},\{4,3,1\},
\{4,3,1\},\{4,3,2\} \]
\[ ^4P_3 = \frac{4!}{1!} = 24 \] \[ ^4C_3 = \frac{4!}{3!\times 1!} = 4 \]
—————————————————————— #### { Permutations}
{
In a group of 50 students 24 like cold drinks and 36 like hot drinks and each student likes at least one of the two drinks. How many like both coffee and tea?
Let X be the set of students who like cold drinks and Y be the set of people who like hot drinks.
So, |X∪Y|=50|X∪Y|=50, |X|=24|X|=24, |Y|=36|Y|=36 |X∩Y|=|X|+|Y|−|X∪Y|=24+36−50=60−50=10|X∩Y|=|X|+|Y|−|X∪Y|=24+36−50=60−50=10 Hence, there are 10 students who like both tea and coffee.
\[ {n \choose k} = \frac{n!}{k! \times (n-k)!} \] Evaluate the following:
In how many ways can a group of four people be selected from three men and four women? In how many of these groups are there more women than men?
In how many ways can a group of five be selected from ten people How many groups can be selected if two particular people from the ten can not be selected in the same group?\
The Venn Diagram shows the number of elements in each subset of set \(S\). If \(P(A) = 3/10\) and \(P(B) = 1/2\), find the values of \(x\) and \(y\)
The code to open a combination lock is an ordered sequence of four digits chosen from the set \(\{1, 2, 3, 4, 5, 6, 7\}\). How many different codes are possible
Twelve balls numbered \(\{1,2,3, \ldots ,12\}\) are placed in a container and three balls are drawn at random without replacement. How many different selections of three balls are possible, if the order of selection is not important?
