# Counting Graphs

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.

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).

-
$N=9$ (not 6), so $\binom{N-1}{r-1} = \binom{8}{2} = 28$. –  Ted Oct 13 '12 at 2:44
Excuse me Ted, You are right, I have been foolish to do so. Thanks for pointing. –  RIPUNJAY TRIPATHI Oct 13 '12 at 2:46
I have edited question to understand the derivation of the expression above. –  RIPUNJAY TRIPATHI Oct 13 '12 at 3:28
Your edit just made a huge part of this long question superfluous. All you seem to be asking now is how to arrive a $\binom{N-1}{r-1}$; the enumeration just distracts from that, since its result is now the expected result. –  joriki Oct 13 '12 at 3:28
Yes, and excuse me for that if that causes any confusion. You may please edit it. –  RIPUNJAY TRIPATHI Oct 13 '12 at 3:34

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.