Easier way to solve combinations

Easier way to solve combinations

Sometimes, you come across some seriously interesting questions in Combinatorics. When you saw the answer, it get thinking – it couldn’t have been a coincidence. There had to be a simpler logic to it and there was!

Question 1: In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if Dave should get either three paintings or five paintings? (All paintings should be given away).

Solution 1:

There are two ways of distributing the paintings in this case:

Dave gets 3 paintings and Mona gets the rest: You select 3 of the 10 paintings and give them to Dave. This can be done in 10C3 = 120 ways

Dave gets 5 paintings and Mona gets the rest: You select 5 of the 10 paintings and give them to Dave. This can be done in 10C5 = 252 ways

Total number of ways in which you can distribute the paintings = 120 + 252 = 372 ways

Simple enough, right? Let’s take a  look at another simple similar question.

Question 2: In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if Dave should get at least two paintings? (All paintings should be given away.)

Solution 2:

Dave should get at least two paintings so it means he can get 2 or 3 or 4 or more up to 10 paintings. Calculating all those cases would be tedious so this is a perfect opportunity to use ‘Total – Opposite’ method.

Total ways in which you can distribute 10 paintings between two people without any constraints: Each painting can be given away in two ways – either to Dave or to Mona. So the paintings can be distributed in 2*2*2*…*2 = 2^10 = 1024 ways

Number of ways in which Dave gets 0 paintings or 1 painting: 1 + 10C1 = 11 ways

So number of ways in which Dave gets 2 or 3 or 4 … upto 10 (i.e. at least 2 paintings) = 1024 – 11 = 1013 ways

Another ‘seen before, know how to solve it’ kind of question. Now let’s come to the question of the day which doesn’t look much different but actually is.

Question 3: In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if both collectors should get an even number of paintings? (All paintings should be given away.)

Solution 3:

Paintings can be distributed in the following ways:

0, 10 – One person gets 0 paintings and the other gets 10

2, 8 – One person gets 2 paintings and the other gets 8

4, 6 – One person gets 4 paintings and the other gets 6

You will need to calculate each one of these ways and then add them. Note that the ‘Total – Opposite’ method does not work here because finding the number of ways in which each person gets odd number of paintings is equally daunting.

Case 1: 0, 10

One person gets 0 paintings and the other gets 10. This can be done in 2 ways – either Dave gets all the paintings or Mona gets them.

Case 2: 2, 8

One person gets 2 paintings and the other gets 8. Select 2 paintings out of 10 for Dave in 10C2 = 45 ways. Mona could also get the 2 selected paintings so total number of ways = 45*2 = 90 ways

Case 3: 4, 6

One person gets 4 paintings and the other gets 6. Select 4 paintings out of 10 for Dave in 10C4 = 210 ways. Mona could also get the 4 selected paintings so total number of ways = 210*2 = 420

Total number of ways such that each person gets even number of paintings = 2 + 90 + 420 = 512 ways

But 512 is 2^9 – in form, suspiciously close to 2^10 we used in question 2 above. Is there some logic which leads to the answer 2^(n-1)? There is!

You have 10 different paintings. Each painting can be given to one of the 2 people in 2 ways. You do that with 9 paintings in 2*2*2…  = 2^9 ways. When you distribute 9 paintings, one person will have odd number of paintings and one will have even number of paintings (0 + 9 or 1 + 8 or 2 + 7 or 3 + 6 or 4 + 5).

The tenth painting needs to be given to the person who has the odd number of paintings so you give the tenth painting in only one way. This accounts for all cases in which both get even number of paintings.

Total ways = 2^9 * 1 = 512

On the same lines, now think about this:

Question 4: In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if both collectors should get an odd number of paintings? (All paintings should be given away.)

div#stuning-header .dfd-stuning-header-bg-container {background-image: url(http://cetking.com/wp-content/uploads/2017/05/slide-3.jpg);background-size: initial;background-position: center top;background-attachment: initial;background-repeat: initial;}#stuning-header div.page-title-inner {min-height: 600px;}