The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

Consider the following function.

Function F(n, m:integer):integer;
    If (n<=0 or (m<=0) then F:=1
      F:F(n-1, m) + F(n, m-1);

Use the recurrence relation  $\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n-1 \\ k-1 \end{pmatrix}$  to answer the following questions. Assume that $n, m$ are positive integers. Write only the answers without any explanation.

  1. What is the value of $F(n, 2)$?

  2. What is the value of $F(n, m)$?

  3. How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.

asked in Algorithms by Veteran (59.5k points) | 413 views


I think question needs small correction. 

F:F(n-1, m) + F(n-1, m-1);

People have provided good answer for A and B part. But for C part O(2^n) is upper bound. I am unable to get exact formula for number of calls for particular F(n,m). But following code could be used to get exact answer.

public class Test {
    public static int n, m, numberOfRecursiveCalls;
	public static int nCm(int a, int b) {
		if(a<=0||b<=0) return 1;
		else 	return nCm(a-1, b) + nCm(a-1, b-1);		
	public static void main(String[] args) {		
			n = 10;  m = 9;
		    numberOfRecursiveCalls = 0;

If anyone knows how exact number of calls could be calculated in Pascal's identity. Please mention it in the answer section. It will be great help. 

2 Answers

+1 vote
a) $\frac{n(n-1)}{2}$

b) $\frac{n(n-m+1)}{m!}$
answered by Veteran (60.8k points)

a) should be

$\frac{(n+1) * (n+2)}{2}$

b) I m struggling for it :p
Isn't its simply nCm ??

(a) nC2

(b) nCm = (n * n-1 * n-2  *....* n-m+1 ) / m!

(c) No. Of Recursive Calls = O(2^n)
In program it is : 
F:F(n-1, m) + F(n, m-1);

and recurence relation given :

$\begin{pmatrix} n\\ k \end{pmatrix}$  =  $\begin{pmatrix} n-1\\ k \end{pmatrix}$ + $\begin{pmatrix} n-1\\ k-1\end{pmatrix}$

Which one to consider ?

0 votes
a) $(n+1)(n+2)\over2 $

b) $(n+m)!\over n!m!$

c) $2{{(n+m)!}\over{n!m!}} - 1$
answered by (33 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,529 questions
46,674 answers
57,594 users