wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> No of Independent Event..
        
(Message started by: k3rn3l on Feb 14th, 2009, 10:21am)
Title: No of Independent Event..
Post by k3rn3l on Feb 14th, 2009, 10:21am
Given n ( Sample Space = S)  and two events  A (subset of S ) and B ( subset of S)..How many possible combo of A  & B will be independent event..??

n can be considered to be a dice with n faces wth equal probability of each face..

Like for example n = 3;
Total number of independent event is 13

Here it is :

Code:
(1,2,3)     ( 1 )
(1,2,3)     ( 2 )
(1,2,3)     ( 3 )
(1,2,3)     ( 1,2 )
(1,2,3)     ( 1,3 )
(1,2,3)     ( 2,3 )

total = 6;

Reversing the set : again 6 so total = 12;
and one combo is (1,2,3) and (1,2,3)
therefore total = 13;



Quote:
independent event  A and B if:

P ( A intersection B) = P(A) * P(B);

I know the value will increase rapidly with n ...so output will be d value  after taking mod of 100000000.

Thnks in advance...i tried it solving for 2 hrs but i m not able..!!

Some ans i may give...for ur checking:
n = 6 ---->  845
     7 ---->  253
     8 ----> 7509
     9 ---->16141


Code:
and i have another question T(n) = 1/sqrt(n)..
what will be T(n)..??
Title: Re: No of Independent Event..
Post by towr on Feb 14th, 2009, 1:26pm
Here's a bit of javascript that solves the first problem in O(n3)-ish time.
There's definite room for improvement, though (e.g. you can solve for c) . But I don't plan on working on this any more tonight.

Code:
<script>

function fac(n)
{
 if (n < 2) return 1;
 return n * fac(n-1);
}

for(s=1; s < 10; s++)
{
 t=0;
 for(a=0; a <=s; a++)
   for(b=0; b <=s; b++)
     for(c=1;  a+b+c <= s ; c++)
       if (c*s == (a+c)*(b+c))
       {
         t += fac(s)/fac(a)/fac(b)/fac(c)/fac(s-a-b-c)
       }

 document.write("s: " + s + "  " + t + "<br>");

}
document.close();

</script>


It's interesting how the results of prime numbers jump out. (Although not surprising, once you understand how this algorithm works)
Title: Re: No of Independent Event..
Post by Eigenray on Feb 14th, 2009, 6:54pm
Using the same formula, a Mathematica one-liner:

Code:
Sum[Total[s!/(c!(#-c)!(s c/#-c)!(s - # - s c/# + c)!) &/@Select[Divisors[s c], c <= # <= s &]], {c,1,s}]


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board