二分探索木のパターン数

質問

二分探索木のパターン数

二分探索木とは、上の値より大きければ右に、小さければ左に子を作っていくツリー状のものです。
例えば
　　　 6
　　 ／ ＼
　　4 　　　9
　／＼　／
　2 　5　8　
　　　／
　　 7
こんな感じです。
http://ja.wikipedia.org/wiki/%e4%ba%8c%e5%88%86%e6%9c%a8

で、問題なのですが、[1,2,3,4,5,6,7,8,9]といった9つの数値がある時、二分探索木は何通りできるか。
というものです。図を書いて色々考えてみたのですが求め方が分かりません。
全パターン書き出すのは量的に辛すぎますし、CやPで計算するのでしょうが、どのような式になるのでしょうか？

回答No.3

osu_neko09 · ベストアンサー

あれ？失礼しました。
http://blog.goo.ne.jp/osu_neko_runway09/e/aef7d70b705bb09778833f6e5396df59
こちらのURLならいかがでしょうか？

お礼

ありがとうございます見れました。詳しく書いて下さりありがとうございます。
すごく計算ややこしいですね。やはり2分探索木の場合はカタラン数の(2n)!/((n+1)!n!)では駄目なんですね

回答No.4

osu_neko09

＞2分探索木の場合はカタラン数の(2n)!/((n+1)!n!)？
n=3のとき、6!/4!3!=5で、形だけなら5通りですが、
以下の二分木を全て異なるものとして扱うと、5通りより多くなります。
　　　1　　　　　　　　2　　　　　　　　3　　　　　
　　 ／ ＼　　　 　　 ／ ＼　　　 　　 ／ ＼　　　
　　2　　　3　　 　　1　　　3　　 　　1　　　2　　

　　　2　　　　　　　2
　　 ／　　　　　　　 ＼
　　1　　　　　　　　　　3
　　 ＼　　　　　　　 ／
　　　　3　　　　　　 1

　　1　　　　　　　　1
　　 ＼　　　　　　　 ＼
　　　　2　　　　　　　　3
　　　　 ＼　　　　　 ／
　　　　　　3　　　　2

　　　　　　3　　　　 3
　　 　　／　　　　　 ／
　　　　2　　　　　　1
　　 ／　　　　　　　 ＼
　　1　　　　　　　　　　2

お礼

ありがとうございます

回答No.2

osu_neko09

式はわからないですけれども、２４，８１１，９２０とおりだと思われます。

計算結果はこちらに上げました。
http://blog.goo.ne.jp/admin/editentry?eid=aef7d70b705bb09778833f6e5396df59

お礼

すみませんそのURLをクリックしても自分のブログの編集画面にいってしまいます

回答No.1

boiseweb

「カタラン数 二分木」でウェブ検索すると，いいことあるかも．

お礼

二分探索木は上の数値より小さければ左、大きければ右という条件がありますが、同じ考え方でいいんでしょうか？