- 今、N個のサンプルがあって、これを2分岐木のクラスタに纏め上げたいとする
- 何通りの木の形状(トポロジー)があるんだろう?
- 漸化式で考える
がその数とする
である
のときを考える
まではわかっているとして、Nの場合を知りたいものとする
は
に分けることができる
- それぞれが
の分け方を持つ
まで数え上げると2回ずつ数えていることになる
の場合には、この
個の要素が作りうる2分岐木と
個の要素が作りうる2分岐木を取らせ得るから
という漸化式になるだろうか・・・
- これを計算すると・・・

numTreeTopology<-function(n=3){
tmp<-rep(0,n)
if(n==1){
tmp[1]<-1
}else if(n==2){
tmp[1]<-1
tmp[2]<-1
}else{
tmp<-rep(0,n)
tmp[1]<-1
tmp[2]<-1
for(i in 3:n){
for(j in 1:(i-1)){
tmp[i]<-tmp[i]+choose(i,j)*tmp[j]*tmp[i-j]/2
}
}
}
tmp
}> numTreeTopology(n=10)
[1] 1 1 3 15 105 945 10395 135135 2027025 34459425
>