Binomial Coefficient

Abstract

$(k n)$ is the number of ways, disregarding order, that $k$ objects can be chosen from among $n$ objects
Also known as the number of k-element Subset (or k-combinations) of a n-element Set
$(1 2) = 2$ , because given a set of 2 elements ${1, 2}$ for example, there are 2 subsets of 1 elements: ${1}$ and ${2}$

Binomial

Bi means two

Chinese name is 二项式

A mathematical expression or algebraic equation that consists of two terms connected by a plus or minus sign, general form is $(a + b)$ or $(a - b)$

Coefficient

Chinese name is 系数

Constant Factor that multiplies a variable

For example, $5$ is the coefficient of $5 x$

So why is it called Binomial Coefficient?

$(a + b)^{n} = (0 n) a^{n} b^{0} + (1 n) a^{n - 1} b^{1} + \dots + (n - 1 n) a^{1} b^{n - 1} + (n n) a^{0} b^{n}$

Binomial Coefficient means it calculates the Coefficient of a binomial expression

As you can see from the equation above, $(k n)$ calculates the Coefficient of the terms of the expanded Binomial $(a + b)^{n}$

The term is expressed as $a^{n - k} \times b^{k}$

Formula 1

(k n) = (k - 1 n - 1) + (k n - 1)

Formula 1 uses Recursion
The idea is to fix an element x in the set. If x is included in the subset, we have to choose k − 1 elements from n − 1 elements, or if x is not included in the subset, we have to choose k elements from n − 1 elements
There are two independent paths here, so we perform Rule of Sum
Since there is recursion involved, there is base case to terminate the recursion too. The base cases are $(0 n) = (n n) = 1$ . Because there is always exactly one way to construct an empty subset and a subset that contains all the elements
Below is an implementation of formula 1 in Java

Is the code editor above not showing the correct source code?

Here is a backup, please report the issue here or comment down below, so I can look into the issue. Thanks :)

class Binom {
  public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
      
    long res = binom(50,6);
    
    long endTime = System.currentTimeMillis();
    long elapsedTime = endTime - startTime;
    
    
    System.out.println("Elapsed time: " + elapsedTime + " milliseconds");
    System.out.println(res);
  }
  
  public static int binom(int n, int k) {
    if (n == k) return 1; // C(n,n)
    if (k == 0) return 1; // C(n,0)
 
    return binom(n-1, k) + binom(n-1, k-1);
  }
}

Exponential Time Complexity

For $(10 20)$ , formula 1 takes a few ms, while Formula 2 only takes 0ms

Likely to have timeout error

No Overflow Issue

As long as the given $n$ and the result are within the range of long, we will not face any overflow issue

Formula 2

(k n) = \frac{n !}{k ! ( n - k )!}

$n!$ calculates the Permutation of n-element where the order matters, so we will have more than one counting which has the same set of elements but different order. However Combination doesn’t care about the order. Thus, $n!$ will overcount. To counter this, we introduce the Divisor $k!$ and $(n - k)!$ to avoid overcounting and only count the combination we want
$\frac{n !}{( n - k )!}$ means how many ways to choose $k$ elements from $n$ element where the order matters
$\frac{n !}{k ! ( n - k )!}$ removes the counting that has the same set of elements
Below is an implementation of formula 2 in Java

Is the code editor above not showing the correct source code?

Here is a backup, please report the issue here or comment down below, so I can look into the issue. Thanks :)

class Binom {
  public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
      
    long res = binom(20,10);
    
    long endTime = System.currentTimeMillis();
    long elapsedTime = endTime - startTime;
    
    
    System.out.println("Elapsed time: " + elapsedTime + " milliseconds");
    System.out.println(res);
  }
  
  public static long binom(int n, int k) {
    long permutation = calFactorial(n) / calFactorial(n-k);
    long combination = permutation / calFactorial(k);
 
    return combination;
  }
  
  public static long calFactorial(long x) {
    long res = 1;
    for (int i=1; i<=x; i++) {
      if (Long.MAX_VALUE / i < res) {
        throw new ArithmeticException("Overflow during factorial calculation");
      }
 
      res *= i;
    }
    return res;
  }
}

Linear Time Complexity

For $(10 20)$ , Formula 1 takes a few ms, while Formula 2 only takes 0ms

Overflow Issue

Try change the $n$ from $20$ to $21$ in the editor above, you should get an overflow error. Because $21!$ is out of the range the long can cover

We can handle this with Scientific notation - Wikipedia, but this introduces extra logic

Binomial Coefficient Properties

Symmetry Property

(k n) = (n - k n)

Proof

For $(k n)$ :
$(k n) = \frac{n !}{k ! ( n - k )!}$
For $(n - k n)$ :
$(n - k n) = \frac{n !}{( n - k )! [ n - ( n - k )]!}$ $\frac{n !}{( n - k )! [ n - ( n - k )]!} = \frac{n !}{( n - k )! ( n - n + k )!}$ $\frac{n !}{( n - k )! ( n - n + k )!} = \frac{n !}{( n - k )! ( 0 + k )!}$ $\frac{n !}{( n - k )! ( 0 + k )!} = \frac{n !}{( n - k )! k !}$
Therefore $(k n) = (n - k n)$ , because:
$\frac{n !}{k ! ( n - k )!} = \frac{n !}{( n - k )! k !}$

Sum of Coefficient

(a + b)^{n} = k = 0 \sum n (k n) a^{n - k} b^{k}

If both $a$ and $b$ are 1, then $(1 + 1)^{n} = 2^{n}$ which is the Sum of Binomial Coefficient

Pascal’s Triangle

In Pascal’s Triangle, each value equals to the sum of two above values
And values at each row can be calculated using the Binomial Coefficient

Binomial Distribution

Overall probability for a specific outcome in a number of independent attempts, each attempt is either a success or failure and each has the same probability of success

P (k) = (k n) p^{k} (1 - p)^{n - k}

$P (k)$ calculates the overall probability for a specific outcome
$k$ is the number of successes in the specific outcome
$n$ is the number of independent attempt
$p$ is the probability of success in each attempt, $p^{k}$ is the probability of having $k$ successes
$(k n)$ is the Binomial Coefficient that calculates the total number of Combination of a certain composition of success and failures, the specific outcome refers to this particular composition of success and failures
$p^{k} (1 - p)^{n - k}$ is the probability of having one such specific outcome

CS Notes

Recent writing

VLAN

End-to-End Service Access Troubleshooting

File System Link

Explorer

Binomial Coefficient

Abstract

Formula 1

Formula 2

Binomial Coefficient Properties

Symmetry Property

Sum of Coefficient

Pascal’s Triangle

Binomial Distribution

References

Table of Contents

Mentioned by

Graph View