What is the number of ways to color $m$ distinct objects using $n$ colors such that at least $k$ colors are used?
For example, for $n=4, m=2, k=2$, the answer is
$$\binom{4}{2} \cdot 2! = 12$$
Here it is straight-forward as $k=m$. How do I solve when $k < m$?
Let $A_i$ be the set of colorings which do not use the $i^{th}$ color. We want to count the number of colorings which use at least $k$ colors, which means there are at most $n-k$ values of $i$ for which the coloring is in $A_i$. Using a generalization of the inclusion-exclusion principle presented here, equation (8), we get $$ \begin{align} \text{# colorings with at least $k$ colors} &=\text{# colorings in at most $n-k$ of the sets $A_i$} \\&=\sum_{j=0}^n(-1)^{j-(n-k)}\binom{n}{j}\binom{j-1}{n-k}|A_1\cap \dots \cap A_j| \end{align} $$ The case $j=0$ of this sum requires special attention. In this case, we get $(-1)^{n-k}\binom{n}0\binom{-1}{n-k}$ times the size of the empty intersection. The empty intersection is just the whole universe of colorings, of which there are $n^m$. Also, $\binom{-1}{n-k}=(-1)^{n-k}$, so this summand is just $n^m$. Furthermore, for $1\le j \le n-k$, we have $\binom{j-1}{n-k}=0$, so we can omit these. Finally, $|A_1\cap \dots \cap A_j|=(n-j)^m$, since there are $j$ fewer colors available. Therefore, we can write this as $$ \begin{align} \text{# colorings with at least $k$ colors} &=n^m+\sum_{j=n-k+1}^n(-1)^{j-(n-k)}\binom nj\binom{j-1}{n-k}(n-j)^m %\\&=n^m+\sum_{j=0}^{k-1}(-1)^{j-k}\binom nj\binom{n-j-1}{n-k}j^m \end{align} $$ This summation can be computed in $O(n\log m)$ time, as long as you pre-compute all of the binomial coefficients involved, and use exponentiation by squaring to find $(n-j)^m$. To quickly do the pre-computation, these identities are quite helpful: $$ \binom{n}{j+1}=\frac{n-j}{j+1}\binom{n}{j}\qquad \binom{j}{n-k}=\frac{j}{j-(n-k)}\binom{j-1}{n-k} $$ Edit After several edits, this is now correct. This Python code serves as a sanity check.