# **Question:** How many ways to make $m$ tasks done, given that there are $n$ people doing all tasks?

Question: How many ways to make $$m$$ tasks done, given that there are $$n$$ people, each people is capable of doing from $$0$$ to $$m$$ tasks, many people can take over 1 tasks.

This can be express in a binary array size $$n*m$$

Beolow is one case.

Examples: $$n=2, m=2$$.

There are $$9$$ ways to make $$m=2$$ tasks done.

Let denote that $$2$$ people are $$P1$$ and $$P2$$, $$2$$ tasks are $$T1$$ and $$T2$$.

So, we can express $$9$$ cases in binary that make $$T1; T2$$ done

$$0011$$ means that $$P1$$ do nothing and $$P2$$ covers $$2$$ tasks. Apart from this, we have $$8$$ other ways: $$1001; 0110; 1100; 0111; 1011; 1110; 1101; 1111.$$

There are $$7$$ cases that does not take into accounts as follows:

$$0000;0001;0010;0100;1000;0101;1010.$$

in the last two cases $$0101; 1010$$ just only task $$T1$$ or $$T2$$ done.

Your help is highly appreciated! Thanks a lot in advance!

• Please help me, thank you. Ngoc Le – Ngoc Le Apr 17 at 3:12
• See Wikipedia on combinations. There are ${n \choose k}=\frac {n!}{k!(n-k)!}$ ways to choose $k$ items out of $n$. If you want at least $k$, add up all the possible values. – Ross Millikan Apr 17 at 3:18
• Thanks Ross for your response. Yeah, I did this way but it is not exactly the answer. Because when we choose k items our of n items, in k items we do not know 0 or 1 in k items. As required k items must be 1. So your answer can be bigger than the expected result. Thank you Ross so much. – Ngoc Le Apr 17 at 4:15
• Thank you Jason for your edit my written problems. It is clear and explicit. I will improve my writing. Thanks – Ngoc Le Apr 17 at 4:20
• It seems like you're looking for a simple closed formula. But as Ross says, you have to add up the binomial coefficients: $$\sum_{j=k}^n{n \choose j}$$ – Théophile Apr 17 at 4:24

## 1 Answer

Looks like the exclusion-inclusion principle has something to do here. You need all possible binary fillings of the $$m\times n$$ matrix, minus those which leave any task unhandled, plus those which leave any two tasks unhandles, minus those which leave any three tasks unhandled... and so on. Of course there are $$m={m\choose 1}$$ tasks which can be unhandled, or $$m\choose 2$$ pairs of tasks, or $$m\choose 3$$ triples of tasks...
Finally, your number is $$2^{nm}-m\cdot2^{n(m-1)} + \tfrac{m(m-1)}2\cdot2^{n(m-2)}-\ldots\pm 1$$ $$= \sum_{i=0}^m (-1)^i{m\choose i}\cdot 2^{n(m-i)}$$ This, however, does not necessarily keep all workers involved - the sum covers also such configurations in which just one of $$n$$ people does all $$m$$ tasks.