1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.