algorithm - 1..nからのバイナリヒープの数

Question

1からnまでの整数を指定して、これらの数値で構築できる有効なバイナリヒープの数を決定します。

Example: 1 2 3 4

有効な最小ヒープは次のとおりです： {1 2 3 4}、、、{1 3 2 4}{1 2 4 3}

したがって、答えは3です

Answer 1

ヒント：

バイナリヒープには、事前定義された数のノードと、明確に定義された構造（完全なツリー）
があります。この問題について再帰的に考えてください。

ルート以外の番号のどれを左側のサブツリーに配置し、どれを右側に配置するかを「選択」し、サブツリーで再帰的に呼び出します。

f(1) = 1 //no sons
f(2) = f(1) * 1 //one son and a root
//chose which element will go to the left sub-tree, and recursively invoke.
f(3) = Chose(2,1)* f(1) * f(1) * 1 
f(4) = Chose(3,2)*f(2) * f(1) * 1 //chose which 2 elements will go to the left sub tree
...

質問は宿題としてタグ付けされているので、一般的なケースの正確な番号を見つけるのはあなた次第です。