3.3.6 #

解答 #

由 3.3.5 可知，$N=6$ 时的树形只有一种。

因此我们只需要将 $N=6$ 记为概率 1，利用乘法原理（或者说分步计数）计算之后的概率即可。

$N=6$ 的树形，底部共有 7 个位置可以插入：

// 'D', 'G', 'K', 'O', 'S', 'Y'

 |--GO--|
D   K   SY

$N=7$ #

如果向 2-结点插入（示例中的 D 或 K），每个 2-结点有两个子树，概率均等，概率 $2/7 \times 2 = 4/7$，可以得到以下树形（记为 7-1）：

// after
|--GO--|
D   KL   SY

如果向 3-结点插入（3-结点有三个子树，概率均等，概率 $3/7$），可以得到以下树形（记为 7-2）：

       |--------O--------|
 |--G--|                 |--S--|
D       K               Q       Y

$N=8$ #

向 7-1 的唯一一个 2-结点插入（示例中的 D），概率 $4/7 \times 2/8= 1/7$，可以得到以下树形（记为 8-1）：

 |--GO--|
AD   KL   SY

向 7-1 的 3-结点插入（示例中的 KL 或 SY），或者向 7-2 的任意一个 2-结点插入，概率 $4/7 \times 6/8 + 3/7 = 6/7$，可以得到以下树形（记为 8-2）：

       |--------O--------|
 |--G--|                 |--S--|
D       K               Q       YZ

$N=9$ #

向 8-1 的最左或最右侧 3-结点插入（示例中的 AD 或 SY），或者向 8-2 底部 3-结点的兄弟 2-结点插入（示例中的 Q），概率 $1/7 \times 6/9 + 6/7 \times 2/9 = 2/7$，可以得到以下树形（记为 9-1）：

       |--------G--------|
 |--C--|                 |--O--|
A       D               KL       SY

向 8-1 的中间结点插入（示例中的 KL），或者向 8-2 底部左右子树均为 2-结点的子结点插入（示例中的 D 或 K），概率 $1/7 \times 3/9 + 6/7 \times 4/9 = 3/7$，得到以下树形（记为 9-2）：

       |--------K--------|
 |--G--|                 |--O--|
AD       J               L       SY

向 8-2 底部唯一的 3-结点插入（示例中的 YZ），概率 $6/7 \times 3/9 = 2/7$，得到以下树形（记为 9-3）：

       |--------O--------|
 |--G--|                 |--SY--|
D       K               Q   X   Z

$N=10$ #

向 9-1 的 2-结点插入（示例中的 A 或 D），或向 9-2 的 2-结点插入（示例中的 J 或 L），概率 $2/7 \times 4/10 + 3/7 \times 4/10 = 2/7$

       |--------G--------|
 |--C--|                 |--O--|
AB       D               KL       SY

向 9-1 底部任意 3-结点插入（示例中的 KL 或 SY），或向 9-3 中 3-结点的子结点插入（示例中的 Q 或 X 或 Z），概率 $2/7 \times 6/10 + 2/7 \times 6/10 = 12/35$。

       |--------O--------|
 |--G--|                 |--SY--|
D       K               PQ   X   Z

向 9-2 底部任意 3-结点插入（示例中的 AD 或 SY），或向 9-3 中 2-结点的子结点插入（示例中的 D 或 K），概率 $3/7 \times 6/10 + 2/7 \times 4/10 = 13/35$

       |--------O--------|
 |--G--|                 |--SY--|
D       JK               Q   X   Z