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

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

OperationDescriptionIllustration
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:

OperationResultIllustration
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
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:

NaiveSafe
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!