edited by
4,488 views
11 votes
11 votes

Consider the following function.

Function F(n, m:integer):integer;
begin
    if (n<=0) or (m<=0) then F:=1
    else
      F:F(n-1, m) + F(n, m-1);
end;

Use the recurrence relation  $\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n \\ 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)$.

edited by

5 Answers

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

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

c) $2{{(n+m)!}\over{n!m!}} - 1$

Related questions

21 votes
21 votes
1 answer
1
Kathleen asked Sep 29, 2014
4,799 views
Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$.Which of the following statements is true?$T(n) = O...
21 votes
21 votes
3 answers
3
Kathleen asked Sep 29, 2014
4,978 views
The correct matching for the following pairs is$$\begin{array}{ll|ll}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\\hline \text{B.} & \...