Pascal's triangle & combinatorics
Sal shows how generating the values in Pascal's triangle is related to the combinatorial formula (n choose k). Created by Sal Khan.
Want to join the conversation?
- I'm trying to understand this and I've watched the previous videos, but it still makes no sense to me. Perhaps there's something I should know and I don't.
How did Pascal invent this? What are the foundations for this?(37 votes)
- The triangle is a simply an expression, or representation, of the following rule: starting at 1, make every number in the next the sum of the two numbers directly above it.
Although Pascal discovered it independently, it had been observed in many cultures (from all around the world) before him. He probably discovered it while toying with sums of series, of with the patterns of an arithmetic sequence.
Basically, it's a cool pattern that comes up a lot.(48 votes)
- This doesn't make sense to me..
'''(x+y)^3 = (x+y)(x+y)(x+y) = x^3+3x^2y+3xy^2+y^3'''
Now, Sal tried to tell us exactly why and how is Binomial Theorem connected to Combinatorics. According to him, to find the coefficient of x^3, we should find the number of ways in which we can choose 0 y's from 3 things, (x+y) , (x+y) and (x+y).. , which is given by 3C0=1.
*HOW?* First of all, what are we considering the "objects" here? (x+y)'s? or the individual x's and y's? Sal first comsidered the objects to be the (x+y)'s... and then while choosing the objects, he considered the objects to be the individual x's and y's.
Can someone help me please!!(9 votes)
- you may think one (x+y) is a bag of two slimes, one named x, the other named y
if you have 3 (x+y) bags, you have 3 x slimes and 3 y slimes in sum.
then all you need to do is pick one of the slimes from each bag and glue them together
= 1x^3 : pick 3 x slimes from all bags
+ 3x^2y^1 : pick 2 x slimes from 2 bags and 1 y from 1 bag
+ 3x^1y^2 : pick 1 x slime from 1 bag and 2 y slimes from 2 bags
+ 1y^3: pick 3 y slimes from 3 bags
= x^3 + 3x^2y + 3xy^2 + y^3
# on coefficients
1) 1 way to pick 3 x slimes from all bags:
x_bag1 x_bag2 x_bag3
2) 3 ways to pick 2 x slimes from 2 bags and 1 y from 1 bag:
x_bag1 x_bag2 y_bag3
x_bag1 y_bag2 x_bag3
y_bag1 x_bag2 x_bag3
3) 3 ways to pick 2 y slimes from 2 bags and 1 x from 1 bag:
y_bag1 y_bag2 x_bag3
y_bag1 x_bag2 y_bag3
x_bag1 y_bag2 y_bag3
4) 1 way to pick 3 y slimes from all bags:
y_bag1 y_bag2 y_bag3
hope you find this helpful(3 votes)
- ok so while constructing xy^2, we have to choose 2 y's out of 3...so that can be done in 3 ways.
but don't we have to also consider that we are choosing 1 x out of 3 x's ?(3 votes)
- Let's say that instead of focusing on the y's, we focused on the x's. If you had to choose 1 x out of 3, there are still only 3 ways it can be done. But when you choose only 1 x, you are also choosing 2 y's, because everything that isn't an x is a y. So let's say you chose the x out of the first set. You are also choosing the y out of the second and third set as well (because you're ultimately trying to make xy^2). If you chose any other x, you would also be choosing the y's out of the sets we didn't take an x out of, so there's still only three combinations.
Choosing 1 x is basically the same thing as choosing 2 y's when you're making xy^2, so there are no extra things to consider.(9 votes)
- Is there a video that shows that, and why, (n over k) is equivalent to (n over n-k)?(2 votes)
- I don't know if you still want to know the answer to this question or not, but I'll just post it in case someone else wants to know the answer to this question.
(n choose k) is basically the amount of ways that you can choose k people out of a group of n, if everybody is the same (order doesn't matter). So (5 choose 2) would be however many ways (10) you can choose two people out of a group of five. However, there are also 10 ways you could NOT choose 3 people, hence why (n choose k) is equal to (n choose n - k).
Hope this helps!(4 votes)
- Everyone is talking about Pascal but I don't know who that is. Can someone please enlighten me?(2 votes)
- Is there a solution or trick to questions with more terms like (a-x+w+s-g)^6?(2 votes)
- i don't think this is a trick, but you can treat (a-x+w+s) as a single term, so you'd do ((a-x+w+s)-g)^6. then you'll get some terms like (a-x+w+s)^6 or 6(a-x+w+s)^5(-g) or 15(a-x+w+s)^4(-g)^2... which eliminates g from being added/subtracted from the other variables.
then to simplify (a-x+w+s)^6 for example, treat (a-x+w) as a single term to get ((a-x+w)+s)^6, which gives you (a-x+w)^6+6(a-x+w)^5(s)+15(a-x+w)^4(s)^2...
repeat this until (a-x+w+s-g)^6 becomes a something like a^6-6ga^5+6sa^5+6wa^5-6xa^5... which is called expanded form because each term has variables multiplied individually rather than having factors like (a-x) or (w+s-g).
hope this helps.(2 votes)
- How to deal with TRINOMIAL expansions and N-NOMIAL expansions?(2 votes)
- I was not sure how to solve this question:
1-x/1+3x , IxI < 1/3(1 vote)
- This is an expression, and expressions are not solvable. If you make it a rational function, it will give y=(1-x)/((1+3x). This would have a vertical asymptote where denominator is 0, so 1+3x=0, subtract 1 and divide by 3, so it would be at x=-1/3. A horizontal asymptote (as x goes to infinity) would be at y=-1/3. The limitation of domain (?) |x|<1/3 would mean that either x < 1/3 or x>-1/3 which limits x to -1/3<x<1/3. As x approaches -1/3, y would approach infinity because this is dividing by 0. When x is 1/3, you get (1-1/3)/(1+3(1/3)) or (2/3)/2=1/3. So for the domain of |x|<1/3, the range would be y>1/3. Since I do not know what you are really asking, I can only guess how to answer it.(2 votes)
- I understand that using all "+" makes it easier to understand the concept but why doesn't he ever use "-" in his examples? Like (x-y)^3.(1 vote)
- You could treat (x-y)^3 as [x+(-y)]^3, treat x and (-y) as the variables when doing the binomial expansion, then simplify in the end. After simplifying, you should end up with alternating plus and minus signs in the terms.(2 votes)
- Is there a video where Sal proves the binomial formula (a+b)^n=a^n + nC1xa^(n-1) etc etc ? I noticed that he used something like it in similar videos.(1 vote)
Voiceover:What I want to do in this video is further connect our understanding of the binomial theorem. Two combinatorics, two Pascal's triangle. Just to review the ideas again, if we're taking x plus y to the third power and I'm just using this as an example that's a little bit easy to get around, get our heads around that's essentially taking three equivalent expressions and multiplying them by each other. You're taking x plus y, times x plus y, times x plus y. Let's call this the first x plus y, the second x plus y, and the third x plus y. If you're looking at the expansion of it and you're saying well how many ways can we construct x y squared or another way to think about it is you have these three expressions, you're going to choose two of them to contribute a y and take the product. For example, you could pick expression one and expression two to contribute the y. You could pick expression one and expression three to contribute the y, or you could take expression two and expression three to contribute the y. Of course the other expressions what's going to contribute to the x. You have three expressions and you're going to choose two to contribute the y and so that's why you have this combinatorics idea it's three choose two. It's the exact same mathematical problem, if you have three friends and you're choosing two to ride in a car with you, you don't care which sit they are going to sit in. You're just saying which two friends get to ride in my two seater or get to ride, what are the two friends that I'm going to pick? Same way here, out of three friends which are the two that I'm going to pick to contribute a y to this product and then the third is going to contribute an x. Now let's go to Pascal's triangle and hopefully see that this is actually a very similar idea. We could go to the same term, so the x y squared term, so that's right over there. Pascal's triangle, I always visualize it as a map. This is a node in the map and I think what are the different ways that I can get to this node on the map. I could have a y squared, and then multiplied by an x. Since we're multiplying an x that's why I made this line orange or I could have an x y and I could multiply by a blue so there's two immediate things above it that I can get to them but there's two ways to get to this one, there's one way to get to this one, and so the combined ways to get to this one is two plus one is equal to three. Just to make it the connection between what we just said, what's really going on here is at each of these nodes as we pick a path, we're essentially saying are we picking an x or y from each of these expressions. We number the expressions, let's number them here. Let's say this is expression one, this is expression two, this is expression three. We said that there's three paths that we could take us here, let's mark them out. There's this path, there's this path right over here that gets us there and that's equivalent to picking the x from expression one. Notice we picked the left hand side then we go to the right hand side. We pick the y from expression two, and then we pick the y from expression three, the last two, we pick the right path, we picked the blue path. That's essentially one way that we could choose two y's out of these three expressions. Once again, one way to choose two y's out of three expressions but we don't care about just that one, we care about all of the different paths. This was one way, another way would be to go like this. Pick a y from the first one, an x from the second one and a y from the third one. Or pick a y from the first expression, a y from the second expression and an x from the third expression. It's really a kind of fundamental mathematical level. It's solving the exact same problem. Hopefully this gives you a little intuition on why Pascal's triangle is connected to two combinatorics and why they're both useful for finding binomial expansions.