[MUSIC] Another problem closely related to the previous one is the problem of counting integer compositions. We define integer composition, An integer composition, of n. Is a presentation of n as an ordered sum of positive integers is a presentation, Of n as an ordered, Sum. n = n1 + n2 + etc., plus nk where all, As an examples here are also positive integers, let us list all the compositions of the numbers 1, 2, 3, and 4. For any quote 1 there is nothing to decompose and there is only one such composition. 2 can be presented in two different ways, it is either 2 or 1 + 1. 3 is 2 + 1, or 1 + 2. I would like to emphasize once more that the conversations are defined as ordered sums. So 2 + 1 and 1 + 2 correspond to two different compositions. Or 3 can be represented as the sum of three 1s. We will be dealing unordered sums, later. And these sums are called partitions as opposed to compositions. But they will be discussed in lecture seven and they are somewhat more involved. Okay, what about 4? 4 is, a 4 or a 3 + 1. Or 1 + 3. And there is another way of presenting it as the sum of two sums. Label it 2 + 2, or this is 2 + 1 + 1, or it is 1 + 2 + 1, or 1 + 1 + 2, or 4 x 1. So we see that the number of partitions is 1 in this case. 2 in this case. 4 in this case, and 8 in this case, so it is a natural conjecture that the number of compositions of an integer k is a power of 2. Namely, 2 to the power of k- 1. And this will be one part of the theorem we are going to prove now. Theorem, a, the number of compositions, Of n is 2 to the power n- 1. Part b, consider the number of compositions with exactly k summands. And this number is equal to n- 1, choose k- 1. (n- 1), which is (k- 1). The proof we'll use the balls and boxes construction. So in this problem can be restated as follows. Suppose we have n balls which correspond to the number n and we want to put them into k boxes. In such a way that all n i's are positive. This means that no box is allowed to stay empty. The compositions, Of, n with the exactly k summands, Correspond to configurations. Of n balls inside, k boxes. Such that no box is empty. Such that each box is not empty. Why do you want to put n balls into k boxes? So I start each box as non-empty. This is the same as putting a ball into each box first. So this last condition will be satisfied automatically. And we're left with n minus k balls, which we need to put into k boxes in an arbitrary way, without other restrictions. And so this is the same as the number of configurations, Of n- k balls. In k boxes. And this number, as we know from the previous part, is n- k + k- 1. Choose the numbers of boxes minus 1. So, choose k- 1, and this nothing but n- 1 choose k- 1. Okay, and this was part b and to show that to the total number of compositions is 2 to the power n- 1. We just need to sum up these values, For all possible values of k so, This was part b and part a, the total number of compositions. Is, n-1 to 0 plus n-1 to 1 plus etc., plus the maximum number of summands in an integer composition is equal to n well, this corresponds to representation of n as 1. So, we sum this up to k equal to n. So this is, n- 1 choose n -1 and in the previous lecture we have found the value of this sum. This is the sum of entries in the n minus first row of the Pascal triangle. So this is 2 to the power of n- 1. This is the total number of compositions of a number. [MUSIC]
