Probability that exactly y of n rolls of an r-sided die are unique Consider an $r$-sided die that is rolled $n$ times.  What is the probability that of the $n$ rolls exactly $y$ of the rolls are unique?  
For example, consider $n = 2$ and $r = 3$.  The possibilities are
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

In this case, $P(y = 0) = 1/3$, $P(y = 1) = 0$, and $P(y = 2) = 2/3.$
I feel as though this should be a fairly simple problem to solve, but for the life of me I haven't been able to figure it out (I need this information to bound the behavior of an algorithm I'm working on).
 A: Define $F(n, k)$ to be the number of ways to allocate $k$ options to $n$ flips such that each option appears either 0 or $\geq 2$ times. Then the probability that you see exactly $y$ unique values when you roll a $k$-sided dice $n$ times is:
$$
Pr(Y=y) = \frac{{k\choose y}{n\choose y}y!F(n-y, k-y)}{k^n}
$$
Basically, there are ${k \choose y}$ ways to select the $y$ unique options from all $k$ options, ${n\choose y}$ ways to select the $y$ rolls for these unique options, and $y!$ orderings of the $y$ options within these rolls.
All that remains is to compute $F(n, k)$. There are a few simple cases and then a recursive definition:
\begin{align*}
F(0, k) &= 1 &\forall~k\geq 0 \\
F(1, k) &= 0 &\forall~k\geq 0 \\
F(n, 0) &= 0 &\forall~n\geq 1 \\
F(n, k) &= F(n, k-1) + \sum_{i=2}^n {n\choose i}F(n-i, k-1) &\forall~n\geq 2, k\geq 1
\end{align*}
The recursive step selects an arbitrary option and separately considers the number of allocations for which it appears $0, 2, 3, \ldots, n$ times. This formulation enables the calculation of the entire pmf in $O(n^2k)$ runtime, which should be a good deal more efficient than summing over all valid partitions of the multinomial distribution. Here's an R implementation:
uniquePMF <- function(n, k) {
  F <- matrix(0, nrow=n+1, ncol=k+1)
  F[1,] <- 1
  for (.k in 1:k) {
    for (.n in 2:n) {
      F[.n+1,.k+1] <- F[.n+1,.k] + sum(choose(.n, 2:.n)*F[.n-(2:.n)+1,.k])
    }
  }
  out <- sapply(0:min(n, k), function(y) choose(k, y)*choose(n, y)*factorial(y)*F[n-y+1,k-y+1]) / k^n
  names(out) <- 0:min(n, k)
  out
}

This returns your hand-calculated results for the $n=2, k=3$ case:
uniquePMF(2, 3)
#         0         1         2 
# 0.3333333 0.0000000 0.6666667

It can also comfortably handle larger instances (here $n=k=100$):
plot(0:100, uniquePMF(100, 100), xlab="y", ylab="Pr(Y=y)")


A: This is basically a generalized coupon-collector problem. I don't think you're going to find an easy closed form solution to it. In general, the distribution of dice throws is multinomial:
$$\binom{n}{a_1,a_2,\cdots,a_r}(1/r)^n,$$
where $a_i$ represents the number of times $i$ is rolled, and $a_1+\cdots+a_r=n$. Then the answer is:
$$(1/r)^n\sum\binom{n}{a_1,a_2,\cdots,a_r},$$
where the sum is over all combinations of $a_i$ such that exactly $y$ of them are nonzero. I.E. you are looking at all partitions of $n=a_1+\cdots+a_r$ such that exactly $y$ are nonzero. You can use some symmetry to simplify this further by just summing over all combinations of $n=a_1+\cdots+a_y$ with $a_i>0$ for $i=1,2,\cdots,y$ and $a_i=0$ for $i>y$,  and then accounting for their multiplicity via $\binom{n}{a_1}\binom{n-a_1}{a_2}\cdots$. 
