反復関係：反復関係を書く

Question

私はこのアルゴリズムの反復関係を書こうとしています。しかし、私は "root"変数と混同しています。誰でも助けてくれます。 n個のノードを持つ可能なバイナリツリーの数？

Algorithm countTrees(n) { 
    if(n<=1) then return 1 
    else { 
     sum = 0 
     for root=1 to root<= n do { 
      left = countTrees(root-1) 
      right = countTrees(n-root) 
      sum = sum+(left*right) 
     } 
     return sum 
    } 
} 

私はこれまでのところ、これを書いたが、私はこの問題を解決するには、rootに対処する方法がわかりません。

T（N）= N [T（ルート-1）+ T（Nルート）]

Answer 1

コードが既にだけアルゴリズムとして表現バイナリツリーの数、のための漸化式です。私はあなたがループ上の合計を持っていたので、あなたが立ち往生していたと思います。ここでは、0..N-1をするより標準的であることを1..nのから変更されたループ値と標準的な数学的notation--である：手で書く

C(0) = C(1) = 1 
C(n) = sum(C(i) * C(n-i-1) for i = 0...n-1) 

（または乳液で）あなたがしたいですsumではなく合計記号を使用しますが、論理的には同じです。

これはCatalan numbers（通常はC(1)の場合は明示的に記載されていません）の反復関係です。また、リンクされたWikipediaページには、再帰関係のクローズフォームソリューションとその正当性の証明が含まれています。