For $n, r \in \mathbb{N}$, $(X_1, ...,X_r)$ is an ordered partition of $[n]$ in $r$ non-empty sets, if $X_1,..., X_r$ are disjoint and non-empty subsets of $[n]$ for which it holds that $X_1 \cup ... \cup X_r = [n]$.
How can one prove that
for $I \in \binom {[r]}{k}$ with $k \in \mathbb{N_0}$ there exists exactly $(r-k)^n$ r-tuples $(X_1, ..., X_r)$ where
- $X_1, ..., X_r$ are disjoint subsets of $[n]$
- for all $i \in I$ the set $X_i$ is empty and
- $X_1 \cup ... \cup X_r = [n]$ holds
I found this here, but it answers a different question and I don't know if we can apply the same here. This proof used to give 3 points in our exam, so it shouldn't require a detailed answer to this extent. Any help is appreciated!
A tuple $(X_1,\dots, X_r)$ where $X_i$ is empty for all $i\in I$, corresponds exactly to a function $f$ from $[n]$ to $[r]\setminus I$. Namely, for any $x\in [n]$, $f(x)$ is the unique element $j$ of $[r]\setminus I$ for which $x\in X_j$, which exists because $(X_1,\dots, X_r)$ is a partition. Clearly, the number of such functions is $(|[r]-I|)^{|[n]|}=(r-k)^n$.