Re: Combinatorica problem
- To: mathgroup at smc.vnet.net
- Subject: [mg38967] Re: Combinatorica problem
- From: Mike Yukish <may106 at psu.edu>
- Date: Thu, 23 Jan 2003 08:03:12 -0500 (EST)
- Organization: Penn State University, Center for Academic Computing
- 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 ideas, both of which are brute force, and use some similar functions...
1) Use the NextComposition[ ] function, starting with list {m,0,0,...,0}] and
iterating through to {0,...,0,m}, counting the ones that meet your constraint.
Divide this by NumberOfComposition[m,n]. This gives exact answer.
2) Run RandomComposition[m,n] a fixed number of times, counting the ones that
meet your constraint, divided by number of times run. This gives approximate
answer. You could monitor the run, and stop on some convergence property.