Binomial expansion & combinatorics
Sal explains why we use the combinatorial formula for (n choose k) to expand binomial expressions. Created by Sal Khan.
Want to join the conversation?
- At3:17Sal gives 3 choose 3. This may be more of a question about the combinatorics formula, but 3!/3!(3-3)! should be undefined as it is 3*2*1/3*2*1(0), which I am simplifying as 1/0. Why does this become one for the coefficient? Is it something peculiar to combinatorics where an otherwise undefined fraction equals one?(25 votes)
- i have a question .. how do you find the remainder when 7^1993 is divided by 100 ?(6 votes)
- Good question.
First let's think of a way to solve this problem without actually computing that crazy number and then dividing it by a hundred. Let's take smaller numbers and see if we can find a pattern that we can exploit.
What is the remainder when 193 is divided by 100? 93. What is the remainder when 1057 is divided by 100? 57. We can see that the remainder when any number is divided by 100 is simply the last 2 digits (the tens digit and the units digit) of the number. Therefore, we have changed our problem to:
Find the units and tens digit of 7¹⁹⁹³.
Once again, let's see if we can find a pattern. Let's focus on the units digit for now. What is the units digit of the first few powers of 7?
7¹ → 7
7² → 9
7³ → 3
7⁴ → 1
7⁵ → 7
Aha! The units digit of powers of 7 repeat every four iterations! This means that the units digit of 7¹⁹⁹³ is either 7, 9, 3, or 1 which correspond to the units digit of 7¹, 7², 7³, and 7⁴. How do we figure out which of the four our number belongs to? Well we noticed that the units digits repeat in blocks of four. What happens when we divide 5 by 4? We get a remainder of 1. And 7⁵ has the same units digit as 7¹! How about 7⁶? 6 divided by 4 gives a remainder of 2. 7⁶ has the same units digit as 7²! Following this logic, 1993 divided by 4 gives a remainder of 1. Therefore 7¹⁹⁹³ must have the same units digit of 7¹ which is simply 7.
We figured out the units digit, now we can use the same method to find the tens digit.
7¹ → 0
7² → 4
7³ → 4
7⁴ → 0
7⁵ → 0
7⁶ → 4
7⁷ → 4
Our pattern here is 0, 4, 4, 0. Once again, we can see this as a block of 4. Dividing the exponent by 4 and having a remainder of 1 or 0 means the tens digit will be 0. Dividing the exponent by 4 and having a remainder of 2 or 3 means the tens digit will be 4. 1993 divided by 4 yields a remainder of 1. The tens digit is therefore 0.
With a tens digit of 0 and a units digit of 7, we see that the remainder when 7¹⁹⁹³ is divided by 100 is simply 7.
Comment if you have questions.(43 votes)
- What are the combinatorics?(10 votes)
- "Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics), deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and studying combinatorial structures arising in an algebraic context, or applying algebraic techniques to combinatorial problems (algebraic combinatorics)."
For more information and reference go here:
- It is easy to use this in combination with for example the coin toss problem. Since you can easily find all the probabilities.
For example, you have 3 coin tosses and you want to know the probability for having 0, 1, 2 or 3 heads. Since the coin is not fair, the probability to get heads is 70% and to get tails is therefore 30%.
(a + b) is then (.7 + .3)
We have 3 coin tosses, so the probabilities can be found by (.7 +.3)^3
Which is equal to:
1 * .7^3 * .3^0 + 3 * .7^2 * .3^1 + 3 * .7^1 * .3^2 + 1 * .7^0 * .3^3
This is equal to:
.343 + .441 + .189 + .027 = 1
In percentages this will be:
34.3% + 44.1% + 18.9% + 2.7% = 100%
3 heads = 34.3%
2 heads = 44.1%
1 heads = 18.9%
0 heads = 2.7%
You can of course choose any number for the amounts of tosses and any number for a and be if you have other probabilities.
Hopefully it is usefull for someone.(8 votes)
- Please can you provide guidance on how to determine the sign of the coefficient. If the equation is (a + b)^4 then all the signs will be positive, but what about (a - b)^4 or (-a + b)^4, etc. Many thanks.(4 votes)
- I'm kinda late but the method I use so that I don't have to memorize a bunch of rules for binomial expansions is for example (a-b)^n can be written as (a+c)^n where c=-b. So you can do it the normal way and then substitute c with -b after expanding the binomial and the signs will take care of themselves.
Hope this helps!(5 votes)
- What if you have something raised to a negative power? say for example (a+b) ^ -4(2 votes)
- You flip it over (reciprocate it) and raise it to the same power. (a+b)^-4 = 1/((a+b)^4).(5 votes)
- At4:14Sal said that 3 choose 2 = 3. I tried to count and the answer made sense, but the formula doesn't agree. n!/(n-r)! = 3!/(3-2)! = 6/1 = 6(2 votes)
- The formula is "n!/r!(n-r)!", not "n!/(n-r)!" so 3!/2!(3-2)! = 6/2(1) = 6/2 = 3(4 votes)
- At0:54, sal says there is only one way of getting y^0 but then proceeds to write 0 in the brackets. could anyone shed some light as to why this is so?
thank you.(2 votes)
- Combinations and combinatorics are same right?(1 vote)
- No. A combination is just a collection of things. Combinatorics is a branch of mathematics.(3 votes)
- At1:58Sal uses 3 choose 1 for how many x^2*y^1 terms there will be, why does he only have to chose the ys used and not the xs?(2 votes)
- The thing is that he does pick the X, you can see it in the first term it's x^3 and in the second term x^2 y^1, basically he can only choose 3, one from each expression (x + y).
He first took 3 X's, the second time he took 2 X's, so you can take 1 Y from one of the 3 expressions (which means 3 possibilities).
If he doesn't pick none Y, he'll have 3 X's.(1 vote)
Voiceover:What I want to do in this video is hopefully give more intuition as to why the binomial theorem or the binomial formula involves combinatorics. Let's just think about what this expansion would be. I'm just using a particular example that's pretty simple, x plus y to the third power which is x plus y, times x plus y, times x plus y. We already know what the terms look like, we could pick an x from each of these. If we pick exactly an x from each of these that's going to be our x to the third term, and we essentially picked no y [zen] because we picked an x from each of this when we multiplied out to get this term. How many ways are there to construct that? How many ways are there, if we're picking from three things. We're picking from three things, how many ways can we choose exactly zero y's of not picking a y? There's only one way to do that, there's only one possible way of doing that. By not picking a y from each of them or you can say by picking an x from each of them. The coefficient right over here is one x to the third. There's only one way, when you take this product out, only one of the terms initially is going to have an x to the third in it. Now, what about the next term? So plus. Now we're going to pick from three buckets but we want to pick one y. Another way of thinking about it you have three people or we have three people, this person, this person, and this person. One of them you're going to choose to be I guess be your friend that's another way of saying which of these are you going to pick the y from? This is the exact same thing as a combinatorics problem, from three things you are choosing one of them to be y. Of course three choose one, this is equal to three. If you're picking one y that means you're picking two x's, and you're taking the product of everything so it's x squared times y to the one and we could keep doing that logic, so plus. Now we're going to think about the situation where we are picking two y's out of three things. It's x to the first, y squared. We're starting with three things and we're going to pick two to two of this y's so it could be this y and this y to construct the product y. It could be y times y times that x or it could be y times y, times that x or it could be y times x, times y. This is three choose two, out of three things what are the different ways, what are the combinations of picking two things. If you have three friends how many combinations can you put two of them in your two seater car where you don't care about who sits in which seat. You're just thinking about how many different combinations can you pick from that and once again this evaluates to three and then finally, how many different ways from a set of three things, from three different things, so from each of these expressions, how many ways can you pick exactly three y's? Well there's only one way to do it, you pick this y, this y and that y. If you're picking three y's that means you picked zero x's and you have picked three y's. That's why we're dealing with combinatorics here. Three choose three. From three expressions, your three binomials, right over here that you are taking the product from you need to choose three y's, so you have to pick the second term in all of them. There's only one way to do that, here you want to pick the second term, the y term, in two of them, exactly two of them. Here you want to pick the y term in exactly one of them, there's one way to do this, three ways to do this, so there's three ways to do this, three ways to do this, one way to do that, one way to do that. This is one, this is three, when you evaluate, when you apply the formula for three choose and choose k, three and this is one.