# 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

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.