Distributing $n$ different things among $r$ distinct groups such that all of them must get atleast $1$

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

Solution 1:

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$.

Solution 2:

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.