Probability of $m$ out of $n$ rolls of a die being among the numbers $1,2,\ldots,m-1$, for some $m$. Suppose I have a $k$ sided die with the numbers $1,2,\ldots,k$ on each side, and that I roll it $n$ times ($n<k$).
What is the probability that there exists an $m\leq n$, so that $m$ of the $n$ rolls lie in the set $\{1,2,\ldots,m-1\}$?
If a closed form in terms of $k,n$ cannot be easily found, a recursion would be equally useful, so it can be more easily calculated.
I have tried calculating this for specific values of $n$ and $k$, but it is difficult, because the two events corresponding to distinct values of $m$ are not mutually exclusive, so you can't just calculate the probability of the event occurring for each value of $m\leq n$, and add them up. This means that copious use of the Principle of Inclusion-Exclusion is required, and it gets messy very quickly.
 A: I fiddled with this after the false-start of missing the $-1$ on $m-1$ for the set.
It appears that the desired result is $S/k^n$, where $S$ is the $(n-1)_{\text{th}}$ element of the $k_{\text{th}}$ row of $A099614$.
So, e.g,. for a six sided die rolled 4 times, $89/432$ results.
The following Mathematica snippet calculates this directly.
p[faces_, rolls_] := Numerator[(faces/(1 + faces))^rolls + rolls/(1 + faces) - 1]/faces^rolls

One can also use WolframAlpha (snip the code to the right of ":=" and replace symbols with values).
I have not found a more direct method to generate the numerator, I'm sure one probably exists.
Here's a quick plot of the calculated results against a simulation check for a 20-sided die rolled 2 to 19 times.

A: I think this seems like a hard problem because we're tempted to see $k$ as fixed and try to use induction or recursion over $n$. The proof of the formula that Hammy found is actually quite straighforward if we focus on $k$.
How many admissible sequences of $n$ rolls are there with $k$ sides, $k\ge n$? Since rolling $k$ doesn't contribute to admissibility, choose any number $j$ of rolls for an admissible sequence using only the first $k-1$ sides and fill the remaining rolls with $k$'s:
$$
a(k,n)=\sum_{j=0}^n\binom nja(k-1,j)\;.
$$
This allows us to prove Hammy's formula,
$$
a(k,n)=k^n-(k+1)^n+n(k+1)^{n-1}\;,
$$
by induction over $k$ and $n$. (Note that the indices in the OEIS sequence Hammy linked to are shifted and swapped with respect to ours.)
The base cases are $a(k,0)=0$ and $a(n-1,n)=(n-1)^n$, since for $n-1$ sides all sequences are admissible. These are readily checked. The induction step uses the binomial expansion of $(x+1)^n$:
\begin{eqnarray}
a(k,n)
&=&\sum_{j=0}^n\binom nja(k-1,j)\\
&=&\sum_{j=0}^n\binom nj\left((k-1)^j-k^j+jk^{j-1}\right)\\
&=&\sum_{j=0}^n\binom nj\left((k-1)^j-k^j+\frac{\mathrm d}{\mathrm dk}k^j\right)\\
&=&k^n-(k+1)^n+\frac{\mathrm d}{\mathrm dk}(k+1)^n\\
&=&k^n-(k+1)^n+n(k+1)^{n-1}\;.
\end{eqnarray}
