# Thread: computing the number of combinations

1. Essentially what I have tried to do in the above code is to calculate
1=C(n-r,0) => C(n-r+1,1) => C(n-r+2,2) ... => C(n-r + r,r)=C(n,r)
by using the iterative formula
C(n+1,r+1)=( (n+1)*C(n,r))/(r+1)

2. I tried it pinko but it does not work. I found my mistake in the code. I should use double as a data type not int.

3. Originally Posted by clover
I tried it pinko but it does not work
For what input?
It works for me fine.
Give me an n and a r for which it does not work.

My output for n=30
choose1(30,0)=1
choose1(30,1)=30
choose1(30,2)=435
choose1(30,3)=4060
choose1(30,4)=27405
choose1(30,5)=142506
choose1(30,6)=593775
choose1(30,7)=2035800
choose1(30,8)=5852925
choose1(30,9)=14307150
choose1(30,10)=30045015
choose1(30,11)=54627300
choose1(30,12)=86493225
choose1(30,13)=119759850
choose1(30,14)=145422675
choose1(30,15)=155117520
choose1(30,16)=145422675
choose1(30,17)=119759850
choose1(30,18)=86493225
choose1(30,19)=54627300
choose1(30,20)=30045015
choose1(30,21)=14307150
choose1(30,22)=5852925
choose1(30,23)=2035800
choose1(30,24)=593775
choose1(30,25)=142506
choose1(30,26)=27405
choose1(30,27)=4060
choose1(30,28)=435
choose1(30,29)=30
choose1(30,30)=1

4. Originally Posted by clover
I tried it pinko but it does not work. I found my mistake in the code. I should use double as a data type not int.

5. for n=14 r=11

6. 31 C 15 : For function choose1() results were 14209041 correct value is 300540195. The values from that depth on breaks down. Same results for function choose().

7. Originally Posted by clover
for n=14 r=11
I am getting 364 which is the correct answer.

8. Originally Posted by Thantos
31 C 15 : For function choose1() results were 14209041 correct value is 300540195. The values from that depth on breaks down. Same results for function choose().
That is an over flow, error, 31 is hitting the bar using this method.
Still if you want to push the bar further accumulate products in higher precision.
Code:
```#include <stdio.h>

unsigned long long
choose1(unsigned long n, unsigned long r) /*non recursive version*/
{
unsigned long long comb=1,num,den;
if( 2*r>n) r=n-r;
if( (r<0) || (r>n) ) return 0;/*error*/
for(num=n-r,den=0;num<n;num++,den++)
{
comb = ( (num+1)*comb )/(den+1);
}
return comb;
}

int
main(void)
{
unsigned long n,i;
printf("Give n\n");
scanf("%lu",&n);
printf("n=%lu\n",n);
for(i=0;i<=n;i++)
{
printf("choose1(%lu,%lu)=%llu\n",n,i,choose1(n,i));
}
return 0;
}```
choose1(31,15) is 300540195 as you want.
But you will of course find sufficiently large values of n for which this will break.

9. I corrected the code above a bit

10. The above code will work for C(n,r) iff
n*C(n-1,r-1) < 2**32-1
It should ULLONG_MAX above, or 2**64-1

11. And that is why I choose to use the reduction method instead. Slower yes, more memory yes, larger range of accurate numbers yes.

12. Thantos,
What is the smallest value of C(2n,n) for which your method fails?

13. It fails at n 35 r 15 is the first failing point. n 36 r 18 is the 2n, n failing point.
Using the long long int format the 2n,n failing point appears to be 70,35

14. Originally Posted by Thantos
It fails at n 35 r 15 is the first failing point. n 36 r 18 is the 2n, n failing point.
Using the long long int format the 2n,n failing point appears to be 70,35
For my code its (64,32) so you are squeezing five more bionomial sequences.