combinations for forest in disjoint datastructure

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.

Above text is from Algorithms and data analysis by Wessis.

I am quite poor in combinational maths, so i am not understanding above problem, i need help here in answering following questions.

1. How do we got 2/5 in above description?
2. How do we got 8/11 in above description?
3. Author has described only two models but at end of paragraph it is mentioned for differen开发者_开发技巧t models, what is third model?

Thanks for your help

---

Here is the answer for the first two questions:

1. Given five trees A, B, C, D, E what is the probability that E is included in a pair of randomly chosen trees?

   Since there are 10 pairs possible (AB, AC, AD, AE, BC, BD, BE, CD, CE, DE) and four of them (AB, AC, AD, AE) contain A the probability is 4/10 = 2/5.

2. Given five trees A={a}, B={b}, C={c}, D={d}, E={e,f,g,h} what is the probability that an element of E is included in a pair of randomly chosen items (where no two items are chosen from one tree)?

   There are 22 pairs of items (ab, ac, ad, ae, af, ag, ah, bc, bd, be, bf, bg, bh, cd, ce, cf, cg, ch, de, df, dg, dh) and 16 of them include one of (e,f,g,h) the probability is 16/22 = 8/11.