What is the Beggar’s Method in permutation and combinations?

7 min readJun 21, 2021

Problems of kind “In how many ways we can distribute n identical coins among r Beggars?” in Permutation and combination is called beggars problem.

To solve these kind of problem there is a simple logic:

Basically what we are doing in this kind of problems is distribution ,these kind of questions are worded like this :

“If you have 10 apples with you , In how many ways you can distribute it completely between 2 people . ”

If I have to distribute it completely lets visualize how it can be done :

If there are 2 people (A & B) sitting in front of me and I have 10 apples with me, I give 1 to 1st person and remaining to other person because it’s a distribution I should be empty handed at the end of the game So, by the process I give :

here, I can be so sure combination of apples with both of them will be (0,10), (1,9), (2,8),…….,(10,0) and these are the only unique combination possible that means only 11 ways are possible. Now , let us think back what is in the word problem and extend logic here : If I put all these apples as letter ‘A’ I put the 10 apples together and I write A 10 times as : A A A A A A A A A A , Now what to do just distribute it using scale , moment I think about scale I put scale anywhere in between these A’s there are 10 A’s ,let put scale in the beginning : |A A A A A A A A A A that means 1st one getting nothing and 2nd person getting all the 10 apples , let put scale after 2: A A | A A A A A A A A that means 1st one getting 2 apples and 2nd person getting all the 8 apples ; now if i think further, had I given an alphabet S to the scale , what i actually doing, i tried to figure out number of combinations how those 10 A’s and 1 S can be rearranged , So this makes a 11 letters word, so no. of ways has to be 11! now this 11! have 10 A’s so it has to be divided by 10! , so 11!/10! = 11 same I have gotten by counting also, counting is very easy but not fruitful to more complicated case , for example I say 25 apples and 3 people, needs to work out many examples ,rather apply this logic of alphabets : 25 apples are 25 A’s and if I need to divide among 3 people all I need is 2 scales, if I placed those 2 scales I am done , If i talk about 2 scales that have initial ‘S’, so there is ‘S’ two times and ‘A’ 25 times , eventually I have to arrange 27 alphabets , that is : (27! / (25! 2!)) ;

Now generalize this as :

n apples and r peoples , we can distribute n apples among r people as :

(n+(r-1))!/(n!)(r-1!)

Other similar problems:

or In how many ways 8 identical balls can be distributed into 3 different boxes so that no box remains empty?

or Three boys picked up 8 oranges. In how many ways can they divide them if all oranges be identical?

VARIATION 2::Find the number of positive integer solutions of the equation X + Y + Z = 8?

This question is almost same but constraints are different i.e. X , Y, Z > 0

Or we can write X≥ 1, Y≥ 1, Z ≥ 1

Again the question is analogous to distributing 8 identical coins to three beggars

But here the condition is every beggar should have atleast 1 coin so we will distribute 1 coin to each beggar in advance.

So giving 1 coin to each beggar means we donated 3 coins. Thus we are left with 5 coins which we have to distribute among 3 beggars which can be done in

VARIATION 3::Find the number of integral solutions of the equation X + Y + Z +W = 20 where X≥ 1 ,Y≥ 2, Z >0 , W ≥ 3?

Solution: This question is almost same but constraints are different i.e. X≥ 1 , Y≥ 2, Z >0 ,W ≥ 3

Again the question is analogous to distributing 20 identical coins to four beggars But here the condition is 1st beggar should have at least 1 coin, 2nd beggar should have at least 2 coin , 3rd beggar should have more than zero coin which is same as saying that he should have at least 1 coin, and 4th beggar should have at least 3 coins So we will give 1 coin to 1st beggar ,2 coins to 2nd beggar ,1 coin to 3rd beggar and 3 coins to 4th beggar first.

Now we are left with 13 coins to distribute among 4 beggars:

which is equals to

VARIATION 4::How many non negative integral solutions are there to the system of equations X + Y + Z +W + K = 20 and W+ K = 7 ?

Solution: Putting the value of W+ K = 7 in

X + Y + Z +W + K = 20 when each of X≥ 0 , Y≥ 0 ,Z ≥ 0 ,W≥ 0 ,K≥ 0

We get X + Y + Z = 13

Solving this equation is same as distributing 13 Identical coins among 3 beggars which can be done in

Similarly solving equation W+ K = 7 where W≥ 0 ,K≥ 0 equivalent to distributing 7 Identical coins among 2 beggars which can be done in

Thus the total number of solutions to the system of equations is = 8 x 105=840

VARIATION 5::QUESTION 8:Find the number of non negative integral solutions of 2X + Y + Z = 18 ?

Solution

The questions which we did till now had coefficient one but this has coefficient two. For the time being we put x =k so equation becomes

2K + Y +Z = 18

Y + Z = 18–2k (1)

As per the given constraint we are given Y ≥ 0 and Z ≥ 0 .

Thus Y + Z ≥ 0

=> 18–2k≥ 0

=> k≤ 9

Now as far as solving equation (1) is concerned we very well know it is equivalent to distributing 18–2k coins among 2 beggars

= 18- 2k + 1 = 19–2k ways

But k varies from 0 to 9.Thus total number of ways

VARIATION 6::Find the number of non negative integral solutions of the equation X + Y + Z ≤18 ?

Solution

Given equation can be written as

X + Y + Z + W = 18 where each of X, Y, Z and W is greater than or equal to zero

Thus reduces to distributing 18 coins to 4 beggars which can be done

Hence the number of non-negative integral solutions of the equation X + Y + Z ≤ 18 are 1330.

What is the Beggar’s Method in permutation and combinations?

Written by Faizan Ansari

Responses (1)