Choosing $k$ objects from $n$ groups, at least one for each group ($k>n$)

Question

I'm struggling to come up with the method to find the number of ways to take $k$ objects from $n$ groups which at least one object from each group is taken and order matters.

More specifically, I'm trying to order $8$ digits from the digit pool of $5-10$ ($6$ digits) and each digit must appear at least once and the order matters, e.g. $5,6,7,8,9,10,5,5$ is fine and different from $5,5,6,7,5,8,9,10$ which is also acceptable.

I'd like to know the method of finding this, something like a generating function or other combinatorics calculation and why it actually true.

Answer 1

We need to consider the following different sets of digits

• $ \{5,6,7,8,9,10,\color{red}{5,5}\},\{5,6,7,8,9,10,\color{red}{5,6}\},...,\{5,6,7,8,9,10,\color{red}{10,10}\}$

which are $21$ ($6$ with one triple of repeated digits and $15$ with $2$ pairs of repeated digits) and we can permutate each one taking into account the repeated digits, therefore the number of different groups is

$$\frac{15\cdot 8!}{2!2!}+\frac{6\cdot 8!}{3!}=191\,520$$

Answer 2

You could try an induction on $n$. For $n=1$ it's easy. If you know the number (call it $\phi(r)$) for all $r<n$. Then, if I'm not mistaken,

$$\phi(n) = \psi(n) - \sum_{r=1}^{n-1} \binom{n}{r}\phi(r)$$

with $\psi(n)$ the number of ways to choose $k$ from $n$ groups without the imposed restriction.

Answer 3

Since you are interested in generating functions, here is an exponential generating function approach. Let $a_r$ be the number of strings of length $r$ with characters taken from a six-character alphabet, with each character used at least once. We define the exponential generating function of $a_r$ by $$f(x) = \sum_{r=0}^{\infty} \frac{a_r}{r!} x^r$$

The exponential generating function for the number of occurrences of any single character is $$x + \frac{1}{2!} + \frac{1}{3!} + \dots = e^x-1$$ since the character must appear at least once, so $$f(x) = (e^x-1)^6$$ The generating function is interesting in its own right, but if you want a formula for $a_r$ you might start by expanding $(e^x-1)^6$ by the Binomial Theorem, with the result $$f(x) = \sum_{j=0}^6 \binom{6}{j} e^{jx} (-1)^{6-j} $$ So $$\begin{align} a_r &= r!\; [x^r] f(x) \\ &= r! \; \sum_{j=0}^6 \binom{6}{j} (-1)^{6-j} [x^r] e^{jx} \\ &=r! \; \sum_{j=0}^6 \binom{6}{j} (-1)^{6-j} \frac{j^r}{r!} \\ &= \sum_{j=0}^6 \binom{6}{j} (-1)^{6-j} j^r \end{align}$$ where $[x^r]$ is the "coefficient of $x^r$" operator.