Bash script for finding binomical coefficient

Question

I am trying to generate a function for a binomial coefficient. I'm using nCk=n!/(k!(n-k)!) formula for this.

My present code is :

function factorial {
  typeset n=$1
  (( n < 2 )) && echo 1 && return
  echo $(( n * $(factorial $((n-1))) ))
}

function nCk {
  echo $((factorial $1/$(( factorial $2 *factorial $(($1-$2)) ))  ))
}

But I'm getting errors since I might be messing with the syntax.

Answer 1

The error is in your nCk function:

nCk() {
    echo $(( $(factorial $1) / ( $(factorial $2) * $(factorial $(($1-$2))) )  ))
}

You need to be careful to enclose each subexpression in $( ) so that things like the * are not treated as arguments to the factorial function. Note that I've also changed the declaration to use the more widely compatible function syntax.

As @chepner has suggested in the comments below your question, this is not the best way to go about computing the binomial coefficient. One of the reasons for this is that you need to calculate the factorial, which gets very large very fast. The highest factorial I can compute using bash is 20!; any higher values cause integer overflow to occur:

$ factorial 20
2432902008176640000
$ factorial 21
-4249290049419214848

There are other ways to calculate the binomial coefficient, which don't require a factorial. The function below implements one of them:

nCk2() {
    num=1
    den=1

    if (( $2 < $1 - $2 )); then
        k=$2
    else
        k=$(( $1 - $2 ))
    fi

    for ((i = 1; i <= k; ++i)); do
        ((num *= $1 + 1 - i)) && ((den *= i))
    done
    echo $((num / den))
}

Using this approach, the coefficient can be calculated for higher values of n without suffering from integer overflow. As a pleasant side effect, the function is also much faster than the original as it doesn't call a recursive function several times.

Answer 2

Try this. The problem was with calling the factorial inside the subshell.

function nCk {
  echo $(($(factorial $1)/$(( $(factorial $2) * $(factorial $(($1-$2))) ))  ))
}