Skip to main content
Loading Explore guides…
Combinatorics · Acedra
Home
Explore
Mathematics
Combinatorics
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
55 segments
Copy
Hide video
0:00
welcome back to Simple Quan today we will cover all of combinotaurics with the help of our good friend Bergamo let's get started today's video will be the first part in a 12-part series covering all of probability today we will be going over combinotaurics what are combinotaurics combinotaurics is the study of counting arranging and combining elements from a set and this forms a foundation of probability because how can you figure out
0:30
how probable an event is without knowing how many ways the event can occur combinotaurics helps us figure out the ways in which events can occur today's topics include basic counting permutations combinations partitions and we'll end with a complicated topic the multinnomial theorem overall this will give a comprehensive overview of all of combinatorics so to start what is basic counting so let's say Bergamo here has three possible main chicks and
1:15
four different side chicks the question we might get asked is how many main chick and side chick pairs are possible see if you can figure it out let's say we have our three different main chicks here and our four side chicks here let's say we start with this main chick how many ways can this one be paired with one of the side chicks well you can be paired with the blue one be paired
1:36
with the pink one be paired with the green one or can be paired with the gray one this gives us four possibilities this gives us four possible pairs starting with the blue main chick now what happens if we start with the green main chick let's see by the same logic the green main chick can either be paired with the blue one the pink one the green one or the gray one which again gives us four
2:02
possible possibilities for pairings including the green main chick and finally by the same logic if we look at the orange one she can be paired with again the blue the pink the green or the gray and that gives us one more time four more possibilities including the orange chick so in total we have 12 possible main chick side chick pairs for Bergama so how many main chick and side chick pairs are possible the answer is 12 now in general the basic principle of
2:38
counting is as follows if there are m outcomes for event A and N outcomes for event B there are m* N outcomes for event A and B this is the basic principle of counting so in our example we had three different outcomes for the main chick and four different outcomes for the side chick so our total outcomes of main chick and side chick equal 3 * 4 = 12 now here's a practice problem to try using the basic principle of counting there are eight waiters at a restaurant and
3:20
five steak options how many ways are there to order a steak from a waiter at this restaurant
3:29
well to start there are eight waiters and there are five stakes so using the basic principle of counting the amount of ways we can pair a waiter with a steak is 8 * 5 which gives us 40 total orderings 40 is the answer now for one more practice problem you have four different shirts 13 pairs of pants and three hats in your closet how many outfits can you make this problem again uses the basic principle of counting and the total number of outfits we can make is 4 * 13 * 3 which
4:12
gives us a total of 156 so from there we've now covered our first topic basic counting and we'll start with permutations next so permutations what is a permutation a permutation is a way in which a set of things can be ordered the main word here is being ordered so for example let's say we have Bergamo again with his chosen main chicken side chick let's consider this one ordering bergamo's
4:43
in front green dumpling is in the middle and pink egg roll is at the end a different permutation could be the green dumpling in front bergamo in the middle and the pink egg roll at the end or for a third example of a permutation we could have something like this the main distinction with the permutation is even if there's the same group of people or objects being chosen each time if they are ordered differently that means they are a different permutation so let's
5:10
look at a practice problem so how many ways are there to order these four people well to start let's give four different slots as ways that we can order them so we'd have the first person the second person the third person and the fourth person so for this first slot we can actually choose any one of these four people to be first so that gives us four possible options for the first slot now for the second slot there's only three people left after we chose that first one
5:41
so there's only three more options for people we can put in the second slot and by the same logic once we get to the third slot there's only two people left to put in the third slot and finally we only have one more choice of who we can put in the last slot if the other three have already been chosen there's only one left here then using the basic principle of counting that we discovered in part one we realize that we have four possibilities for first
6:08
place three for second place two for third and one for fourth which gives us a total of 4 * 3 * 2 * 1 total possibilities of ordering these four people which is 24 so our final definition for permutations is if if we have n objects there are n * n -1 * n -2 all the way down to one different permutations so if you look back at this problem we had 4 * 4 -1 * 4 - 2 all the way down to one that's how many permutations we had so by formal definition the number of
6:52
permutations is this product right here and that is called n factorial this symbol means factorial so what does a factorial mean it just means you start at n and multiply by each number decreasing by one until you get to one so some facts about factorials for example 3 factorial is 3 * 2 * 1 7 factorial is 7 * 6 * 5 * 4 all the way to 1 and then you can also treat 7 factorial as 7 * 6 factorial and finally just as a definition of factorials 0 factorial equals 1
7:40
so now let's try some permutation practice problems how many batting orders are there for a 9p person baseball team well we could treat this similarly to how we treated the ordering of our four friends so in the first slot there are nine possibilities because there's nine total people that we can put first and then after we put the first person there in the second slot we only have eight possibilities and in the third slot we only have seven and
8:08
so on until our last slot we only have one more possibility and clearly you can see that the number of possibilities is 9 * 8 * 7 all the way to 1 which is the same as 9 factorial now for another practice problem five men and four women are ranked by height if the men are ordered among themselves and women are ordered among themselves how many rankings are possible to start let's order them in so the ways we can order the men is five factorial it's the same as
8:47
the baseball and it's the same as the ordering four people there's just five people this time so there's five factorial ways to order the men and then to order the women there are four factorial ways to order the women same logic just four people instead then finally using our basic principle of counting the total number of permutations is 5 factorial * 4 factorial which ends up being 2,880 now there's one other type of problem that comes with permutations and this
9:21
question is how many ways are there to order a a b c now it's the same idea as before but now the one hiccup is sum of the people or the objects that we order are actually the same let's see how we can approach this problem so how many ways are there to order a a b c so one way to think about it is to label all the letters with subscripts and that now distinguishes our a's and it turns into the
9:50
problem we had before if a1 and a2 are different letters then we should have five factorial total combinations as figured out in previous problems but the issue here is that they're not labeled and that they are the same thing so what happens now well that basically implies a different permutation such as this one now equals this one because if you get rid of those little subscripts these two permutations are the same thing and also these two are also the same thing
10:30
if you get rid of all the subscripts these all lead to only one permutation which is this one so how can you figure out how many of these permutations lead back to the same permutation well if you look here essentially these two are the same permutation except you swapped the A's how many ways are there to swap these two A's well there's two factorial ways to swap these two A's and same thing goes for the C's so for example these
11:08
two permutations are exactly the same except you swapped this C4 and this C5 how many ways are there to order the C4 and the C5 well that's also two factorial the number of redundant permutations boils down to the number of ways to swap around the identical symbols and the number of ways to swap around the identical symbols is the number of symbols factorial so in our case since we had two repeating A's and two repeating C's we took the five factorial total
11:51
permutations and each one turned into four and these four permutations arose because we divided five factorial by the number of A's factorial times the number of B's factorial time the number of C's factorial so our solution is 5 factorial over 2 factorial * 1 factorial * 2 factorial and these are all the parts of this solution so we had the total number of permutations the number of identical A's the number of identical B's and the number of identical C's in general if there
12:32
are n objects of which N1 are identical so for example in our problem we had five objects in which two of the A's are identical n2 one of the B's are identical or NR that's just continuing but in our case it was N3 and there was two identical C's the total number of permutations is N factorial over N1 factorial N2 factorial and so on until you get to nr factorial now let's try a practice problem how many letter arrangements can be formed with the word probability ities
13:17
so to start if our letters were all different we'd have 13 factorial total permutations we have some repeating letters so let's figure out which letters are repeated we have one P one R one O two B's one A three I's one L one T one E and one S so our final answer we have to divide by the repeated characters so our final answer will be 13 factorial over 1 factorial 1 factorial 1 factorial 2 factorial 1 factorial 3 factorial 1 factorial 1 factorial 1 factorial 1
14:05
factorial and this can be simplified into 15 factorial over 12 so that's our final answer that concludes our coverage of permutations and we will now move on to combinations what is a combination a combination is the number of groups of R objects that can be formed from a total of n objects now that sounds kind of confusing but it's very similar to permutations the main difference is that in permutations these two orderings would be considered different in
14:44
combinations these two orderings are actually the same thing it doesn't matter how the people are ordered as long as the same people are chosen so while these two are the same in combinations terms these two are not the same combination because they include different people so let's take a look at a practice problem and see if that helps us out so how many ways are there to choose three people
15:12
from these four people and each way we choose three people is called a combination so to start we have three possible people to pick and the first person to pick can be one of any of these four people so that gives us four options for the first person now for the second person since we already picked someone we have three people left that gives us three people and finally for the third person we've already picked two people so we only have two people left so by permutation
15:44
logic that means we have 24 permutations of people to choose but that's not including the duplicate combinations because we could pick green dumpling first bow bun second and egg roll third and that would count as a permutation but that would be exactly the same as picking bow bun first green dumpling second and egg roll third so we got to figure out how many of these combinations are redundant so we know there are 4 * 3 * 2 total permutations of three people now our question is
16:20
how many of these are redundant let's say we have bow bun dumpling and egg roll in this order that counts as a permutation but how many ways can we order these three cuz ordering these three all count as the same combination so how many of these are actually the same well any one of these can swap places with any of the other ones and that gives us a total of three factorial total ways to order these three people so out of our 4 * 3 * 2 total possibilities 3 factorial are actually
16:57
redundant so this is our answer this is how many ways we can choose three people out of the four so in our example we chose 4 * 3 * 2 over 3 factorial and this equation holds in general as well in general the number of ways to choose r people out of n objects is n * n -1 * n - r + 1 / r factorial and then through a little bit of simplification we can take that term and multiply by one which is
17:31
this thing right here and that simplifies to our general case for n choose r which is n factorial n - r factorial over r factorial so given n choose r which is symbolized as this choosing r objects out of n total objects the total number of combinations to choose if taken in groups of r is n choose r= n factorial over n minus r factorial * r factorial and this is one of the most useful equations in all of probability so as a practice problem what is 100 choose 47 simply using
18:12
this equation our solution should then be 100 factorial over 100 - 47 factorial * 47 factorial now for another example there are six fathers and eight mothers in a school how many different two father three mother committees can be formed so for this problem we first choose a combination of fathers and then a combination of mothers so for the fathers we have six fathers and we're choosing two that's the combinations of fathers
18:57
and then for the mothers we then have 8 choose three which is a combination of mothers and then using the basic principle of counting the total number of committees that we can form is 6 choose 2 * 8 choose 3 that concludes our overview of combinations so we've now covered basic counting permutations and combinations and we'll now move on to partitions so what is a partition a partition is dividing a set of elements into subsets so basically
19:39
it's what it sounds like you take a group of elements and you split them and you partition them into different groups so for example let's imagine that there are eight different fish jiggle Bob is kind of fat so he wants to eat four fish max and Reagan each are normal and they only eat two fish now our question is how many ways can you group these eight different fish into distinct groups of four two and two so how many ways are there to give Jiggle Bob four fish Max two fish
20:11
and Reagan two fish well here's one way to think about it let's label all of our fish A B C D E G H now each grouping of fish that we give to Jiggle Bob Max and Reagan can actually be listed as an eight letter sequence so for example we could have A B C D E F G H now that gives these three people each the amount of fish that they want and it's an easy way to keep track of how many orderings
20:40
we can have so using this logic the total number of permutations of fish that we can give away is the number of ways to order these eight letters which is 8 factorial total possibilities the next thing we have to consider though is how many of these possibilities are redundant cuz again if we have a b c d e f this is actually the same ordering as b a c d efgh cuz jiggle bob still gets the same exact fish so how can we count for those redundant possibilities well it's similar
21:13
to the previous problem we did ordering a A B C basically these four letters can be swapped around in four factorial different ways and the same goes for these two they can be swapped around in two factorial and these ones can be swapped around in two factorial different ways so for each permutation each of these eight total possibilities 4 * 2 factorial * 2 factorial possibilities are actually redundant so our final answer to this question is actually 8 factorial
21:49
over 4 factorial * 2 factorial * 2 factorial so that's one type of partition problem the second type of partition problem utilizes a method called stars and bars so the stars and bars method is as follows how many ways can you put 12 balls into these three bins well one way to do this is to actually separate these balls with bars and then say these four go to A these four go to B and these four go to C or for a different orientation or for a different orientation you
22:25
might put the bar here and here you have two balls go to A six six balls go to B and four balls go to C now what this problem boils down to is actually the number of ways to order these 12 balls and two bars so we actually have 14 total objects and we have 14 slots to put all these objects so now we have 14 slots for 14 different objects now how many ways can we separate these objects well the answer is to actually see how many ways we can put the 12 balls in the 14 slots which is
23:06
14 choose 12 that's our solution this method is called the stars and bars method because often times you won't see problems with just balls but you can have any object and if you split them into a numbered amount of groups you can use this method so in general the stars and bars method states that if you split n items into k groups of unknown size this can be represented as splitting n stars with k bars which has a solution of n + k minus one / n so in our case we had 12 stars we
23:52
had three groups and that led to a total of 12 + 3 - 1 over 12 different groupings now let's try a practice problem how many non- negative sequences of a1 through a4 satisfy a1 + a2 + a3 + a4 equals 27 now this might be tricky at first but this is just another way of saying how can we split 27 into four groups this is again stars and bars with 27 stars and four groups
24:32
so that gives us a final answer of 27 + 4 - 1 over 27 we've now successfully covered basic counting permutations combinations and partitions and we'll finish with a challenging topic multinomial theorem before we get before we get to the multinnomial theorem let's start with the binomial theorem which is slightly simplified version so a binomial is defined as the polomial of two terms raised to any n
25:07
power now the goal of the binomial theorem is to find a general formula that can be used to write the expansion of any of these such binomials let's start by trying to figure out x + y cubed let's see where that gets us so first let's look at something like this where we have three different terms and all the variables are distinguished so we have x1 y1 x2 y2 x3 and y3 when we multiply these three terms out we end up with these eight terms x1 x2 x3 x1 x2 y3 and so on
25:46
now we realize these eight terms are actually the sum of all the ways that we can choose one variable from each of these three terms now let's see how that's useful so if we figure out x + y cubed that's the same as what we just did but removing all the subscripts so now this would be be an x cubed and this would be an x x2 y and so on from here now we can group the like terms and get our final answer so we have one x cubed term we have three x^2 y terms we
26:30
have 3 x y^2 terms and one y cubed term so our final answer is x cub + 3 x^2 y + 3 x y^2 + y cubed so what's one thing we notice we notice that each of these terms all are length three before we simplify we have three variables in each of these terms the number of x squar y's is the same as the number of ways to put two x's in three slots so there's actually 3 choose 2 x^2 ys and by the same logic there's actually 3 choose 1 x y^2 which is the number of ways you can put one
27:23
x in three slots and lastly the x cubed is the same as 3 choose 3 which is how many ways can you put three x's in three slots which is just one and the same with the y cubed how many ways can you put zero x's in three slots that's also one so what we notice is that the coefficient for each of the final terms in our polomial is actually the number of ways to choose the number of x's out of the total length which is three in general the binomial theorem is defined as follows
28:04
x + y to the n equals the sum of k = 0 to the n of n choose k * x k * y nus k so for example if we had x + y cubed is 3 choose 0 * y cubed 3 choose 1 * x y^ 2 3 choose 2 * x^2 y + 3 choose 3 x cubed and that was our original solution I cubed this is 3x y^2 3 x^2 y and x cubed so now that we understand the binomial theorem we now move on to the multinnomial theorem which is simply the binomial theorem in higher dimensions so what does that mean the multinnomial
28:59
for example could be something like a + b + c to the 4th there are just more than two terms in the parenthesis now what's a way that we can find a general formula for this type of problem well to start how many terms are in a + b + c to the 4th well the number of terms is the number of ways that we can choose one variable from each of these four terms and that ends up being 81 because there are three variables we can choose from the first term three
29:34
from the second term three from the third term and three from the fourth term and that gives us a total of 3 to the 4th which equals 81 we know one of the terms in our final polomial will have this variable at the end a^ 2 b c how many of those a squar bc terms will we have well if we look at the expansion right here the number of a^ squ bc terms is actually the number of ways to choose two a's a b and a c from these
30:18
four terms now how many ways are there to do that well that's the same thing as saying if we have four spots right here how many ways can we split four spots into two A's one B and one C this once again turns into the permutation problem we had where we figured out how many ways we could write a A B C or it's also the same as that problem we did where we split fish among Jiggle Bob Max
30:52
and Reagan what ends up happening is we have four factorial total options for organizing A's B's and C's in a row such as A B A C or B A C A and all such permutations there's four factorial of those however once again we might end up with some duplicate permutations such as A B A C again we want to figure out how many of them are redundant and not count those the number of ways to split four spots into 2 A's 1 B and 1 C is actually four factorial over 2 factorial * 1 factorial * 1
31:34
factorial so the coefficient term that goes in front of this is actually this term right here
31:43
and if we continue that for all of these terms we'll end up with this as our final polomial as you can see if we add together all these coefficients the total is 81 which is the number of four sequence terms we had figured out initially so to conclude what is the general form of the multinnomial theorem well given that we have x1 + x2 + x3 all the way to xr to the n which is a multinnomial this number can be expanded as the sum of all possible n1 n2s all
32:19
the way to nr that add up to n of n factorial divided by n1 factorial n2 factorial all the way to nr factorial this is the term we figured out earlier is the coefficient times whatever variable we have at the end which is x1 to the n1 x2 to the n2 all the way to the xr to the nr so now having covered multinnomial theorem one of the hardest topics in all of combinotaurics that concludes our full overview of combinotaurics i hope you enjoyed please leave any comments
33:05
below if you have any questions i'll be sure to answer them thank you so much for watching and if you want more videos like this in the future please consider subscribing thank you very much
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat