counting the number of n-tuples with maximum number of distinct elements I have a set A of m elements. I want to count the number of n-tuples (permutations of size n) when the elements of the n-tuples are selected from A and there are at most r distinct elements in an n-tuple. 
I think we can solve this with a recursive eq. like the following:
$$X(n,m,r)=X(n,m-1,r)+\sum_{i=1}^n \binom{n}{i}  X(n-i,m-1,r-1)$$
However, I am looking for more straight forward and simpler answers 
 A: This would appear from first principles to be
$$\bbox[5px,border:2px solid #00A000]{
\sum_{q=1}^r {m\choose q} q! {n\brace q}.}$$
Here $q$  gives the number of  different elements that have  been seen
where $q\le r \le m.$ We choose  these from the $m$ available ones and
partition  the  constituents of  the  tuple  into $q$  non-empty  sets
(Stirling number),  one for each type  of element, where the  order of
the sets  matters (factor $q!$  as we map  each element to  the places
where it appears in the tuple).
We can also derive this from the combinatorial class
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SEQ}_{=q}(\textsc{SET}_{\ge 1}(\mathcal{Z}))$$
which gives the EGF
$$G_q(z) = (\exp(z)-1)^q.$$
We then have
$$\sum_{q=1}^r {m\choose q} n! [z^n] G_q(z)
= n! [z^n] \sum_{q=1}^r {m\choose q} (\exp(z)-1)^q
\\ = n! [z^n] \sum_{q=1}^r {m\choose q} q!
\frac{(\exp(z)-1)^q}{q!}
= \sum_{q=1}^r {m\choose q} q! {n\brace q}.$$
Note that when $r=m$ we get as a sanity check
$$n! [z^n] \sum_{q=1}^m {m\choose q} (\exp(z)-1)^q.$$
The term for $q=0$ does not contribute when $n\ge 1$ and we find
$$n! [z^n] \sum_{q=0}^m {m\choose q} (\exp(z)-1)^q
= n! [z^n] \exp(mz) = m^n,$$
as expected.
