The factorial of a given integer is defined as follows:
By convention, .
For given integers , the notation is read " choose " and is called a binomial coefficient. It is defined as follows:
For , Pascal's rule gives a relationship between neighboring coefficients:
The evolution of binomial coefficients with respect to and can be visualized using Pascal's triangle:
The binomial theorem states that for and , we have:
We note that when , we have:
A combination is an arrangement of objects from a pool of objects where the order does not matter. The number of such arrangements is given by :
For choices among elements, there are possible combinations.
Suppose items in containers, with . The pigeonhole principle states that at least one container has more than one item.
A permutation is an arrangement of objects from a pool of objects where the order matters. The number of such arrangements is given by :
For choices among elements, there are possible permutations.
For , we have .
Given a set of elements, the lexicographic ordering sorts the resulting permutations in an alphabetical way.
To illustrate this, the lexicographic ordering of the permutations of 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 representing a permutation of the set of elements , the goal of this problem is to find the next permutation in the lexicographic order.
The solution is found in time and space as follows:
- Step 1: Find the largest index , such that .
If there is no such , go directly to Step 4 and use .
- Step 2: Find the largest index , such that .
- Step 3: Swap and .
- Step 4: Reverse the subarray that starts from index .
Given a set of ordered observations , we can compute the following quantities:
The Euclidean division of by finds the unique values of and such that:
is called the dividend, the divisor, the quotient and the remainder.
This can be written in a different way using the modulo notation:
which is read " is equal to modulo ".
Fibonacci numbers 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.
The decomposition of an integer in base is unique and given by:
The representation of in base can be equivalently written as:
The most commonly used bases are summarized in the table below:
|Base||Possible values||Representation |
A binary number is the representation of an integer in base 2. It is expressed as follows:
Each is called a binary digit, often abbreviated as bit. We note that:
- If , then is an even number.
- If , then is an odd number.
A binary number represented with 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.
The truth table of the bitwise operators , , between and is given below:
Shifting operations change the binary representation of a number as follows:
|Binary representation of x moved by y bits to the right.|
|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&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 .
The problem of integer overflow occurs when the number of bits needed to encode an integer exceeds the number of available bits . More precisely, binary numbers encoded on bits cannot exceed .
This issue can sometimes be alleviated by changing the order in which operations are performed. For example, a safe way to average two integers and is shown below:
| || |
Step 1 led to integer overflow
There was no integer overflow.
Subscribe here to be notified of new Super Study Guide releases!