In this question, I asked about a confusion I had counting the size of the sample space for allocation of n processes to n servers. Bangye gave a simple answer by approaching the counting problem from the perspective of the choice when allocating each process.

I'd like to know -- to expand my understanding of counting -- how we might count in a different way, from the server perspective: assigning each server to some number of processes.

The obvious problem I see is if I have already allocated one process to a server, I then can't allocate it to another, and so the analysis becomes complicated -- each server-based count is dependent on all other server-based counts.

Is this a common problem, and there's actually a heuristic to know which way to count things?

  • $\begingroup$ The answer of $n^n$ is wrong in my opinion--as it should be $n!$. Further if you know the number of servers and processes then you can count the number of ways to partition the processes using the Stars and Bars Method. $\endgroup$ – Jared Apr 9 '15 at 23:42

The heuristic is: "try both ways, and see which works". As you get more practice you might start to develop a sixth sense about which one to try first, but that's the most useful principle I can suggest.

The general mathematical principle is the bijection principle. If you have two finite sets $S,T$ and you can find a bijection between $S$ and $T$, then they must have the same size. So, if you can count the number of elements in either of them, you can infer the number of elements in the other one.

| cite | improve this answer | |

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.