13
$\begingroup$

In how many ways can we arrange $7$ different things to $3$ people, such that all of them must get at least one?

We know that if we have $n$ identical items which will be distributed in $r$ distinct groups where each must get at least one then the number of way is $\binom {n-1}{r-1}$ (i.e in this case $\binom62$. But in the question it is said that $7$ DIFFERENT things then what will be the approach?

MY TRY ::

At first selecting $1$ by $1$ for each $3$ people so that each get at least one : $\binom71 \times \binom 61 \times \binom 51$
Now each of $4$ can go to any of $3$ so :$3^4$ ways, so $\binom71\times\binom61\times\binom51\times (3^4)$

MY TRY #2 ::

total possibilities - {any one get $0$ $(0,6,1)(0,5,2)(0,4,3)$} - {any two get $0$ $ (0,0,7)(0,7,0)(7,0,0)$} so

$3^7$ - {($\binom76 + \binom 75 + \binom 74$ )$\times$ 3!} - 3

$\endgroup$
2
  • $\begingroup$ You are double counting. For example, if objects 1,2,3,4,5,6, and 7 are allocated among A, B, and C. You are counting one way in which 1,2,3 are assigned to A, B, and C, respectively and then 4,5,6, and 7 go to A. But you also count the possibility in which 4,2,3 are first assigned to A,B, and C and then 1,5,6,7 go to A. $\endgroup$
    – user96614
    Oct 15 '13 at 16:27
  • $\begingroup$ then how should i do this???what is the correct way??? $\endgroup$ Oct 15 '13 at 16:43
12
$\begingroup$

It's actually helpful here to generalize the problem to distributing $n$ different objects to $3$ people (with $n\ge3$ so that each person can be guaranteed getting at least one item). If you disregard the requirement that each person get at least one item, then you get the overestimate $3^n$. From this, let's subtract the number of ways you can pick one person to not get any items, distributing the rest to the other two, giving

$$3^n-3\cdot2^n$$

But this now under-estimates because you're now doublecounting occasions when two people fail to receive any items. So we need to add back in the number of ways this can happen, producing

$$3^n-3\cdot2^n+3\cdot1^n$$

As a sanity check, consider the case $n=3$, where there are clearly $6$ ways to assign an item to each person:

$$3^3-3\cdot2^3+3=27-24+3=6$$

For $n=7$, the formula gives

$$3^7-3\cdot2^7+3 = 2187-3\cdot128+3=1806$$

The general principle here is known as inclusion-exclusion. Note that it gives the correct answer, $0$, even for $n=1$ and $2$.

$\endgroup$
2
  • $\begingroup$ is there any mistake in my second try @barry cipra $\endgroup$ Oct 15 '13 at 18:03
  • 1
    $\begingroup$ @RitabrataGautam, your second try looks perfectly fine. However, it's worth comparing its approach to the formula in my answer for values of $n$ larger than $7$, say $n=20$. $\endgroup$ Oct 15 '13 at 18:17
1
$\begingroup$

In any distribution let there be groups $z_1, z_2, z_2,...,z_r$ and consider the distribution where blanks are allowed.

The total number of these are $ r^n$. The number in which $z_1$ is blank is $$(r-1)^n$$ $\therefore$ the number in which $z_1$ is not blank is , $$r^n-(r-1)^n$$ of these last,the umber in which $z_2$ is blank, is $$(r-1)^n-(r-2)^n$$ $\therefore$, the number in which $z_1$ and $z_2$ are not blank,is $$r^n-2(r-1)^n+(r-2)^n$$ If we keep doing this for $z^r$ groups, we will get this expression, $$r^n-{x\choose1}(r-1)^n+{x\choose2}(r-2)^n-...+(-1)^x(r-x)^n$$ The number of distribution in which no one of x assigned groups is blank, is when x=r, then $$r^n-{r\choose1}(r-1)^n+{r\choose2}(r-2)^n-...+(-1)^(r-1){r\choose{r-1}}$$ $$or$$ $$\sum^{r}_{p=0} (-1)^p{{r}\choose{p}}(r-p)^n$$ $$or$$ $$Coefficient\,\,of\,\,x^n\,in\,\,n!(e^x-1)^r$$

So finally answer to you question,In how many ways can we arrange 7 different things to 3 people, such that all of them must get at least one?

--> $3^7-{3\choose1}2^7+{3\choose2}1^7-{3\choose3}0^7$ =1806

Bibliography: Goyal, S., Dr. (n.d.). Chapter-5, Session-6, Arrangement in groups,Multinomial Theorem, Multiplying Syntetically. In Skill in Mathematics - Algebra for JEE Main and Advanced 2020. Arihant.

$\endgroup$
-4
$\begingroup$

Check stars and bars. Say you want to distribute $k$ items among $n$ people, no other restrictions. This means you have to chop a string of $k$ items (stars, $*$) into $n$ stretches, one to each person (with bars, $|$). This requires $n - 1$ bars. So you have a string of $n + k - 1$ stars-and-bars, of which $n - 1$ are bars, so the number of ways to do this is:

$$\binom{k + n - 1}{n - 1}$$

If you restrict each one to get at least one item, it means you first distribute $n$ items, one to each, and then you get to distribute $k - n$ among the $n$ people with no restrictions, for a number of ways (by the above):

$$\binom{k - n + n - 1}{n - 1} = \binom{k - 1}{n - 1}$$

$\endgroup$
1
  • $\begingroup$ This will surely work for 'k' identical items. Does this work for 'k' distinct items ? $\endgroup$
    – AllTooSir
    Jun 24 '16 at 13:07

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.