クラスタリングの場合の数

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

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
>