# Mathematical concepts

*By Afshine Amidi and Shervine Amidi*

## Combinatorics

### Factorial

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

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:

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

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:

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

### 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)$:

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

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

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:

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

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

### Fibonacci sequence

Fibonacci numbers $F_n$ are a sequence defined by:

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

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

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:

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

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 |

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 ofoperations | $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. |

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