Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
1  
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
That was a fantastic reply. To enlighten myself better, I want to have some more exercises on similar problems. Please point to some material or other similar questions that you may have answered. –  RIPUNJAY TRIPATHI Oct 13 '12 at 5:03
1  
Thank you! Here are a couple of similar questions (not answered by me): math.stackexchange.com/questions/101432/… and math.stackexchange.com/questions/106860/… –  Owen Biesel Oct 13 '12 at 5:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.