Mathematical concepts

By Afshine Amidi and Shervine Amidi

Combinatorics

Factorial

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

$$\boxed{n!\triangleq n\times(n-1)\times...\times2\times1}$$

Remark

By convention, $0!=1$.

Binomial coefficient

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

$$\boxed{\binom{n}{k}\triangleq\frac{n!}{k!(n-k)!}}$$

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

$$\boxed{\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}}$$

The evolution of binomial coefficients with respect to $k$ and $n$ can be visualized using Pascal's triangle:

Binomial theorem

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

$$\boxed{(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}y^k}$$

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

$$\sum_{k=0}^n\binom{n}{k}=2^n$$

Combination

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

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

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

Pigeonhole principle

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

Permutation

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

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

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

Remark

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

Lexicographic ordering

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

To illustrate this, the lexicographic ordering of the $3!$ permutations of $\{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=[a_0, ..., a_{n-1}]$ representing a permutation of the set of $n$ elements $\{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 $\mathcal{O}(n)$ time and $\mathcal{O}(1)$ space as follows:

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

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

• Step 2: Find the largest index $l > k$, such that $a_k < a_l$.

• Step 3: Swap $a_{k}$ and $a_{l}$.

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

Mathematical analysis

Statistics

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

Euclidean division

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

$$\boxed{a=bq+r}$$

$a$ is called the dividend, $b$ the divisor, $q$ the quotient and $r$ the remainder.

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

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

which is read "$a$ is equal to $r$ modulo $b$".

Fibonacci sequence

Fibonacci numbers $F_n$ are a sequence defined by:

$$\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:

Remark

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 $n$ in base $b$ is unique and given by:

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

The representation of $n$ in base $b$ can be equivalently written as:

$$\boxed{n=(...\texttt{n}_k...\texttt{n}_3\texttt{n}_2\texttt{n}_1\texttt{n}_0)_b}$$

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

Base $b$	Possible values $\texttt{n}_k$	Representation of $n=154$	Application
2 "binary"	$\{0, 1\}$	$(10011010)_2$	Logic
10 "decimal"	$\{0, ..., 9\}$	$(154)_{10}$	Day-to-day life
16 "hexadecimal"	$\{0, ..., 9, A, ..., F\}$	$(9A)_{16}$	Memory allocation

Binary number

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

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

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

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

Bit notations

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

Notation	Description	Illustration with N = 10
Least significant bit	Right-most bit.
Lowest set bit	Right-most bit that has a value of 1.
Highest set bit	Left-most bit that has a value of 1.
Most significant bit	Left-most bit.

Remark

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 $\texttt{OR}$, $\texttt{XOR}$, $\texttt{AND}$ between $x\in\{0, 1\}$ and $y\in\{0, 1\}$ is given below:

		$\texttt{OR}$	$\texttt{XOR}$	$\texttt{AND}$
		$x\textrm{ }\vert\textrm{ }y$	$x\wedge y$	$x\textrm{ }\&\textrm{ }y$
$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$1$	$0$
$0$	$1$	$1$	$1$	$0$
$1$	$1$	$1$	$0$	$1$

Bit shifting

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

Operation	Description	Illustration
x≫y "right shift"	Binary representation of x moved by y bits to the right.
x≪y "left shift"	Binary representation of x moved by y bits to the left.

Tricks

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

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

Remark

The first trick stems from the fact that $\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 $n$ exceeds the number of available bits $N$. More precisely, binary numbers encoded on $N$ bits cannot exceed $2^{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 $a$ and $b$ is shown below:

	Naive	Safe
Formula	$\displaystyle\frac{a+b}{2}$	$\displaystyle a+\frac{b-a}{2}$
Order of operations	$s_1=a+b$ $\displaystyle s_2=\frac{s_1}{2}$	$s_1=b-a$ $\displaystyle s_2=\frac{s_1}{2}$ $\displaystyle s_3=a+s_2$
Example	$s_1=2^{31}+2^{31}={\color{red}2^{32}}$ $\displaystyle s_2=\frac{2^{32}}{2}=2^{31}$ Step 1 led to integer overflow because $s_1>2^{32}-1$.	$s_1=2^{31}-2^{31}=0$ $\displaystyle s_2=\frac{0}{2}=0$ $\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!