
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
 
 Comment:1 times 
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
Thus

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 subgroups 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 subgroups 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, , :
 Box   Box   Box   Number of ways 
    
    
    
    
    
    
    Total : 


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 subgroup 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 subgroups. (you aren’t required to distribute those subgroups 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 subgroups 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 nonidentical, 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 nonnegative 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 nonnegative 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
Note:
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 nonnegative 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 fivedigit 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


