1
$\begingroup$

I know that :

$T(n,k)=T(n−1,k−1)+T(n−1,k)$ is the Pascal triangle.

But what is this then:

$T(n,k)=T(n−1,k−1)+T(n,k-1)$

Is there any name for it? I am trying to learn about it's time complexity etc, but I can't find anything online.

$\endgroup$
3
  • 2
    $\begingroup$ What is the time complexity of a recurrence? Time complexity is usually associated with algorithms: it describes the asymptotic rate of growth of their running time. $\endgroup$ May 3 at 2:53
  • 2
    $\begingroup$ You might find it useful to know about oeis.org $\endgroup$
    – D.W.
    May 3 at 3:23
  • 2
    $\begingroup$ Let $T'(n,m):=T(m,n)$. Rewrite the second recurrence. $\endgroup$ May 3 at 12:34

1 Answer 1

3
$\begingroup$

The second recurrence is ALSO Pascal's Triangle (interchange n and k).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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