[MUSIC] Here's another problem which often appears in combinatorics which is called balls in boxes and multisets. These are in fact, two various interpretations of the same problem. Okay, the setting is as follows. Suppose we have k balls, Which all looks the same. And suppose we have n boxes. And boxes are numbered, 1, 2, 3, okay, let's say, 4. And the question is, in how many ways can we put these k balls into n boxes? Note that in this problem there are no restrictions on the capacity of boxes. We can say, put any number of balls into each box or we can leave boxes empty or we can do whatever we want. Suppose that well, we are dealing with another version of this problem. Suppose that each box had the maximal capacity 1. So, if The maximal capacity Of each box is 1, Then, well, that means that we can put only 1 ball in each of the boxes or leave it empty. So, the answer would be, (n choose k) if n is greater than or equal to k and 0 otherwise. Because out of n boxes, we need to pick exactly k filled by balls with having a ball in it and the other boxes remain empty. Okay, and what if there are no restrictions on the capacity of boxes? What We'll get a solution of this problem in a couple of moments, but before that let me restate it in a different way. So, this problem of boxes of maximum capacity 1 can be treated as a problem of selecting a k element subset inside an n element set. And we have dealt with this problem last time and the answer is given by a binomial coefficient. And this problem with no restriction on the capacity of boxes is about something called multisets. Let me give a definition. Suppose that X is an arbitrary set. In our examples, X will be finite but this is not important. Definition, a multiset Is a function from X to non-negative integers. Is the function which I denote by mu. From X into Z greater than or equal to 0. The size of a multiset, Is the sum of values of this function mu over all values of X. The sum of mu(x), for small x belonging to the capital X. Well, this formal definition should be understood as follows. Suppose we have a set, let's say, x, or let's say, Let's pick a set just consisting of 4 elements. And, we pick something like a subset of this set, but the difference with subsets is that we are allowed to take each element not only once but a couple of times. Namely, we can take each element, mu(x) times. So, let's take 1 once, let's take 3, three times, and let's take 4 once. So in this case, the multiset shown on this picture will correspond to the function mu(1)=1, mu(2)=0, mu(3)=3, and mu(4)=1. So, the size of this multiset is 5. So, we have 5 elements in total. The size of mu is 5. Okay, it's clear that such a multiset corresponds to a mutiset of size k corresponds to configurations of k balls put inside n boxes. Well, if we take an element, mu(i) times this means that in our configuration of balls inside boxes we need to put mu(i) balls into the ith box. Namely, this configuration will correspond to 1 ball in the first box, the second box is empty, 3 balls are inside the third box and there is 1 ball inside the fourth box. So, we have put 5 balls inside 4 boxes. Okay, so the number of Of configurations of k balls. In n boxes corresponds to the number of multisets of an n element set of size k. Multisets Of {1, et cetera n} of Of size k. And now I will show how to compute this number and how it is related to binomial coefficients. [MUSIC]