Let's consider the following problem. We have now unlimited supply of tomatoes, bell peppers, lettuce, and eggplants. So we want to make a salad out of 7 units among these four ingredients. Again, we do not have to use all ingredients, we just have to pick 7 units among them. How many different salads we can make? Okay, we can use recursive counting here as well as in the previous problem. But now we would like to obtain a formula, and this will be a general solution. Our solution will work for any number of ingredients and any size of salad. Okay, so here is the picture again. Now tomato is red, bell pepper is yellow, lettuce is green, and eggplant is purple. Okay now, we have cell ingredients, here is an example of salad, but note again, that the order doesn't matter. So for our convenience, let's just list the tomatoes first, then bell peppers, then lettuce, then eggplants. So here's our salad. The solution to the problem in nontrivial, so we will break it down to several simple ideas. Okay, the first idea. What information do we need to specify the list of ingredients, what is enough? Okay, it turns out that it is enough to say where on this list we switch from tomatoes to bell peppers. Where in this list we switch from bell peppers to lettuce, and where we switch from lettuce to eggplant. So we can mark this places, and then this is enough information, we can forget about colors. Now we do not need colors, we can construct them from what is on the picture. Okay, next, second idea. We do not even need these text descriptions for tomatoes, bell peppers, and eggplants. We can remove them, because we know that this first place corresponds to the switch from tomatoes to bell peppers. We have ordered ingredients in this way. The second correspond to switch from bell peppers to lettuce, and the last one from lettuce to eggplant. Okay, and finally we've heard the idea. We can represent these places of switches by some special signs, some delimiter signs. Let's do it, okay? We have done this. So now we have the first delimiter between tomatoes and bell peppers is after the second ingredient. Then the next delimiter is between bell peppers and lettuce, and the last delimiter is between lettuce and eggplant. Okay, and note again, that the salad can be still restored from the current picture. We can just color the ingredients as we described before, and we would restore the original salad from this picture. Let's do a small thing check right now. What happens if in our salad there are no say, bell peppers? So will the picture make sense? So how will it look like? Can we present such a salad with such a picture? It turns out that this is fine. We will have a picture just to have a picture like this. The first and the second delimiter will be right next to each other. There are no ingredients in between of them, so in case of this particle or picture we have several, we have two tomatoes, three lettuce, and two eggplants. So this is fine, our pictures still represent such salad. Okay, now let's proceed to the proof. What do we need to specify, to give, to fix a particular salad? Okay, now it turns out that this is simple. We need just to specify where to place three delimiters among these two positions. If we specify three delimiters there, then our salad is ready. Okay, and these are exact combinations. So we have 10 possible options, and we have to pick three out of them without order, so our answer here isn't just choose three, which is 120. Note that this is 120 not 120 for. So the answer to the problem is 120. Okay, let's review how we got there. Here is the original problem and let's review our main ideas. First, order salad in a convenient way. Order doesn't matter. So we can order the ingredients in a way we like. So it turned out to be very useful. Next, salad can be determined by the delimiters between types of ingredients. So introduce delimiters, and once we introduce them, we do not have to provide any more information. We have delimiters, we know where ingredients change. And final idea is to place delimiters in the line of our ingredients. And then we have a list of 10 options, seven units plus three delimiters, and we have to pick three delimiters in one of them. And that's what we already know how to do. So if you consider number of combinations of size k out of n object with repetitions, then the number of such combinations is equal to k + n- 1, choose n- 1. So here is the connection to the previous problem, size of the combinations is size of the salad. Number of objects is the number of ingredients, and the same argument works. So just our previous argument was general, so we can substitute 7 and 4 by k and n, and just the same proof works. Let's just recollect briefly why we have k + n- 1 here and n- 1. Why not, for example, k + n and n, just so it looks natural, but instead we have k + n- 1 and n- 1. So recall that n ingredients in the salad mean, that we need to place n- 1 delimiters between them. So here is where n- 1 comes from. So in the end of a solution we will have to choose n- 1 positions in the line of k + n- 1 elements. K stands for the size of a salad for the number of units of ingredients in the salad, and n- 1 is the number of delimiters. Okay, now let's get back to our table we had in the beginning of this lesson. We can consider different variations of sections of k items out of n possible options. And so, there are several variations. There are ordered and unordered selections. There are selections with repetitions and without repetitions. Let's briefly review them. So ordered selections with repetitions are just tuples, there are n to the k of them. Next, ordered selections without repetitions are k permutations where n factorial divided by n- k factorial of them. Then we proceed to unordered selections, unordered selection without repetitions. There are combinations and there are choose k of n, and in this lesson we consider the final sale of this table unordered selection with repetition, and it turns out by no known efficients help here as well. So the number of combinations with repetitions is equal to k + n -1, choose n -1. [SOUND] [MUSIC]