Combination

Abstract

The selection of items from a larger set without considering the order of selection
The number of combinations can be calculated using the Binomial Coefficient

Binomial Coefficient

So what is 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}$

$(k n)$ gives the Coefficient of one of the term of the expansion Binomial $(a + b)^{n}$

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

Binomial

Bi means two
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

Constant Factor that multiplies a variable
For example, $5$ is the coefficient of $5 x$

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, and 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

No Overflow Issue

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

Formula 2

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

The divisor Divisor $k!$ and $(n - k)!$ avoid overcounting, $n!$ includes counting that have the same set of elements but different order
$\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 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(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 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 !}

$(k n) = (n - k n)$ , since:

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

References

Competitive Programmer’s Handbook

CS Notes

Recent Updates

 My Macos Setup

Atuin

Common Security Attacks

Explorer

Combination

Abstract

Binomial Coefficient

Binomial

Coefficient

Formula 1

Formula 2

Binomial Coefficient Properties

Symmetry Property

Proof

References

Table of Contents

Backlinks

Graph View