Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Math Topics » discretemath

Topic: a gift exchange
Replies: 6   Last Post: Aug 10, 2013 11:20 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
John

Posts: 54
Registered: 12/6/04
Re: a gift exchange
Posted: Dec 14, 2004 9:07 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

I can understand building a tree up to n=5, but beyond that I am lost.
Can you please e-mail me

On 26 Nov 04 02:28:48 -0500 (EST), Vladimir wrote:
>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.
>
>Vladimir




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.