Abstract


  • is the number of ways, disregarding order, that objects can be chosen from among objects


  • Also known as the number of k-element Subset (or k-combinations) of a n-element Set

  • , because given a set of 2 elements for example, there are 2 subsets of 1 elements: and

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 or

Coefficient

  • Chinese name is 系数
  • Constant Factor that multiplies a variable
  • For example, is the coefficient of

So why is it called Binomial Coefficient?

  • Binomial Coefficient means it calculates the Coefficient of a binomial expression
  • As you can see from the equation above, calculates the Coefficient of the terms of the expanded Binomial
  • The term is expressed as

Formula 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 . 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

Exponential Time Complexity

For , 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 and the result are within the range of long, we will not face any overflow issue

Formula 2

  • 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, will overcount. To counter this, we introduce the Divisor and to avoid overcounting and only count the combination we want

  • means how many ways to choose elements from element where the order matters

  • removes the counting that has the same set of elements


  • Below is an implementation of formula 2 in Java

Linear Time Complexity

For , Formula 1 takes a few ms, while Formula 2 only takes 0ms

Overflow Issue

Try change the from to in the editor above, you should get an overflow error. Because 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

Sum of Coefficient

  • If both and are 1, then 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
  • calculates the overall probability for a specific outcome
  • is the number of successes in the specific outcome
  • is the number of independent attempt
  • is the probability of success in each attempt, is the probability of having successes
  • 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
  • is the probability of having one such specific outcome

References