Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Replies: 6   Last Post: Aug 10, 2013 11:20 PM

 Messages: [ Previous | Next ]
 Vladimir Zajic Posts: 319 Registered: 12/3/04
Posted: Nov 26, 2004 2:28 AM

On Wed, 24 Nov 2004 22:13:53 -0500 (EST), Jerry Grossman wrote:
&gt;This is all very nice but invalid for solving our problem. The
&gt;permutations in the situation given are NOT equally likely.
&gt;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 &lt; 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.

Date Subject Author
11/23/04 John
11/24/04 Jerry Grossman