0
$\begingroup$

I have to compute (m+n)!/(m!)(n!) where m>=n.

Due to overflow constraints, I cannot calculate (m+n)! as it might exceed size of variable (int). To overcome this difficulty, one solution is to do the following :

Observe that the original problem can be reduced to (m+1)(m+2)...(m+n)/(n!)

We do the following :

integer result = 1, j=1;

for(integer i = m+1; i <= m+n; i++)

{
result = result * i;
result = result / j;
j=j+1; }

return result;

I do understand that a sequence of k consecutive integers will consist of a multiple of k (periodicity), but situation above isn't that straight forward. Since we are also dividing at each step, how do I show that although the resulting product is no longer a product of "consecutive" integers, we can still divide in this iteration by j.

Crude example, let sequence be 39,40,41,42,43. Here division by 2 utilises 40, so does 4, and 5 (in their respective iterations), but after division by 2, product is no longer of consecutive integers - why "division by 2" is not affecting "division by 4" despite both utilising integer 40.

$\endgroup$
3
  • $\begingroup$ So you want to prove that $\displaystyle \frac {(m+n)!} {(m!)(n!)} = \displaystyle \frac{ (m+1)(m+2)...(m+n)} {(n!)} \text{ ??} $ $\endgroup$
    – Constantinos Pisimisis
    Commented Oct 23, 2022 at 13:56
  • $\begingroup$ @ConstantinosPisimisis Well that is provable via expansion. Consider a sequence 41,42,43,44,45 -algorithm above will produce integer at each step and this is easy to verify because these are respectively divisible by 1,2,3,4,5. But algorithm will product integer for a "out of sync" sequence like 39,40,41,42,43 as well. But 41 is not divisible by 3, 42 is not divisible by 4, 43 is not divisible by 5. Why? Why is division of 40 by 2, not hampering division of (40->20) by 4 later? $\endgroup$
    – Ajax
    Commented Oct 23, 2022 at 14:15
  • $\begingroup$ Related: How do I compute binomial coefficients efficiently? $\endgroup$
    – JMoravitz
    Commented Oct 23, 2022 at 14:37

1 Answer 1

Reset to default
1
$\begingroup$

So you want to prove that each step of your algorithm produces an integer, i.e. the prefix products $\prod_{i=1}^k \frac{m + i}{i}$ is an integer for all $k = 1, 2, \ldots, n$ (we will just prove it for all $k$). This is true because, well, $\prod_{i=1}^k \frac{m+i}{i} = \frac{(m+k)!}{m!k!}=\binom{m+k}{k}$, which is an integer. See this for a proof.

$\endgroup$
2
  • 1
    $\begingroup$ He doesn't want to prove that the result is integer but he wants to avoid overflow that may occur and the variable type int shows error, $\endgroup$
    – Constantinos Pisimisis
    Commented Oct 23, 2022 at 14:02
  • $\begingroup$ @ConstantinosPisimisis Well firstly I proved more than that the result is integer, but also that the intermediate results are integer. OP also asked us to show that each of the intermediate steps of "x39 /1 x40 /2 x41 /3 x42 /4 x43 /5" will still produce an integer, since in programming languages dividing integers by integers will produce the floor of the result (5 / 2 = 2), and so I showed what he required. If he wants to avoid overflow, there are probably various ways to bound the intermediate values, but one way might be just to use chinese remainder theorem + Lucas's Theorem. $\endgroup$
    – Gareth Ma
    Commented Oct 23, 2022 at 14:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .