# There are r tasks that can be assigned to n people, where there is no limit on the number of tasks that can be assigned to each person. [duplicate]

This is a hw question I got in my class, but I'm not even sure how to begin it. I need to find the probability of each of the four parts below, but first I can't even count the total number of ways these tasks could be allocated.

1. "Person number 1 is assigned no jobs";
2. "People number 1 and 2 are assigned no jobs";
3. "exactly two of the people are assigned no jobs"
4. "No person is assigned more than one job".

I wrote out some examples, and it has confused me even more.

For example, if we had 1 task and 2 people, all the possibilities are {(1,0), (0,1)}, giving 2 different possibilities.

If we had 2 tasks and 2 people, we have {(0,2), (1,1), (2,0)}, giving 3 different possibilities.

If we had 2 tasks and 3 people, we have {(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)}, giving 6.

I'm having a lot of difficulty with finding a pattern between these cases.

Any help would be appreciated. Thanks!

## marked as duplicate by N. F. Taussig combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 17 at 23:59

• If you are asking a probability question, you need to specify how the assignment is randomly chosen. Is each task assigned to a uniformly random person, independent of the others? – Mike Earnest Jan 17 at 22:56
• Yes, sorry. Each task is assigned to a uniformly random person, and independent of the others. – Tim Weah Jan 17 at 22:59
• Also, this has already been asked: math.stackexchange.com/questions/3076435/… – Mike Earnest Jan 17 at 23:18
• @TimWeah I upvoted because I thought that you showed good preliminary effort in solving the problem on your own. – user2661923 Jan 17 at 23:54

There are $$n$$ possible ways to assign each of the $$r$$ tasks, so the sample space has $$n^r$$ possible assignments.

Suppose tasks $$A$$, $$B$$ can be assigned to persons $$1$$, $$2$$, or $$3$$. Then there are $$3^2 = 9$$ possible assignments, as shown in the following table, with each row corresponding to an assignment. $$\begin{array}{c c c} 1 & 2 & 3\\ \hline A, B & & \\ A & B & \\ A & & B \\ B & A & \\ B & & A\\ & A, B & \\ & A & B \\ & B & A \\ & & B, A \end{array}$$

For the first question, since person number $$1$$ is not assigned a task, there are $$n - 1$$ ways to assign each of the $$r$$ tasks.

For the second question since persons $$1$$ and $$2$$ are not assigned a task, there are $$n - 2$$ ways to assign each of the $$r$$ tasks.

For the third question, choose which two people will not be assigned a task, then assign the $$r$$ tasks to the remaining $$n - 2$$ people. Since each of those $$n - 2$$ people must be assigned a task, the number of such assignments is equal to the number of surjective functions from a set of $$r$$ elements to a set of $$n - 2$$ elements, which is found by multiplying the Stirling number of the second kind $$S(r, n - 2)$$ by the $$(n - 2)!$$ ways of matching people to groups of tasks.

For the fourth question, choose which $$r$$ people will be assigned a task, then distribute the tasks to them.