A composition of a natural number is a sequence of non-zero integers which add up to . How many compositions of exist?
Let us make the question more clear by taking a particular example for , say .
As described in the question, the compositions of will be which are in number.
Observe carefully the compositions listed out. How can we characterize each of these compositions mathematically? Recall the problem of finding the number of non-negative solutions of the integral equation where each solution corresponded to a unique permutation of “ “symbols and “” symbols. Can we do something like that here? In other words, can we represent each composition in another form whose permutations are easier to count?
It turns out that we can, as follows:
On the right hand side, we have “”s and thus blank spaces between the “” s. We can insert “” signs in these blank spaces; each different arrangement of “” signs in these blank spaces will correspond to a different composition.
To count the number of these arrangements, we proceed as follows: For each blank space, we have options, we can either insert or not insert a “” sign into that space. There are blank spaces; so the total number of all arrangements of “” signs in the blank spaces is (which is the number of compositions we already listed out).
In the general case, we will have blank spaces and options for each such blank space. Thus, the total number of ways in which we can arrange “” signs in these blank spaces, and therefore, the total number of compositions, will be
Prove logically the following assertion:
Suppose that we have to form a string of length , consisting of only letters from the set . Thus, we have options to fill any particular place in the string: We fill that place with either , or . Thus the total number of different strings of length would be
We now approach the task of formation of these strings from a different perspective.
Suppose that our string contains a total of “” s. How many such strings will exist? We first select places out of which we will fill with “”. This can be done in ways. For each of the remaining places, we have two options; we either fill it with “” or “”. Thus, the number of strings containing “” s will be .
Now we vary from to and thus get the total number of strings as
balls are to be placed in boxes. Each box can hold all the balls. In how many ways can we place the balls into the boxes so that no box remains empty, if
(a) balls and boxes are all different
(b) balls are identical but boxes are different
(c) balls are different but boxes are identical
(d) balls as well as boxes are identical
(e) balls as well as boxes are identical, but the boxes are kept in a row.
One of the constraints that should always be satisfied is that no box should remain empty. Thus, each box should get at least one ball. This means that the distribution of balls can have the configuration or . Only in these two configurations does no box remain empty.
In this case, the balls and the boxes are all different. If you observe carefully, you will note that this case is equivalent to dealing cards to players. Here, we are dealing balls (all different) into boxes (all different). In the card game, we were dealing cards (all different) to players (all different).
Suppose we distribute the balls in the configuration . We first divide the group of balls into this configuration. This can be done in ways since we just need to select a group of balls and our division will be accomplished. Once the division of the group of balls into -subgroups in the configuration has been done, we can permute the sub-groups among the different boxes in ways.
Thus, the number of ways to achieve the configuration is
We now find the number of ways to achieve the configuration .
We first select balls out of the which can be done in ways. We then select balls from the remaining , which can be done in ways. Thus simple division into the configuration can be achieved in ways. Division by is required since two subgroups are of the same size and right now we are just dividing into sub groups so the order to the sub-groups doesn’t matter. Once division has been accomplished, we permute the subgroups so formed amongst the different boxes is ways.
Thus, the number of ways to achieve the configuration is
The total number of ways is
To make things more clear, let us list down in detail the various configurations possible for the different boxes, , :
Number of ways
The balls are now identical so it doesn’t matter which ball goes into which box. What matters is only the configuration of the distribution.
By simple enumeration, only configurations exist for this case. (The notation implies that Box – has a balls, Box – has balls and Box – has balls.)
Thus, possible ways exist for this case
The boxes are identical. This means that it does not matter which sub-group of balls you put in which box. What matters is only the division of the group of balls. This case is akin to the one where you have to divide a deck of cards into sub-groups. (you aren’t required to distribute those sub-groups to players).
For the configuration , the number of ways of division is (we just choose balls out the and the division is automatically accomplished. For the configuration the number of ways of division is (division by is required since two sub-groups are of the same size, and here the order of the group doesn’t matter)
Thus, the total number of ways is
This case is quite straightforward. The balls are identical. The boxes are identical too. The only possible configuration are and . There can be no permutation of these configurations since the boxes are indistinguishable. Thus, only ways of division exist.
If we keep the boxes in a row, we have inherently ordered them and made them non-identical, since the boxes can be numbered now.
Therefore, in this case, the balls are identical but the boxes are different so this question becomes the same as the one in part – (b)
We have identical balls available with us which we need to be distributed amongst boys , and such that always gets an even number of balls. How many ways of doing so are possible?
The only constraint is that should get an even number of balls. There’s no constraint on the minimum number of balls a boy should get. This means that a boy can also not be given any ball.
We can represent the number of balls given to by since must get an even number of balls. If we represent the number of balls given to and by and , we should have
This means that to find the number of distributions possible, we find the number of non-negative integral solutions to the equation .
Note that can take a maximum value of and a minimum value of .
We rearrange so that we get an integral equation with and as variables, treating as a constant
The number of non-negative integer solutions of is
We now add the number of solutions so obtained for all the possible values of . The total number of solutions is therefore
An alert reader must have noticed that we can form arbitrarily complex integer equations. For example, what do we do if we intend to find out the number of non-negative integer solutions to the equation
where the are integers that are not necessarily equal to unity.
In addition, what if we impose constraints on the themselves say, we define an upper and lower bound for , i.e
For example, how do we distribute apples among boys such that each boy gets more than apples but less that apples, in addition to the constraint that one of the boys, say , must always get an even number of apples? Think about it. We will revisit the problem of such general integral equations in example – and in the chapter on Binomial Theorem. There we’ll learn to solve such problems using the Multinomial theorem.
Find the sum of the divisors of . Generalise the result for an arbitrary natural number .
The divisors of are listed out below:
The sum of these divisors is . We have to determine an elegant way to deduce this sum because we cannot repeat everytime the procedure of listing down all the factors and summing them.
For this purpose, we again resort to the use of the prime factorization form.
The sum of the divisors will be
This notation is simply a shorthand which implies that we vary the integral indices , and (in their respective allowed ranges) and this way we will have listed down all the factors and hence evaluated the required sum.
To generate the expression for the sum , we can alternatively use the following method:
Did you realize the trick? Writing this way also gives rise to all the factors. You are urged to convince yourself about this by expanding this expression and observing that all possible factors will be generated.
Thus, can now be simply evaluated as follows:
This is the same result that we got earlier!
To do the general case, assume that the prime factorization form of is
where the are all positive integers and the s are all primes. The sum of all the factors will be
Find the sum of all the five-digit numbers that can be formed using the digits , , , and if no digit is repeated.
This problem can be solved very easily if we view it from an individual digit’s perspective. Suppose that we only consider the digit “”. How many numbers will there be with “” in the units place?
From these numbers, what is the total contribution of the digit “” to the sum we are required to calculate? Since “” is at the units place and it occurs times, its contribution will be
Similarly, there will be numbers where “” is at the tens place. The total contribution of “” from these numbers will be
Proceeding in this way, we see that the total contribution of the digit “” from all the numbers that can be possibly formed is:
This is the contribution to the sum from only the digit “”. To calculate the entire sum , we calculate the contributions from all the five digits. Thus, the sum is