In dynamic resource allocation r tasks are assigned at random to n computers, with no restriction on the number of jobs per computer

Question

I have never done this type of question (with arbitrary variables in a counting problem), so I had a lot of difficulty. Please let me know if my approach is wrong. Thanks!

1. "Computer number 1 is assigned no jobs";
2. "Computers number 1 and 2 are assigned no jobs";
3. "exactly two of the computers are assigned no jobs"
4. "No computer is assigned more than one job".

Here are my attempts:

Firstly, the total number of combinations is $r^n$, since for each of the n computers, an unlimited number of tasks from r can be allocated.

1. Since Computer 1 can be assigned no jobs, there are $r^{n-1}$ ways to assign the tasks to the remaining tasks. Thus P = $\frac{r^{n-1}}{r^n}$.

2. Same idea to the one above, P = $\frac{r^{n-2}}{r^n}$

3. There are $r^{n-2}$ resources to allocate, but since any two computers, there would be $n \choose 2$ different ways to choose the two computers. Thus $P=\frac{(r^{n-2}) {n \choose 2}}{r^n}$

4. This one I have no idea how to even begin. Please help!

Answer 1

The total number of ways to assign tasks to computer is $n^r$, not $r^n$. This is because each of the $r$ tasks needs to be assigned to be assigned to exactly one computer, and there are $n$ choices for where to assign each task. Once you make this switch, you will have the correct answer to questions $1$ and $2$.

Question $4$ is easier than $3$. The first task can be assigned to any of the $n$ computers. The second can be assigned to any of $(n-1)$ computers, since it cannot be assigned to the first. The third task can be assigned to any of $(n-2)$ computers, and so on. The final answer is $$ \frac{n(n-1)(n-2)\cdots(n-r+1)}{n^r}=\frac{n!}{n^r(n-r)!}. $$ Question $3$ is actually pretty tricky. There are $\binom{n}2$ ways to choose the computers which get no tasks. We now need to assign tasks to the remaining computers so that each computer gets at least one task. This condition is hard to account for; you cannot just do $(n-2)^r$. Rather, we need to use the principle of inclusion exclusion. If you are unfamiliar with this method, then whoever asked you this question was being unfair!

Specifically, take all of the ways to assign tasks to these $(n-2)$ computers, $(n-2)^r$. For each computer, we then subtract the "bad" assignments where that computer did not receive a task. The result is $(n-2)^r-(n-2)(n-3)^r$. However, assignments which were "doubly bad" have been subtracted twice, so these must be added back in, resulting in $(n-2)^r-(n-2)(n-3)^r+\binom{n-2}2(n-4)^r$. It turns out we have to then subtract the "triple bads," add back the quadruple bads, and so on all the way down, resulting in a final answer of $$ \frac1{n^r}\sum_{k=0}^{n-2}(-1)^k\binom{n-2}k(n-2-k)^r. $$