algorithm - 不相交数据结构中森林的组合

Question

The average-case analysis is quite hard to do for disjoint data structure. The least of the problems is that the answer depends on how to define average (with respect to the union operation). For instance, in the forest given below. For description purpose each tree is represented by set.

{0}、{1}、{2}、{3}、{4、5、6,8}

we could say that since there are five trees, there are 5 * 4 = 20 equally likely results of the next union (as any two different trees can be unioned). Of course, the implication of this model is that there is only a 2/5 chance that the next union will involve the large tree.

Another model might say that all unions between any two elements in different trees are equally likely, so a larger tree is more likely to be involved in the next union than a smaller tree. In the example above, there is an 8/11 chance that the large tree is involved in the next union, since (ignoring symmetries) there are 6 ways in which to merge two elements in {1, 2, 3, 4}, and 16 ways to merge an element in {5, 6, 7, 8} with an element in {1, 2, 3, 4}. There are still more models and no general agreement on which is the best. The average running time depends on the model; O(m), O(m log n), and O(mn) bounds have actually been shown for three different models, although the latter bound is thought to be more realistic.

以上文字来自Wessis的Algorithms and data analysis。

我的组合数学很差，所以我不明白上面的问题，我需要帮助回答以下问题。

1. 我们如何在上面的描述中得到 2/5？
2. 我们如何得到上述描述中的 8/11？
3. 作者只描述了两个模型，但在段落末尾提到了不同的模型，第三个模型是什么？

谢谢你的帮助

Answer 1

前两个问题的答案如下:

1. 给定五棵树 A、B、C、D、E，E 包含在一对随机选择的树中的概率是多少？

   因为有 10 对可能(AB、AC、AD、AE、BC、BD、BE、CD、CE、DE)并且其中四对(AB、AC、AD、AE)包含 A，所以概率是 4/10 = 2/5。

2. 给定五棵树 A={a}, B={b}, C={c}, D={d}, E={e,f,g,h} 一个概率是多少E 的元素包含在一对随机选择的项目中(其中没有从一棵树中选择两个项目)？

   有 22 对项目 (ab, ac, ad, ae, af, ag, ah, bc, bd, be, bf, bg, bh, cd, ce, cf, cg, ch, de, df, dg,dh)，其中16个包含(e,f,g,h)之一的概率是16/22 = 8/11。