Re: Combinatorica problem
- To: mathgroup at smc.vnet.net
- Subject: [mg38976] Re: Combinatorica problem
- From: may106 at psu.edu (Nafod40)
- Date: Thu, 23 Jan 2003 08:04:50 -0500 (EST)
- References: <b0jfo5$t8c$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
guillerm at usal.es wrote ...
> Dear group,
> I have m balls shared in n box. What is the probability that one box has r o
> more balls?
>
> If m = 4, n=3 and r = 2 the solution will be (?):
>
> In[1] := Needs["DiscreteMath`Combinatorica`"]
>
> In[2] := list = Compositions[4,3];
>
> In[3] := (Count[list,2,2]+Count[list,2,3]+Count[list,2,4])/(3 Length[list])
>
> The question is that this way works only when m and n are small , but for
> values sush as m=20, n=11 and r=5 the computer is out of memory. Any idea?
Two brute force-type methods that use functions in combinatoria:
1) Given m and n, initialize a Composition c={m,0,...,0} so it is a
set of Length[c]=n. Now repeatedly call c=NextComposition[c], testing
each iteration to see if it meets your criteria. Stop when you get
c={0,...,0,m}.
2) Repeatedly call RandomComposition[m,n] and test, using a sample
size such that you have confidence that the probability calculated via
Monte Carlo is "close enough".