recategorized by
313 views
3 votes
3 votes
Suppose that a person with 10 friends invites a different subset of 3 friends to dinner every night for 10 days. In how many ways can he do this so that all friends are included at least once ?

How to approach this problem ?
recategorized by

1 Answer

Best answer
1 votes
1 votes

This is a very nice combinatorial problem . Here the concept of inclusion exclusion principle is to be used  , [similar to the case where we find number of onto functions , where in f : A --> B , all the elements of B are mapped by A at least once] :

For  d days , we want to call f friends n at a time .

Thus we have  fCn such subsets .

So for d days , number of ways we can select such groups  =  ( fCn )d

Let we exclude one friend , then  number of ways                =   ( fCn-1 )d

Excluding a friend is done  in  fC1 ways

So number of ways of inviting when one friend is excluded    =    fC1 * ( fCn-1 )d

Similarly number of ways of inviting when two friends are exluded  =   fC2 * ( fCn-2 )d

In general , when k friends are to be excluded , number of ways   =   fCk * ( fCn-k )d

So this we will go on till  k  =  f - n as beyond that there will be 0 ways of inviting as we need to have 'n' friends at least so we cannot exclude more than 'f - n' friends . 

Hence total number of ways         =     Number of ways in which 0 friend is excluded (k = 0 ) - Number of ways 1 friend is                                                                     excluded (k = 1) +  Number of ways 2 friends are excluded(k = 2) - .. + .............[ till  k <=                                                         f - n  and   n - k >= 0 ]

                                                 =    Σ (-1)k  *   fCk * ( fCn-k )d    where k = 0 to the value as satisified by the condition mentioned                                                         in the brackets

Here we substitute  f = 10  , d = 10 and n = 3 to get the desired result 

selected by

Related questions

5 votes
5 votes
1 answer
2
dd asked Jun 8, 2020
1,178 views
How many pairs $(x,y)$ such that $x+y <= k$, where x y and k are integers and $x,y>=0, k 0$.Solve by summation rules.Solve by combinatorial argument.
0 votes
0 votes
1 answer
3
garimanand asked Dec 2, 2018
505 views
1 votes
1 votes
1 answer
4
Lakshman Bhaiya asked Oct 24, 2018
517 views
A number of ways we can arrange letters of the word " TESTBOOK " such that E always comes between O's is ___________