On Wed, 24 Nov 2004 22:13:53 -0500 (EST), Jerry Grossman wrote: >This is all very nice but invalid for solving our problem. The >permutations in the situation given are NOT equally likely. >jerry
Yes, you are right, I missed the fact that the acceptable permutations are not equally likely. The only solution I found is the brute force approach, i.e., to construct a tree with
n braches from the root - 1-st level (n-1) braches from each 1-st level node - 2-nd level (n-2) braches from each 2-nd level node - 3-rd level . . . 2 branches from each (n-2)-nd level node - (n-1)-st level 1 branch from each (n-1)-st level node - n-th level
Each node or leaf is assigned a number from 1 to n, the condition being that an acceptable number does not appear in its path from the root and the node does not have a brother with the same number. Each node on the k-th level (k < n) is assigned the probability:
0, if its number is equal to k, 1/(n - k), if its number is not equal to k, but it has a brother with the number k, 1/(n - k + 1), if its number is not equal k and it does not have a brother with the number k.
Each leaf on the n-th level is assigned a probability equal to the product of probabilities in its path from the root. (If a zero probability appears anywhere in its path, the leaf is assigned probability 0.)
The probabilities of all leaves must add up to 1. The desired probability is equal to the sum of probabilities of the leaves with the number n.
n = 3: P(3) = 1/4 n = 4: P(4) = 5/36 n = 5: P(5) = 19/144
For a larger n, I would have to do some programming. In any case, a simmulation with random numbers for n = 3, 4, 5 was in agreement with the above probabilities and for n = 10, I got about P(10) ~ 0.075 +- 0.01.