Push your limits

How many ways to share 15 different candies to 3 people and each must have at least one candy?

This problem can be generalize to N people and M different candies


The answer is 14250606.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Ravi Dwivedi
Jul 10, 2015

First of all we calculate total number of ways of distributing the candies without the restriction that each must have at least one candy.

Since there are 15 candies ,we can give then to 3 people in 3 15 3^{15} ways.

But in our above calculation we have included the cases in which 1 person has not got candy and when 2 persons got no candy so we need to subtract them.

Case1: Any one of them is without candy

First we select one of the person among 3 in ( 3 1 ) {3 \choose 1} ways and distributed 15 candies to remaining two people in 2 15 2^{15} ways.

Fundamental principle of multiplication yields a total number of ( 3 1 ) 2 15 {3 \choose 1} \cdot 2^{15} ways in this case.

Case2: 2 people got no candy

Select 2 people out of 3 in ( 3 2 ) {3 \choose 2} ways and give all candies to remaining person which can be done in 1 1 way.

Number of ways in this case= ( 3 2 ) 1 {3 \choose 2} \cdot 1

By Inclusion exclusion principle

Answer= 3 15 ( ( 3 1 ) 2 15 ( 3 2 ) 1 ) = 3 15 ( 3 1 ) 2 15 + ( 3 2 ) 1 = 3 15 3 × 2 15 + 3 = 14348907 98304 + 3 = 14250606 3^{15} - ({3 \choose 1} \cdot 2^{15} - {3 \choose 2} \cdot 1)\\ =3^{15} - {3 \choose 1} \cdot 2^{15} + {3 \choose 2} \cdot 1\\ =3^{15}- 3 \times 2^{15} +3\\ =14348907-98304+3\\ =14250606

Moderator note:

PIE makes this problem much easier to approach. I'm not sure why you chose to write the answer as "Total - (Case 1 - Case 2)", as that reminds me of the complement approach. The PIE approach would just be "Total - Case 1 + Case 2".

This is to explain and elaborate!!

Ravi Dwivedi - 5 years, 11 months ago

i was on the right track but i couldnt do it on top of my mind XD

Austin Opper - 5 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...