We will be using a first course in probability by Sheldon Ross. This book is the standard for probability theory. The PDF can be found here.
https://readyforai.com/download/a-first-course-in-probability-9th-edition-pdf/
Forpart 1 of probability theory, we will only be looking at chapters 1-4. Everything after chapter 5 requires calculus.
Combinatorics is a branch of mathematics that gives us the theoretical framework to count. We can all count in fact, we learn to count from a very young age, however there are entities that are far too large to count. If we had three blocks of three different colors (Blue, Red, Green), how could we count the number of ways we could arrange the blocks by color? One would simply try to list them out such as (Blue Red Green), (Bue, Green Red), (Red, Green , Blue) (Red Blue Green) (Green Red Blue) (Green Blue Red)…we listed out 6!
What if we wanted to find all possible telephone numbers or all possible lottery ticket number combinations?? We are unable to list those out, however, we have techniques and methods to count these things. Counting and probability go hand in hand but we will get to probability after we learn to count.
Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of m possible outcomes and if, for each outcome of experiment 1, there are n possible outcomes of experiment 2, then together there are mn possible outcomes of the two experiments.
To summarize the theorem of the basic principal of counting, if we have some experiemnt with m outcomes and another experiment with n outcomes, then m multiplied by n yield the total number of outcomes from both experiments.
Lets jump right into an example, A small community consists of 10 women, each of whom has 3 children. If one woman and one of her children are to be chosen as mother and child of the year, how many different choices are possible?
Our throught process should be how can we take this scenerio and divide it up into an experiment A and Experiment B. In our case, our choice of woman is one experiment and the choice of child is the other experiment,hence, the number of different choices for mother of the year is 10 X 3 =30
We can actually generalize this theorem to consider cases where there could be more than 2 experiments. This is known as the generalized principal of counting
If r experiments that are to be performed are such that the first one may result in any of ni possible outcomes; and if, for each of these ni possible outcomes, there are nz possible outcomes of the second experiment; and if, for each of the possible outcomes of the first two experiments, there are n3 possible outcomes of the third experiment; and if … , then there is a total of ni · nz · · · n, possible outcomes of the r experiments.
Lets do an example of the generalized principle
Our thought process should be similar to the counting theorem. How can we divide the situation into experiments. The choice of one member from each class is the experiment hence if we multiply 3 X 4 X 5 X 2 =120. Hence, there are 120 ways to choose a subcommittee of 4 people from the planning committee.
At this point, you are probably wondering if order matters or doesnt matter. This is a very important concept that will be dealt with later on.
Lets practice some additional examples so that we may feel comfortable with the generalized principal of counting.
It is easy to conceptualize this problem if you imagine slots where digits and numbers will go. We have a 7-place license plate , so we can imagine 7 slots as follows: _ _ - _ _ _ The first 3 slots go to letters and the final 4 go to numbers. We can think of each slot as its own experiment. We need to identify the number of outcomes per experiment (slot) Also note, we are not given any infromation regarding lower case or upper case so for sake of simplicity, lets assume lower case only. We can also assume letters and numbers can be repeated.
For each of the first three slots, we can have one of 26 possible letters (a-z) and for the last four slots we can have one of 10 possible digits (0-9), hence we can make 26 X 26 X 26 X 10 X 10 X 10 X 10 = 175,760,000 different license plates
Lets revist the example we did first with the three blocks of diffrent colors. When we looked at this problem, we listed all the orderings but now lets apply our counting principal. If we imagine three slots for each block _ _ _ ,then each slot its own experiment, however we know that blocks can’t repeat becuase they are physical objects. For the first slot, we have our choice of three blocks. For the second slot, we only have a choice of two blocks, and for the last slot, we can only choose from one slot, hence 3 X 2 X 1=6. In this case order did matter. This leads us to the concept of the permutation.
So far, we have only looked at situations where there are no restrictions such as ordering or repition. Lets now introduce the theoretical framework to be able to answer the same kinds of questions with some sort of ordering condition applied.
Suppose now that we have n objects. The number of ways to get n permutations is
This is actually what a factorial is. In this case, n should be positive and if n is 0,then 0!=1. This makes more sense than people think. It’s the same as saying how many ways can you order 0 things on a very high level. There are more rigid number theory proofs to show why this is true but that is way out of scope.
Lets look at some examples
in the first slot, we have 9 players to choose from, in the second slot we have 8 players to choose from, in the third slot we have 7 players to choose from…keep going down the list until you have no more players to choose from. We can then see that the number of ways to order a baseball team of 8 players is 9 x 8 x 7 x 6 x 5 x 4 x 3 X 2 X 1=9!= 362,880
How many different rankings are possible? In this case, we do not need to differentiate between women or men since we are looking at the entire class as a whole. There are 6+4=10 students total, so there are 10! = 3,628,800 possible rankings of students.
If the men are ranked just among themselves and the women just among themselves, how many different rankings are possible? In this case, we simply consider the men and women in their own groups. There are 6! rankings for men and 4! possible rankings for women, hence if we consider rank men and women seperate,then we have a total of (6!) X (4!)= 17,280 possible rankings.
This problem is going to be a little tricky because there are two layers of permutations we need to consider. lets break it down bit by bit.
Lets start with the ordering of the subjetcs. There are 4 subjects (math, chem, history, language)…each slot belongs to a subject but remember that within each subject, there are multiple books. We will get to that later,but we have _ _ _ _, so in the first slot, we have 4 subjects to choose from, the third only has 3….and so forth, hence we only have 4! ways to order subjects. Now lets factor in the books within each subject.
In math, we have 4 books so 4 math books can be arranged 4! ways. We have 3 chem books that can be arranged 3! ways. We have 2 history books that can be arranged 2! and finally 1 language book can be arranged 1 way.
If we put this all together, then we can arrange all the books kept together by subject , 4! X 4! X 3! X 2! X 1!=6,912
(Use whiteboard to show groupings)
Now lets examine a special case of permutations
What happens in cases where objects cannot be distinguished from one another? We need a re-working of our factorial, otherwise we will be overcounting.
ex) How many different letter arrangements can be formed from the letters PEPPER?
P3-P2-E2-P1-E1-R
We can see that we are over counting,even if we distinguish the repeated letters from one another because in the end, they are still the same letter. If we permutate the P’s and the E’s alone, we get 3! ways to arrange P’s and 2! ways to arrange E’s. We have 6 letters that can be arranged 6! ways and we divide this by the overcounting factors of repeated objects, in our case P’s and E’s. Hence,
\[ \frac{6!}{3!2!}=60 \]
We can generalize the indistiguishable permutations to the following formula:
\[ \frac{n!}{n_1 ! n_2 ! ...n_r !} \] we can find different permutations of n objects, of which ni are alike, nz are alike, … , n, are alike.
We are given information about nationalities but not players themselves, therefore, players are indistinguishable objects. 10 players can be distinguished 10! ways. Our denominator is going to consist of the factors which are similar,hence 4 russian players 4! ways, 3 us players 3! ways, 2 great britain players 2! ways and 1 brazil player 1 way, hence the number of outcomes of players is
\[ \frac{10!}{4!3!2!1!}=12,600 \]
We will now introduce the framework to be able to select different groups from a set of possible choices. We want to count the number of ways to select groups of r objects that could be formed from a total of n objects. It shoudl follow that r needs to be less than or equal to n. Lets introduce the proper notation.
\[ \begin{pmatrix} n \\ r \end{pmatrix}=nCr=\frac{n!}{(n-r)!r!}\\ r\le n \] Both of these notations mean the same thing. You read it as n choose r. How many ways can we choose r groups from n objects?
We have to count how many ways to form a committee of 3 from 20 people, regardless of order.
\[ \begin{pmatrix} 20 \\ 3 \end{pmatrix}=20C3=\frac{20!}{(20-3)!3!}= \frac{20!}{17!3!}=\frac{20\bullet19\bullet18\bullet17!}{17!3!}=\frac{20\bullet19\bullet18}{3\bullet2} =1,140 \]
We need to use combinations on top of the counting principal. Our first experiment is choosing 2 of the 5 women and our second experiment is choosing 3 out of the 7 men. We have 5C2 ways to select women and 7C3 ways to select men,therefore:
\[ \begin{pmatrix} 5 \\ 2 \end{pmatrix}\begin{pmatrix} 7 \\ 3 \end{pmatrix} \] To make our work easier, we can do each part one by one and then multiply the results at the end.
\[ \begin{pmatrix} 5 \\ 2 \end{pmatrix}=5C2=\frac{5!}{(5-2)!2!}=\frac{5!}{3!2!}=\frac{5\bullet4\bullet3!}{3!2\bullet1}=\frac{5\bullet4}{2}=(5\bullet2)=10 \] \[ \begin{pmatrix} 7 \\ 3 \end{pmatrix}=7C3=\frac{7!}{(7-3)!3!}=\frac{7!}{4!3!}=\frac{7\bullet6\bullet5\bullet4!}{4!3\bullet2\bullet1}=\frac{7\bullet6\bullet5}{3\bullet2\bullet1}=(7\bullet5)=35 \] Finally we put our results together by using the basic counting principal.
\[ \begin{pmatrix} 5 \\ 2 \end{pmatrix}\begin{pmatrix} 7 \\ 3 \end{pmatrix}=(10)(35)=350 \]
Now lets answer the next part of the question. How can we make the same arrangement if 2 of the men are feuding and refuse to serve on the committee together?
The number of ways to select the women still remain unchanged. We found that 5C2=10. As for the men, we found that there are 7C3=35 ways to select men including the two men who are fueding so what if we count the number of ways to select groups where the men are fueding and then subtract this number from all possible choices of men?
There are 7 men total. We can break this up as counting the number of ways we can select men where two fueding men are included. select 2 of the fueding men out of two fueding men and then select 1 of the remaining 5 men, hence:
\[ \begin{pmatrix} 2 \\ 2 \end{pmatrix}\begin{pmatrix} 5 \\ 1 \end{pmatrix} =\frac{2!}{(2-2)!2!}\frac{5!}{(5-1)!1!} =\frac{1}{0!}\frac{5\bullet4!}{4!}=\frac{1}{1}(5)=5 \] There are only 5 ways to select groups of men inclusive of the fueding men, so we subtract this from all possible combinations to get
\[ (\begin{pmatrix} 7 \\ 3 \end{pmatrix}-\begin{pmatrix} 2 \\ 2 \end{pmatrix}\begin{pmatrix} 5 \\ 1 \end{pmatrix})(\begin{pmatrix} 5 \\ 2 \end{pmatrix})\\ (35-5)(10)\\ (30)(10)=300 \]
\[ (x+y)^{n}= \sum _{ k=0 }^{ n }{ \begin{pmatrix} n \\ k \end{pmatrix} } x^{k}y^{n-k} \]
In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. A binomial is simply an expression that is made up of the sum of two monomials. A monomial is a single term polynomial.
This formula is not something that came out of thin air. Lets look at the reasoning behind the formula.
\[ (a+b)^{n}=\\ (a+b)^{0}=1\\ (a+b)^{1}=a+b\\ (a+b)^{2}=(a+b)(a+b)=a^{2}+2ab+b^{2}\\ (a+b)^{3}= a^{2}+2ab+b^{2}(a+b)=a^{3}+3a^{2}b+3ab^{2}+b^{3}\\ (a+b)^{4}=a^{3}+3a^{2}b+3ab^{2}+b^{3}(a+b)=a^{4}+4a^{3}b+6a^{2}b^{2}+4ab^{3}+b^{4} \] Each iteration of (a+b) is going to get longer and longer,however a patter starts to emerge.
Lets look at just the exponents of any “a”, term by term. They are 4, 3, 2, 1. If we look at the exponents of just b, they are 1, 2, 3, 4. What are the coefficients of each term? They are 1,4,6,4,1
What does this all mean? In this case lets enumurate the exponents ofeach ab pair with b starting at 0 and a starting at 4.
\[ \begin{matrix} b_k=0 & b_k=1 & b_k=2 & b_k=3 & b_k=4 \\ { a }^{ 4 } & { a }^{ 3 } & { a }^{ 2 } & { a }^{ 1 } & { a }^{ 0 } \\ { b }^{ 0 } & { b }^{ 1 } & { b }^{ 2 } & { b }^{ 3 } & { b }^{ 4 } \\ { a }^{ 4 } & { a }^{ 3 }{ b } & { a }^{ 2 }{ b }^{ 2 } & { a{ b }^{ 3 } } & { b }^{ 4 } \end{matrix} \] We can see that if we let the exponent of b=0 and a=4 and then add 1 to the b exponent and subtract 1 from the a exponent, we can list all the terms that resulted in the expansion of (a+b) to the 4th power.
What about the coefficients?
pascalTriangle <- function(h)
{
for(i in 0:(h-1))
{
s <- ""
for(k in 0:(h-i)) s <- paste(s, " ", sep="")
for(j in 0:i) {
s <- paste(s, sprintf("%3d ", choose(i, j)), sep="")
}
print(s)
}
}
pascalTriangle(5)## [1] " 1 "
## [1] " 1 1 "
## [1] " 1 2 1 "
## [1] " 1 3 3 1 "
## [1] " 1 4 6 4 1 "The coefficients are actually each row of the pascal triangle. Each row pertains to each expansion starting at n=0.
All of these patters were put together into the binomial theorem. More formal proofs exist using methods such as proof by induction but they are out of the scope of this session.
Lets jump into problem solving using this theorem.
Expand the following:
\[ (x+y)^{3}=\sum _{ k=0 }^{ 3 }{ \begin{pmatrix} 3 \\ k \end{pmatrix} } x^{k}y^{3-k}\\ =\begin{pmatrix} 3 \\ 0 \end{pmatrix}x^{0}y^{3-0}+\begin{pmatrix} 3 \\ 1 \end{pmatrix}x^{1}y^{3-1} +\begin{pmatrix} 3 \\ 2 \end{pmatrix}x^{2}y^{3-2} +\begin{pmatrix} 3 \\ 3 \end{pmatrix}x^{3}y^{3-3}\\ =y^{3}+3xy^{2}+3x^{3}y+x^{3} \]
We will now consider the case of n objects divided into r groups. We should know that we consider n objects to be distinct. We can use multinomial coefficients to answer the question how many ways can we divide n distinct objects into r groups?
\[ n_1 + n_2 +...+n_r=n,\\ then\\ \begin{pmatrix} n \\ n_1, n_2,n_3, ..., n_r \end{pmatrix}=\frac{n!}{n_1 ! n_2 ! n_3 !...n_r} \] Hence, we can count how many ways we can divide n distinct objects into r groups where nr is the size of each sub group.
Lets apply this formula to solve an example.
ex) A police department in a small city consists of 10 officers. If the department policy is to have 5 of the officers patrolling the streets, 2 of the officers working full time at the station, and 3 of the officers on reserve at the station, how many different divisions of the 10 officers into the 3 groups are possible?
We have 10 distinct officers. We want to divide 10 distinct officers into a group of 5 officers on the streets, 2 officers at the station and, 3 officers on reserve.
\[ \frac{10!}{5!2!3!}=\frac{10\bullet 9\bullet8\bullet7\bullet6\bullet5!}{5!2!3!}=\frac{10\bullet 9\bullet8\bullet7\bullet6}{2\bullet1\bullet3\bullet2\bullet1}=2,520 \]
We will skip over counting the number of integer solutions to an equation since it is a very niche application of the multinomial theorem,however I encourage the student to read about it in the text.
Please do the following problems on page 15: q1 - q33 odd problems only
Please read chapter 1