Skip to main content

Mathematical concepts

By Afshine Amidi and Shervine Amidi



The factorial n!n! of a given integer nn is defined as follows:

n!n×(n1)×...×2×1\boxed{n!\triangleq n\times(n-1)\times...\times2\times1}

By convention, 0!=10!=1.

Binomial coefficient

For given integers 0kn0\leqslant k\leqslant n, the notation (nk)\displaystyle\binom{n}{k} is read "nn choose kk" and is called a binomial coefficient. It is defined as follows:


For k,nNk, n\in\mathbb{N}^*, Pascal's rule gives a relationship between neighboring coefficients:


The evolution of binomial coefficients with respect to kk and nn can be visualized using Pascal's triangle:

Binomial theorem

The binomial theorem states that for x,yRx, y\in\mathbb{R} and nNn\in\mathbb{N}, we have:


We note that when x=y=1x=y=1, we have:



A combination is an arrangement of kk objects from a pool of nn objects where the order does not matter. The number of such arrangements is given by C(n,k)C(n, k):

C(n,k)=(nk)=n!k!(nk)!\boxed{C(n, k)=\binom{n}{k}=\frac{n!}{k!(n-k)!}}

For k=2k=2 choices among n=3n=3 elements, there are C(3,2)=3C(3, 2)=3 possible combinations.

Pigeonhole principle

Suppose nn items in mm containers, with n>mn > m. The pigeonhole principle states that at least one container has more than one item.


A permutation is an arrangement of kk objects from a pool of nn objects where the order matters. The number of such arrangements is given by P(n,k)P(n, k):

P(n,k)=C(n,k)×k!=n!(nk)!\boxed{P(n, k)=C(n, k)\times k!=\frac{n!}{(n-k)!}}

For k=2k=2 choices among n=3n=3 elements, there are P(3,2)=6P(3, 2)=6 possible permutations.


For 0kn0\leqslant k\leqslant n, we have P(n,k)C(n,k)P(n, k)\geqslant C(n, k).

Lexicographic ordering

Given a set of nn elements, the lexicographic ordering sorts the resulting P(n,n)=n!P(n, n) = n! permutations in an alphabetical way.

To illustrate this, the lexicographic ordering of the 3!3! permutations of {2,6,7}\{2, 6, 7\} is as follows:

We note that this way of ordering permutations can be applied to sets containing any type of ordered elements, such as integers and characters.

Next lexicographic permutation

Given an array A=[a0,...,an1]A=[a_0, ..., a_{n-1}] representing a permutation of the set of nn elements {a0,...,an1}\{a_0, ..., a_{n-1}\}, the goal of this problem is to find the next permutation in the lexicographic order.

The solution is found in O(n)\mathcal{O}(n) time and O(1)\mathcal{O}(1) space as follows:

  • Step 1: Find the largest index kk, such that ak<ak+1a_k < a_{k+1}.

If there is no such kk, go directly to Step 4 and use k=1k=-1.

  • Step 2: Find the largest index l>kl > k, such that ak<ala_k < a_l.

  • Step 3: Swap aka_{k} and ala_{l}.

  • Step 4: Reverse the subarray that starts from index k+1k+1.

Mathematical analysis


Given a set of ordered observations x1...xnx_1\leqslant ...\leqslant x_n, we can compute the following quantities:

Euclidean division

The Euclidean division of aNa\in\mathbb{N} by bNb\in\mathbb{N}^* finds the unique values of qNq\in\mathbb{N} and r{0,...,b1}r\in\{0, ..., b-1\} such that:


aa is called the dividend, bb the divisor, qq the quotient and rr the remainder.

This can be written in a different way using the modulo notation:

ar[b]\boxed{a\equiv r\hspace{0.25cm}[b]}

which is read "aa is equal to rr modulo bb".

Fibonacci sequence

Fibonacci numbers FnF_n are a sequence defined by:

Fn=Fn1+Fn2 with F0=0 and F1=1\boxed{F_n=F_{n-1}+F_{n-2}}\quad\textrm{ with }F_0=0\textrm{ and }F_1=1

They can be geometrically represented as follows:


The first ten numbers of the sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

Bit manipulation

Integer representation

The decomposition of an integer nn in base bb is unique and given by:

n=k=0+nkbkwhere nk{0,...,b1}\boxed{n=\sum_{k=0}^{+\infty}\texttt{n}_kb^k}\quad\textrm{where }\texttt{n}_k\in\{0, ..., b-1\}

The representation of nn in base bb can be equivalently written as:


The most commonly used bases are summarized in the table below:

Base bbPossible values nk\texttt{n}_kRepresentation
of n=154n=154
{0,1}\{0, 1\}(10011010)2(10011010)_2Logic
{0,...,9}\{0, ..., 9\}(154)10(154)_{10}Day-to-day life
{0,...,9,A,...,F}\{0, ..., 9, A, ..., F\}(9A)16(9A)_{16}Memory allocation

Binary number

A binary number is the representation of an integer nn in base 2. It is expressed as follows:

n=k=0+nk2kwhere nk{0,1}\boxed{n=\sum_{k=0}^{+\infty}\texttt{n}_k2^k}\quad\textrm{where }\texttt{n}_k\in\{0,1\}

Each nk\texttt{n}_k is called a binary digit, often abbreviated as bit. We note that:

  • If n0=0\texttt{n}_0=0, then nn is an even number.
  • If n0=1\texttt{n}_0=1, then nn is an odd number.

Bit notations

A binary number represented with NN bits has the following bit-related notations:

NotationDescriptionIllustration with N = 10
Least significant bitRight-most bit.
Lowest set bitRight-most bit that has a value of 1.
Highest set bitLeft-most bit that has a value of 1.
Most significant bitLeft-most bit.

The abbreviation "LSB" is sometimes ambiguous as it may either refer to the least significant bit or the lowest set bit.

Bitwise operators

The truth table of the bitwise operators OR\texttt{OR}, XOR\texttt{XOR}, AND\texttt{AND} between x{0,1}x\in\{0, 1\} and y{0,1}y\in\{0, 1\} is given below:

x  yx\textrm{ }\vert\textrm{ }yxyx\wedge yx & yx\textrm{ }\&\textrm{ }y

Bit shifting

Shifting operations change the binary representation of a number as follows:

"right shift"
Binary representation of x moved by y bits to the right.
"left shift"
Binary representation of x moved by y bits to the left.


The table below shows a few bit-related tricks that are useful in establishing non-trivial results with minimal effort:

x & (x−1)0 means that x is a power of 2
x&10 means that x is divisible by 2
1≪j2 to the power of j

The first trick stems from the fact that 2n1=k=0n12k\displaystyle2^{n}-1=\sum_{k=0}^{n-1}2^k.

Integer overflow

The problem of integer overflow occurs when the number of bits needed to encode an integer nn exceeds the number of available bits NN. More precisely, binary numbers encoded on NN bits cannot exceed 2N12^{N}-1.

This issue can sometimes be alleviated by changing the order in which operations are performed. For example, a safe way to average two integers aa and bb is shown below:

Formulaa+b2\displaystyle\frac{a+b}{2}a+ba2\displaystyle a+\frac{b-a}{2}
Order of
s2=s12\displaystyle s_2=\frac{s_1}{2}
s2=s12\displaystyle s_2=\frac{s_1}{2}
s3=a+s2\displaystyle s_3=a+s_2
s2=2322=231\displaystyle s_2=\frac{2^{32}}{2}=2^{31}
Step 1 led to integer overflow
because s1>2321s_1>2^{32}-1.
s2=02=0\displaystyle s_2=\frac{0}{2}=0
s3=231+0=231\displaystyle s_3=2^{31}+0=2^{31}
There was no integer overflow.

Want more content like this?

Subscribe here to be notified of new Super Study Guide releases!