How many ways can I put m objects into n bins such that at least 1 bin has at least k objects? In other words, how many positive integer solutions are there to
$x_1+x_2+...+x_n = m \text{ such that at least one } x\geq k$
I'm not sure how to approach this problem. Usually, with constraints, we can "artificially inflate" variables but in this case, we don't have a specific variable that must satisfy a constraint. I tried accounting for 1 variable at a time, then summing it up for all $x_{1-n}$, but then there's overlap.
 A: The overlaps can be handled systematically with Inclusion-Exclusion.
Let $A_j$ be the set of those solutions where $x_j\geq k$. The quantity we're after, denote it by $f(m, n, k)$, is the size of their union. By Inclusion-Exclusion
$$f(m,n,k) = \left|\bigcup_{j=1}^n A_j \right |
= \sum_{\emptyset \neq J \subset [n]} (-1)^{|J|+1} \left|\bigcap_{j\in J} A_j \right |
$$
Size of the intersection is the number of those solutions where the variables $x_j$ for $j\in J$ are at least $k$. This is given by (do the "artificial inflation")
$$
\left|\bigcap_{j\in J} A_j \right | = {m-|J|(k-1)-1 \choose n-1}.
$$
Notice that this depends only on the size of the index set $J$, so we can enumerate them by $r = |J|$. There are $n \choose r$ index sets with $|J|=r$ so we get
$$
f(m,n,k) = \sum_{r=1}^n (-1)^{r+1} {n \choose r} {m-r(k-1)-1 \choose n-1}.
$$
Note: if $m < nk$, the sum only needs to go up to $\left\lfloor \frac{m-n}{k-1} \right\rfloor$. And if $m\geq nk$, it's guaranteed that some variable is at least $k$ and we get the total number of compositions of $m$ into $n$ parts, i.e.  $m-1 \choose n-1$.
