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 ]
 John Posts: 54 Registered: 12/6/04
Posted: Dec 14, 2004 9:07 PM

I can understand building a tree up to n=5, but beyond that I am lost.

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

Date Subject Author
11/23/04 John
11/24/04 Jerry Grossman
11/24/04 Jerry Grossman
12/14/04 John
8/10/13 Mark Rickert