1
$\begingroup$

This problem actually relates to multi processing computer architecture, but boils down to a mathematical expression quite difficult to understand.

The image below explains the problem and the last expression (N-1)C(r-1) is some thing I am NOT able to understand.

enter image description here

I took an example of 9 tasks and 3 levels so that N=9 and r=3. Going by the description at the bottom, each level at least should have one task and hence division of rest of 6 tasks in three levels counts the number of process graphs. I did try as below :

Enumerate in how many ways number 6 be partitioned in three places :

2,2,2 <-- Only 1 way to express so that it totals to 6

1,1,4 <-- Only 3 ways to express so that it totals to 6

3,2,1 <-- 6 ways to express so that it totals to 6

4,2,0 <-- 6 ways to express so that it totals to 6

5,1,0 <-- 6 ways to express so that it totals to 6

6,0,0 <-- Only 3 ways to express so that it totals to 6

3,3,0 <-- Only 3 ways to express so that it totals to 6

So in all this totals to 1+3+6+6+6+3+3 = 28 ways

Going by the expression the value should be 8C2 which evaluates to 28.

However, what I lack is to understand, how we have arrived at the result (N-1)C(r-1).

Thanks for reading.

  • 0
    Yes, $a$nd excuse me for that if that causes any confusion. You may please edit it.2012-10-13

1 Answers 1

2

A standard way of counting arrangements like these is the so-called "stars and bars" argument. If you have a way of splitting a total of $m$ into a sum of $r$ parts, then that's the same as a way of listing $m$ stars ($\star$) separated by $r-1$ bars ($|$). For example: $\begin{align*} 6 = 2+2+2 &\implies \star\star|\star\star\ |\star\star\\ 6 = 5+0+1 &\implies \star\star\star\star\star\ |\ |\star \end{align*}$ How many ways are there to separate $m$ stars by $r-1$ bars? Well, that's a total of $m + (r-1)$ symbols, and you're counting the ways for $(r-1)$ of them to be bars, so there are ${m + (r-1) \choose r-1}$ ways total.

In your case, $m=N-r$, so it simplifies to ${(N-r) + (r-1)\choose r-1} = {N-1\choose r-1}\text{ ways.}$

On the other hand, you can count directly by imagining that instead of trying to fit $N$ tasks into $r$ preexisting levels, the tasks come with an ordering and you are deciding which of the tasks are the last tasks in each level. Since there are $r$ levels, you have to choose $r$ of the $N$ tasks to be level-finishing tasks. But the final task has to be the $r$th level-finisher, so you are really only choosing which of the remaining $N-1$ tasks finish the first $r-1$ levels. There are ${N-1\choose r-1}$ ways to choose.

  • 1
    Thank you! Here are a couple of similar questions (not answered by me): http://math.stackexchange.com/questions/101432/stars-and-bars-with-constraint and http://math.stackexchange.com/questions/106860/if-n-balls-are-distributed-randomly-into-k-urns-what-is-the-probability-tha2012-10-13