Permutations and Combinations – Counting the number of solutions of an integral equation

For this article, by an integer equation we will mean an equation of the form

x_1+x_2+x_3+ \ldots + x_n = k

where all the x_1,x_2, \ldots ,x_n, k are integers. In addition, we can impose more constraints on these variables. For example, all the x_i‘s are non-negative, or 3 < x_3 < 11, or whatever appropriate constraints that are possible for integral variables.

The problem that we are concerned with in this article is finding the number of non-negative solutions to an integer equation, a problem that is encountered very frequently in the subject of permutations and combinations in different guises. Lets take an example on an integer equation and list down some of its non-negative solutions.

x_1 + x_ 2 + x_3 = 8
(0,0,8)

(1,2,5)

(3,3,2)

(7,1,0)

etc.

Why do we care about counting the non-negative solutions to an integer equation? Why is this particular problem so important? Well, because it crops up in so many different kinds of problems, which may seem seemingly unrelated.

     Problem: 1

Suppose that a person goes to a soft-drinks shop with an empty crate which can store 24 bottles. There are 4 brands of soft-drinks available at the shop: Coke, Pepsi, Sprite and Dew. In how many ways can the person fill up the crate?

Solution

Lets represent the number of Coke bottles the person buys with x_{Coke}. Similarly, we will have x_{Pepsi}, x_{Sprite} and x_{Dew}. The total number of bottles to be filled is 24. Also, the number of bottles for each brand will obviously be a non-negative integer (it can be 0, which means no bottle from that brand). Thus, to count the number of ways to fill up the crate, we simply count the number of non-negative solutions to the integer equation:

x_{Coke} + x_{Pepsi} + x_{Sprite} + x_{Dew}=24
     Example: 2

Suppose that a person has n identical rolling dice (a rolling die is a perfect cube with faces marked 1 to 6) which he rolls at once. How many distinct throws are possible in this scenario?

Solution

Ok, this is another really interesting problem, and lets see how it reduces to finding the number of non-negative solutions to an integer equation. Note that the dice are identical, which means that there is no way to distinguish between two dice. When n such dice are rolled simultaneously, how can the outcome be described in words? Since we cannot distinguish between any two dice, we cannot talk about the outcomes on particular dices. All we can say is that we obtained these many “1“s, these many “2“s, these many “3“s, and so on, with the total number of outcomes being n, since there are n dice.

Now, suppose that when the n dice are rolled simultaneously, x_1 represents the number of “1“s obtained, x_2 represents the number of “2“s obtained, and so on. This, to count the number of distinct throws, all we have to do is to calculate the number of non-negative solutions to the integer equation:

x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = n

Now that we have seen why the general problem we are talking about is important, let us begin talking about how actually to solve that problem. For that, we first recall a basic formula from the theory on permutations and combinations:

Let there be a total of n objects, of which n_1 are identical and of one kind, n_2 are identical and of another kind, and so on, up to n_k. Thus, we’ll have n_1 + n_2 + \ldots + n_k = n. The number of permutations of these n objects taken all at a time is given by

\dfrac{n!}{n_1! n_2! \ldots n_k!}

Thus, for example, if we consider the string aaaaaaabbbbb, which has 7 a symbols and 5 b symbols, which means a total of 12 symbols, the number of permutations of this string is \dfrac{12!}{7! 5!}.

Coming back to our integer equation, we take a particular example again, one we have already taken, and find the number of its non-negative solutions.

x_1 + x_2 + x_3 = 8

We take a particular non-negative solution to this equation, say (1,2,5) and analyze it more closely. We break-up this solution and write it as follows:

1 + 2 + 5 = 8
1 + 1 1 + 1 1 1 1 1 = 8

Similarly, the particular solution (3,3,2) can be written as:

3 + 3 + 2 = 8
1 1 1 + 1 1 1 + 1 1 = 8

while the particular solution (0,0,8) can be written as:

0 + 0 + 8 = 8
+ + 1 1 1 1 1 1 1 1 = 8

The pattern that we observe is that each solution can be expressed as a string of 10 symbols, consisting of 81” symbols and 2+” symbols. Convince yourself about this point. Take any particular solution and break it up as we have described. You will obtain a string of 10 symbols of which 8 are “1” and 2 are “+“. Thus, every solution can be described by such a string, and every such string corresponds to a non-negative solution. That is, there is a one-to-one correspondence between the set of solutions and the set of such strings. In other words, to count the required number of solutions, we simple count the number of strings with 10 symbols, 8 of them identical and of one kind, and 2 of them identical and of another kind. The required number of solutions is therefore \dfrac{10!}{8! 2!}

If you are not clear about the reasoning process, it is imperative that you go through it again before proceeding on. Now let us generalize this example to the general integer equation:

x_1 + x_2 + x_3 + \ldots + x_n = k

In this case, once we break-up any particular solution, we will have a total of k1” symbols, and n-1+” symbols. Verify this yourself by comparing it with the particular example we took above. Thus, each particular solution can be represented by a string with of length n + k -1, consisting of k1” symbols and n-1+” symbols. The number of permutations of this string will be \dfrac{(n+k-1)!}{k!(n-1)!} or ^{n+k-1}C_k. This is also the required number of solutions.

We are now in a position to calculate the final answers to the two problems above. For Problem-1, n = 4 and k = 24, and so the required answer is ^{27}C_4. For Problem-2, the answer is ^{n+5}C_5.

14 comments
cvryn7
cvryn7

found one more way for solving equations with constraints.... i can't write whole stuff here as it contains summation symbols etc.. REFER to DISCRETE MATHEMATICS AND ITS APPLICATION by kenneth h rosen .. page no. 446  chapter ADVANCED COUNTING TECHNIQUES ...part 6.6 applications of inclusion-exclusion. ... and yes 446 pg for edition 7 

cvryn7
cvryn7

how we can solve this in case of constraints ??

cuemath
cuemath moderator

 @cvryn7 Let the equation be ax1+bx2+cx3=r.....in that case, you can evaluate the coefficient of x^r in the expression (1+x^a+x^2a+x^3a......)(1+x^b+x^2b+x^3b......)(1+x^c+x^2c+x^3c......) to ensure that the "contribution" from different brackets are multiples of a, b and c respectively. 

 

Suppose you have an equation x1+x2+x3=r, and the constraint is that p<= x1 <=q. In that case, you can evaluate the coefficient of x^r in (x^p+x^(p+1)+....x^q)(1+x+x^2+.....)(1+x+x^2+.....). This ensures that the contribution from the first bracket is between p and q.  

cvryn7
cvryn7

 @cuemath is x total number of x's?? ....i m trying to understand ur solution... little hard for me...can u elaborate a litttle?? thanx for fast reply.

 

cuemath
cuemath moderator

 @cvryn7 On the right hand side of the integer equation, you have r. That means the sum of all the variable terms on the left should come out to be r. Since the contribution is being measured in terms of powers of x, you calculate the coefficient of x^r - that gives you the number of ways in which x^r is formed - or equivalently, the number of ways in which you can generate a sum of r by the variable terms on the left. 

cvryn7
cvryn7

 @cuemath got it thnks...... :) .... now one more doubt.....why we find coefficient of x^r? .. rest is clear to me..

cvryn7
cvryn7

 @cuemath thnks dude....waiting.. actually problem is that.. i m not able understand that .. you can evalutate the coefficient of x^r in (x^p+x^(p+1).....+x^q)(....)(.....)        ...and what is x^r???? help me..

cuemath
cuemath moderator

 @cvryn7 No, it cannot be solved by a straightforward binomial approach. I'm posting an example in a bit. 

cvryn7
cvryn7

 @cuemath are you solving all this using binomial?? can you explain in combinations without using this coefficient thing...

cuemath
cuemath moderator

 @cvryn7 Basically, comparing the coefficients on both sides enables you to indirectly count the number of solutions. The coefficient of x^r means that when you algebraically expand the product, one of the terms will be ()x^r, that is, a number will accompany x^r. That is the coefficient. For eg, in the expansion of (1+x)^2, the coefficient of x is 2. 

cvryn7
cvryn7

 @cuemath and also.. what you mean by COEFFICIENT OF x^r??