by Hong-Yen, Wu | Dec. 2022
| Formula | Order relevant | Repetition | Memo | ||
|---|---|---|---|---|---|
| yes | no | # Permutations of size r from n distinct objects | |||
| no | no | # Selections/Combinations of size r from n distinct objects | |||
| yes | yes | # Arrangements with repetition of size r from n distinct objects | |||
| no | yes | # Selections with repetition of size r from n distinct objects |
| Formula | Memo | ||
|---|---|---|---|
| `C_n=[(2n)!]/[(n+1)!n!]` | # The first Catalan numbers for n = 1, 2, 3, 4, ... are 1, 1, 2, 5, ... | ||
| `[n(n+1)]/2` |
# Counts objects arranged in an equilateral triangle. for n = 1, 2, 3, 4, ... are 1, 3, 6, 10, ... |
||
| `H_n=sum_(k=1)^n(1/k)` | # The n-th harmonic number is the sum of the reciprocals of the first n natural numbers. | ||
| `F_n=F_(n-1)+F_(n-2) (n>=2)` |
# The sequence follows the rule that each number is equal to the sum of the preceding two numbers. # start as 1, 1 |
||
| `L_n=L_(n-1)+L_(n-2) (n>1)` |
# Similar to the Fibonacci numbers, each Lucas number is defined to be the sum of its two immediately previous terms. # start as 2, 1 |
| Formula | Memo | ||
|---|---|---|---|
| `A(n,m)` | # The number of permutations of the numbers 1 to n in which exactly m elements are greater than the previous element. | ||
| `S(n, k)` | # The number of ways to partition a set of n objects into k non-empty subsets. |