Combinatorics¶

Permutations¶

Permutations are the number of ways to arrange a set of objects.
The number of permutations of \(n\) objects is \(n!\).
The number of permutations of \(n\) objects taken \(r\) at a time is \(P(n, r) = \frac{n!}{(n-r)!}\).
The number of permutations of \(n\) objects taken \(r\) at a time with repetition is \(n^r\).

Combinations are the number of ways to select a subset of objects.
The number of combinations of \(n\) objects taken \(r\) at a time is \(C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}\).
The number of combinations of \(n\) objects taken \(r\) at a time with repetition is \(C(n+r-1, r)\).

\(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\)
Sum of the first \(n\) squares: \(\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\)
Sum of the first \(n\) cubes: \(\sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4}\)
Sum of the first \(n\) even numbers: \(\sum_{i=1}^{n} 2i = n(n+1)\)
Sum of the first \(n\) odd numbers: \(\sum_{i=1}^{n} (2i-1) = n^2\)
Sum of the first \(n\) powers of 2: \(\sum_{i=0}^{n} 2^i = 2^{n+1} - 1\)
Sum of the first \(n\) powers of 3: \(\sum_{i=0}^{n} 3^i = \frac{3^{n+1} - 1}{2}\)

Binomial Expansion: The number of terms in the expansion of \((a+b)^n\) is \(n+1\).
Trinomial Expansion: The number of terms in the expansion of \((a+b+c)^n\) is \(\frac{(n+1)(n+2)}{2}\).
Multinomial Expansion: The number of terms in the expansion of \((a_1+a_2+...+a_k)^n\) is \(\binom{n+k-1}{k-1}\).