Distribution of Function of Random Vector N, K, and i are positive integers for the following:
Let the random vector X be represented by < X1, X2, ... , XN >, where X1, X2, ... XN are all random variables which follow a discrete uniform distribution with parameters 1 and K. Hence, P(Xi = xi) = 1/K on 1 <= xi <= K for 1 <= i <= N.
Let the random variable Y = f(X vector) = the number of distinct entries in X vector.
So, for example, if N = 3 and K = 9:
f(<1, 1, 1>) = 1
f(<1, 2, 1>) = 2
f(<1, 2, 3>) = 3
f(<3, 1, 3>) = 2
f(<9, 9, 9>) = 1
f(<1, 8, 8>) = 2
etc.
What is the distribution of Y?
I could only figure this out by writing some Python code, putting the sequences of integers I obtained into OEIS, looking up the functions which generated those sequences, and then trying to reverse engineer the probability mass function from there.  I think it worked, but it honestly took a lot of guessing:
PMF of Y
on 1 <= y <= K
Do any of you have a more intuitive explanation for this, if I'm even correct?  If so, can you prove it?
 A: For $i=1,\dots,K$ let $E_{i}$ denote the event that $i\notin\left\{ X_{1},\dots,X_{N}\right\} $.
Then:
$$\begin{aligned}\mathsf{P}\left(Y=y\right) & =\binom{K}{y}\mathsf{P}\left(E_{1}^{\complement}\cap\cdots\cap E_{y}^{\complement}\cap E_{y+1}\cap\cdots\cap E_{K}\right)\\
 & =\binom{K}{y}\mathsf{P}\left(E_{1}^{\complement}\cap\cdots\cap E_{y}^{\complement}\mid E_{y+1}\cap\cdots\cap E_{K}\right)\mathsf{P}\left(E_{y+1}\cap\cdots\cap E_{K}\right)
\end{aligned}
$$
With IEP we find:
$$\begin{aligned}\mathsf{P}\left(E_{1}^{\complement}\cap\cdots\cap E_{y}^{\complement}\mid E_{y+1}\cap\cdots\cap E_{K}\right) & =1-\mathsf{P}\left(E_{1}\cup\cdots\cup E_{y}\mid E_{y+1}\cap\cdots\cap E_{K}\right)\\
 & =\sum_{i=0}^{y}\binom{y}{i}\left(-1\right)^{i}\mathsf{P}\left(E_{1}\cap\cdots\cap E_{i}\mid E_{y+1}\cap\cdots\cap E_{K}\right)\\
 & =\sum_{i=0}^{y}\binom{y}{i}\left(-1\right)^{i}\left(\frac{y-i}{y}\right)^{N}
\end{aligned}
$$
Further we have: $$\mathsf{P}\left(E_{k+1}\cap\cdots\cap E_{K}\right)=\left(\frac{y}{K}\right)^{N}$$
So we end up with:
$$\begin{aligned}\mathsf{P}\left(Y=y\right) & =\binom{K}{y}\left(\frac{y}{K}\right)^{N}\sum_{i=0}^{y}\binom{y}{i}\left(-1\right)^{i}\left(\frac{y-i}{y}\right)^{N}\\
 & =\binom{K}{y}\sum_{i=0}^{y}\binom{y}{i}\left(-1\right)^{i}\left(\frac{y-i}{K}\right)^{N}
\end{aligned}
$$
