http://oshiete.goo.ne.jp/qa/6105548.html
について。
以下、f(a,b)は、二分木に追加されていない数字がa個あり、
二分木のうち枝とも葉とも決まっていないノードがb個ある状態と、
そのときの場合の数と定義する。
二分探索木のぱたーん数
根っこが9とおり、
9*f(8,1)--9*2756880=24811920
f(8,1)は2756880
1個ぶらさがるとき8*f(7,1)--8*168210
2個ぶらさがるとき28*f(6,2)--28*50400
f(7,1)は168210
1個ぶらさがるとき7*f(6,1)--7*11970
2個ぶらさがるとき21*f(5,2)--21*4020
f(6,2)は50400
0個ぶらさがるとき1*f(6,1)--1*11970
1個ぶらさがるとき6*f(5,2)--6*4020
2個ぶらさがるとき15*f(4,3)--15*954
f(6,1)は11970
1個ぶらさがるとき6*f(5,1)--6*1020
2個ぶらさがるとき15*f(4,2)--15*390
f(5,2)は4020
0個ぶらさがるとき1*f(5,1)--1*1020
1個ぶらさがるとき5*f(4,2)--5*390
2個ぶらさがるとき10*f(3,3)--10*105
f(4,3)は954
0個ぶらさがるとき1*f(4,2)--1*390
1個ぶらさがるとき4*f(3,3)--4*105
2個ぶらさがるとき6*f(2,4)--6*24
f(5,1)は1020
1個ぶらさがるとき5*f(4,1)--5*108
2個ぶらさがるとき10*f(3,2)--10*48
f(4,2)は390
0個ぶらさがるとき1*f(4,1)--1*108
1個ぶらさがるとき4*f(3,2)--4*48
2個ぶらさがるとき6*f(2,3)--6*15
f(3,3)は105
0個ぶらさがるとき1*f(3,2)--1*48
1個ぶらさがるとき3*f(2,3)--3*15
2個ぶらさがるとき3*f(1,4)--3*4
f(2,4)は24
0個ぶらさがるとき1*f(2,3)--1*15
1個ぶらさがるとき2*f(1,4)--2*4
2個ぶらさがるとき1*f(0,5)--1*1
f(4,1)は108
1個ぶらさがるとき4*f(3,1)--4*15
2個ぶらさがるとき6*f(2,2)--6*8
f(3,2)は48
0個ぶらさがるとき1*f(3,1)--1*15
1個ぶらさがるとき3*f(2,2)--3*8
2個ぶらさがるとき3*f(1,3)--3*3
f(2,3)は15
0個ぶらさがるとき1*f(2,2)--1*8
1個ぶらさがるとき2*f(1,3)--2*3
2個ぶらさがるとき1*f(0,4)--1*1
f(1,4)は4
0個ぶらさがるとき1*f(1,3)--1*3
1個ぶらさがるとき1*f(0,4)--1*1
f(3,1)は15
1個ぶらさがるとき3*f(2,1)--3*3
2個ぶらさがるとき3*f(1,2)--3*2
f(2,2)は8
0個ぶらさがるとき1*f(2,1)--1*3
1個ぶらさがるとき2*f(1,2)--2*2
2個ぶらさがるとき1*f(0,3)--1*1
f(1,3)は3
0個ぶらさがるとき1*f(1,2)--1*2
1個ぶらさがるとき1*f(0,3)--1*1
f(2,1)は3
1個ぶらさがるとき2*f(1,1)--2*1
2個ぶらさがるとき1*f(0,2)--1*1
f(1,2)は2
0個ぶらさがるとき1*f(1,1)--1*1
1個ぶらさがるとき1*f(0,2)--1*1
f(1,1)は1
1個ぶらさがるとき1*f(0,1)--1*1
について。
以下、f(a,b)は、二分木に追加されていない数字がa個あり、
二分木のうち枝とも葉とも決まっていないノードがb個ある状態と、
そのときの場合の数と定義する。
二分探索木のぱたーん数
根っこが9とおり、
9*f(8,1)--9*2756880=24811920
f(8,1)は2756880
1個ぶらさがるとき8*f(7,1)--8*168210
2個ぶらさがるとき28*f(6,2)--28*50400
f(7,1)は168210
1個ぶらさがるとき7*f(6,1)--7*11970
2個ぶらさがるとき21*f(5,2)--21*4020
f(6,2)は50400
0個ぶらさがるとき1*f(6,1)--1*11970
1個ぶらさがるとき6*f(5,2)--6*4020
2個ぶらさがるとき15*f(4,3)--15*954
f(6,1)は11970
1個ぶらさがるとき6*f(5,1)--6*1020
2個ぶらさがるとき15*f(4,2)--15*390
f(5,2)は4020
0個ぶらさがるとき1*f(5,1)--1*1020
1個ぶらさがるとき5*f(4,2)--5*390
2個ぶらさがるとき10*f(3,3)--10*105
f(4,3)は954
0個ぶらさがるとき1*f(4,2)--1*390
1個ぶらさがるとき4*f(3,3)--4*105
2個ぶらさがるとき6*f(2,4)--6*24
f(5,1)は1020
1個ぶらさがるとき5*f(4,1)--5*108
2個ぶらさがるとき10*f(3,2)--10*48
f(4,2)は390
0個ぶらさがるとき1*f(4,1)--1*108
1個ぶらさがるとき4*f(3,2)--4*48
2個ぶらさがるとき6*f(2,3)--6*15
f(3,3)は105
0個ぶらさがるとき1*f(3,2)--1*48
1個ぶらさがるとき3*f(2,3)--3*15
2個ぶらさがるとき3*f(1,4)--3*4
f(2,4)は24
0個ぶらさがるとき1*f(2,3)--1*15
1個ぶらさがるとき2*f(1,4)--2*4
2個ぶらさがるとき1*f(0,5)--1*1
f(4,1)は108
1個ぶらさがるとき4*f(3,1)--4*15
2個ぶらさがるとき6*f(2,2)--6*8
f(3,2)は48
0個ぶらさがるとき1*f(3,1)--1*15
1個ぶらさがるとき3*f(2,2)--3*8
2個ぶらさがるとき3*f(1,3)--3*3
f(2,3)は15
0個ぶらさがるとき1*f(2,2)--1*8
1個ぶらさがるとき2*f(1,3)--2*3
2個ぶらさがるとき1*f(0,4)--1*1
f(1,4)は4
0個ぶらさがるとき1*f(1,3)--1*3
1個ぶらさがるとき1*f(0,4)--1*1
f(3,1)は15
1個ぶらさがるとき3*f(2,1)--3*3
2個ぶらさがるとき3*f(1,2)--3*2
f(2,2)は8
0個ぶらさがるとき1*f(2,1)--1*3
1個ぶらさがるとき2*f(1,2)--2*2
2個ぶらさがるとき1*f(0,3)--1*1
f(1,3)は3
0個ぶらさがるとき1*f(1,2)--1*2
1個ぶらさがるとき1*f(0,3)--1*1
f(2,1)は3
1個ぶらさがるとき2*f(1,1)--2*1
2個ぶらさがるとき1*f(0,2)--1*1
f(1,2)は2
0個ぶらさがるとき1*f(1,1)--1*1
1個ぶらさがるとき1*f(0,2)--1*1
f(1,1)は1
1個ぶらさがるとき1*f(0,1)--1*1