# 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

• 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. Oct 15, 2013 at 16:27
• then how should i do this???what is the correct way??? Oct 15, 2013 at 16:43

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

• is there any mistake in my second try @barry cipra Oct 15, 2013 at 18:03
• @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$. Oct 15, 2013 at 18:17

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.

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

• This will surely work for 'k' identical items. Does this work for 'k' distinct items ? Jun 24, 2016 at 13:07