Combination

Abstract

The selection of items from a larger set without considering the order of selection. That means each combination has an unique set of items
The number of combinations can be calculated using the Binomial Coefficient

Binomial Coefficient

$(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

References

Competitive Programmer’s Handbook

CS Notes

Recent Updates

GPU

Graph Data Structure

Tree

Explorer

Combination

Abstract

Binomial Coefficient

Formula 1

Formula 2

Binomial Coefficient Properties

Symmetry Property

Sum of Coefficient

Pascal’s Triangle

References

Table of Contents

Backlinks

Graph View