1
$\begingroup$

In how many ways can $7$ different objects be divided among three persons so that either one or two of them do not get any objects?

My Approach

I am not able to understand how to solve the problem.

I did $7$!/$3$! . $4$!

Can anyone guide me how to solve the problem?

$\endgroup$
5
$\begingroup$

Call the people A, B, and C. Suppose C is to be shut out. Then A can get any of the $2^7$ subsets of the set of objects.

Our first estimate of the number of ways is therefore $3\cdot 2^7$. However, this sum counts $6$ times the number of ways two of the people receive nothing. However, there are only $3$ such ways, so the total is actually $3\cdot 2^7 -3$.

Another way: There are $2^7-2$ ways that C is shut out of the game and A and B each receive at least one object. Multiply by $3$, and add the three ways in which one of the players gets everything.

Remark: Our first way used the principle of Inclusion/Exclusion, because it is such a useful idea. The second way, for this problem, is more straightforward.

$\endgroup$
  • $\begingroup$ Nicolas Can you explain me in more detail? $\endgroup$ – justin takro Nov 14 '15 at 2:57
  • 1
    $\begingroup$ For the second way, we want to count the number of ways C gets nothing, and A and B each get at least one thing. Our collection of $7$ different objects has $2^7$ subsets. A is allowed to have (almost) any subset, with B getting the rest, The $2$ subsets A cannot get are (i) the empty set, for then A would get nothing and (ii) the full set, for then B would get nothing. So the number of possible choices for what A gets is $2^7-2$. Multiply by $3$, since any of the people can be shut out, and add $3$ for the ways one person gets all the toys. Total $3(2^7-2)+3=3\cdot 2^7-3$. $\endgroup$ – André Nicolas Nov 14 '15 at 3:06
  • 1
    $\begingroup$ That is exactly what the answer solves. Look at second approach. We saw that there are $2^7-2$ ways in which C gets nothing, and each of A or B get at least one thing. There are also $2^7-2$ ways in which B gets nothing but A and C get something, and there are also $2^2-2$ ways in which A gets shut out and the others don't. Total so far, $3(2^7-2)$. Now we must count also the $3$ ways two people get shut out. So total $3(2^7-2)+3=381$. $\endgroup$ – André Nicolas Nov 14 '15 at 4:06
  • 1
    $\begingroup$ There are $7$ distinct objects. How many ways are there to divide them between X and Y? We pick a subset of the set of objects, give it to X, giv the rest to Y. A $7$-element set has $2^7$ subsets. Except that in Way 2 we did not allow either X or Y to get nothing, which leaves $2^7-2$ ways. $\endgroup$ – André Nicolas Nov 14 '15 at 4:11
  • 1
    $\begingroup$ Imagine the $7$ toys are lined up in a row, and we are deciding which ones to give to X. In front of each toy we write 1 if the toy is to go to X, and 0 if it isn't. There are $2^7$ different strings of 0's and 1's that we could write, and each string corresponds to X getting certain of the toys. $\endgroup$ – André Nicolas Nov 14 '15 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.