-1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Please help me, thank you. Ngoc Le $\endgroup$ – Ngoc Le Apr 17 at 3:12
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 17 at 3:18
  • $\begingroup$ 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. $\endgroup$ – Ngoc Le Apr 17 at 4:15
  • $\begingroup$ Thank you Jason for your edit my written problems. It is clear and explicit. I will improve my writing. Thanks $\endgroup$ – Ngoc Le Apr 17 at 4:20
  • $\begingroup$ 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}$$ $\endgroup$ – Théophile Apr 17 at 4:24
0
$\begingroup$

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.

$\endgroup$

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.