2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thats true but main problem for me is to find count of notequal strings builded at alphabet P, where every p from P is there more than once. $\endgroup$
    – Jara M
    May 20, 2016 at 16:18
  • $\begingroup$ Well that looks good, i never met Stirling numbers before, but by definition it seems correct. Thanks with help $\endgroup$
    – Jara M
    May 20, 2016 at 16:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .