2.3 Combination Function

Choose

## function (n, r) 
## {
##     if (is.nan(n) | is.nan(r) | n == -Inf | r == +Inf | r == 
##         -Inf) 
##         return(NaN)
##     if (n == +Inf) 
##         return(+Inf)
##     if (n < 0 | r < 0 | r > n | floor(n) != n | floor(r) != r) 
##         return(0)
##     if (r > n/2) 
##         r = n - r
##     if (r == 0) {
##         return(1)
##     }
##     else if (r == 1) {
##         return(n)
##     }
##     else {
##         Res = n
##         for (i in 2:r) {
##             Res = Res/i * (n - i + 1)
##             if (Res == +Inf) {
##                 return(Res)
##             }
##         }
##         return(Res)
##     }
## }
## <bytecode: 0x000001e2a8621338>
## <environment: namespace:math>

Choose(3, 1)

## [1] 3

Choose(4, 2)

## [1] 6

Choose(10, 5)

## [1] 252

Choose(100, 50)

## [1] 1.009e+29

Choose(1000, 500)

## [1] 2.703e+299

Choose(2000, 1000)

## [1] Inf

Comparison of Choose and choose R internal function. R internal choose function also uses gamma function.

CntChoose = 0
Cntchoose = 0
Tol = 1e-14
for (i in 2:100) {
  for (j in 1:i) {
    n0 = prod((i - j + 1):i)/prod(1:j)
    n1 = Choose(i, j)
    n2 = choose(i, j)
    RelDiff1 = abs(n1 - n0) / n0
    RelDiff2 = abs(n2 - n0) / n0
    if (RelDiff1 > Tol) {
      CntChoose = CntChoose + 1
      print(paste("Choose", CntChoose, i, j, paste(format(c(n0, n1), digits=22), collapse=" ")))
    }
    if (RelDiff2 > Tol) {
      Cntchoose = Cntchoose + 1
      print(paste("choose", Cntchoose, i, j, paste(format(c(n0, n2), digits=22), collapse=" ")))
    }
  }
}

## [1] "choose 1 89 32 1548024891640804561448020 1548024891640786039366026"
## [1] "choose 2 89 37 14869898879640287459264408 14869898879640100628206202"
## [1] "choose 3 89 52 14869898879640289606402686 14869898879640100628206202"
## [1] "choose 4 89 57 1548024891640804829864446 1548024891640786039366026"
## [1] "choose 5 90 44 101570303433476165704488600 101570303433474928752248202"
## [1] "choose 6 90 46 101570303433476148528864026 101570303433474928752248202"
## [1] "choose 7 91 41 132884211874988283624422428 132884211874989726736844624"
## [1] "choose 8 91 44 196657396009496385104826206 196657396009493464528864626"
## [1] "choose 9 91 47 196657396009496419466064464 196657396009493464528864626"
## [1] "choose 10 91 50 132884211874988300808006602 132884211874989726736844624"
## [1] "choose 11 92 45 402055120730526039082260240 402055120730519373380428248"
## [1] "choose 12 92 47 402055120730525970368284424 402055120730519373380428248"
## [1] "choose 13 93 36 76730709735928433186602028 76730709735929506920826028"
## [1] "choose 14 93 57 76730709735928441778868660 76730709735929506920826028"
## [1] "choose 15 94 37 194937478788574951828026844 194937478788577253920682000"
## [1] "choose 16 94 57 194937478788574951828026844 194937478788577253920682000"
## [1] "choose 17 96 47 6.303739115624129446102e+27 6.303739115624043683975e+27"
## [1] "choose 18 96 49 6.303739115624130545483e+27 6.303739115624043683975e+27"
## [1] "choose 19 97 33 87305137393412628306886244 87305137393413573192482664"
## [1] "choose 20 97 38 1.326167301635892758886e+27 1.326167301635907052465e+27"
## [1] "choose 21 97 45 9.969700941885360833544e+27 9.969700941885244285280e+27"
## [1] "choose 22 97 52 9.969700941885360833544e+27 9.969700941885244285280e+27"
## [1] "choose 23 97 59 1.326167301635892758886e+27 1.326167301635907052465e+27"
## [1] "choose 24 97 64 87305137393412628306886244 87305137393413573192482664"
## [1] "choose 25 98 38 2.166073259338624848631e+27 2.166073259338651236811e+27"
## [1] "choose 26 98 60 2.166073259338624848631e+27 2.166073259338651236811e+27"
## [1] "choose 27 99 33 197443926105102399728486444 197443926105100166346026624"
## [1] "choose 28 99 41 1.186869972588828183440e+28 1.186869972588844016487e+28"
## [1] "choose 29 99 47 4.473914826002394159489e+28 4.473914826002454852693e+28"
## [1] "choose 30 99 49 5.044567227278210109088e+28 5.044567227278144138421e+28"
## [1] "choose 31 99 50 5.044567227278210109088e+28 5.044567227278144138421e+28"
## [1] "choose 32 99 52 4.473914826002394159489e+28 4.473914826002454852693e+28"
## [1] "choose 33 99 58 1.186869972588828183440e+28 1.186869972588844016487e+28"
## [1] "choose 34 99 66 197443926105102399728486444 197443926105100166346026624"
## [1] "choose 35 100 37 3.420029547493937615915e+27 3.420029547493901332222e+27"
## [1] "choose 36 100 44 4.937823579707371518185e+28 4.937823579707319621331e+28"
## [1] "choose 37 100 50 1.008913445455642021926e+29 1.008913445455630762920e+29"
## [1] "choose 38 100 56 4.937823579707371518185e+28 4.937823579707319621331e+28"
## [1] "choose 39 100 63 3.420029547493938165822e+27 3.420029547493901332222e+27"

CntChoose # 0 discrepancies

## [1] 0

Cntchoose # 39 dicrepancies

## [1] 39

How about the maximum values to calculate?

for (i in 100:10000) {
  if (Choose(i*2, i) == +Inf) {
    print(i) # 515
    break
  }
}

## [1] 515

for (i in 100:10000) {
  if (choose(i*2, i) == +Inf) {
    print(i) # 515
    break
  }
}

## [1] 515

The above test shows the same capacity.

You can also test internal consistency using the following equality.

\[\binom{n}{r} = \binom{n - 1}{r} + \binom{n - 1}{r - 1}\]

xmax = 1020
n1 = Choose(xmax, xmax/2)
n1.r = Choose(xmax - 1, xmax/2) + Choose(xmax - 1, xmax/2 - 1)
RelDiff1 = (n1 - n1.r)/n1.r

n2 = choose(xmax, xmax/2)
n2.r = choose(xmax - 1, xmax/2) + choose(xmax - 1, xmax/2 - 1)
RelDiff2 = (n2 - n2.r)/n2.r

format(c(n1, n1.r), digits=22)

## [1] "2.806267768299625702672e+305" "2.806267768299621414609e+305"

format(RelDiff1, digits=22)

## [1] "1.527986107902366902291e-15"

format(c(n2, n2.r), digits=22)

## [1] "2.806267768299730562109e+305" "2.806267768299246804717e+305"

format(RelDiff2, digits=22)

## [1] "1.723846145370082218184e-13"