I am having big problems with this exercise:
There are $n$ customers and $k$ types of products and number $i$, where $n \ge k \ge i$. I have to find the probability of the situation where customers buy exactly $i$ types of products (one customer can buy just one product and every customer has random choice).
I already tried to solve the weaker problem where $i = k$, and I wasn't able to solve even it: my potential solution was: $P[] = \binom n k \frac {k^{n-k}} {k^n}$, but there is the problem that something is counted twice, so I expect some use of Inclusion/Exclusion theorem, but I just don't know how.
Is there some formula for it ?
Thanks for answers.
We have an alphabet $\Sigma$ of of $k$ letters and we consider the set of strings of length $n$, i.e. $\Sigma^n$.
Now we choose a "sub-alphabet", call it $P$, such that $P \subseteq \Sigma$ and $|P| = i$. There are ${k \choose i}$ ways to choose this sub-alphabet. Now we have reduced it again to the case where $k=i$.
The problem is reduced to finding the number of strings of length $n$ in an alphabet of size $i$ with each letter appearing at least once. Consider the index set of size $n$: $\{1, 2, \dots, n\}$. Now there are $S(n, i)$ ways to partition this set into $i$ parts, where $S(n, i)$ is the Stirling number of the second kind. Now we replace all elements of each part with a unique letter from the alphabet, we can do this in $i!$ ways. We "put the set back together" according to the original indices, and this corresponds to such a string.
Thus, this is $i! {k \choose i} S(n, i)$ in total.