count integral solutions to equation using probability

44 Views Asked by At

I am working on a computer algorithm to find the number of positive integral solutions to the equation- $$ l_1 + l_2 +l_3+ \cdots +l_m=h $$ where - $$ 1\leq l_i\leq n $$ The known approach is of binomial coefficients. But factorials exceed max data type size. I want to use probability. Suppose an n-sided dice is rolled m-times, total number of possibilities = $$n^m$$ , so probability of getting sum as h = No. of integral solutions / (n ^ m). To find probability, loop_m_times(a = a + random_1_to_n() ) run this code a large no. b times. Count no. of times a=h and divide it by b, to get probability. Will this algorithm give accurate answer to the original question ?

1

There are 1 best solutions below

0
On BEST ANSWER

For large (or even moderate) values of $n, m, h$ you will have # of integral solutions $\ll n^m$, so the number of runs to get a relevant precision, or even to hit an integral solution will be prohibitive.