Conditional bakery problem

Question

This question is from QuantGuide(Bakery Boxes):
A bakery manager uniformly at random selects an integer k between 1 and 4, inclusive. He then chooses from k distinct desert types at his shop to create a gift basket consisting of k items. Find the expected number of ways that the manager can create the gift basket.
My Approach:
Let us have the opportunity to select k from 1 to n-1 and the expected value be denoted by $E_{n-1}$. Where $E_1 = 1$. With probability $\frac{n-1}{n}$ we select a number less than n and in that case the expected value is $E_{n-1}$. With probability $\frac{1}{n}$ we select n. In that case, using n distinct deserts are used to make a basket of n items. Total no of ways is $n^n$. Hence \begin{equation} E_n = \frac{n-1}{n}E_{n-1}+\frac{1}{n}n^n = \frac{1}{n}(1+2^2+3^3+ \cdots + n^n) \end{equation} Using this I'm getting 72

Answer 1

Your calculations involve quite a lot of double counting. For eg. consider the case when $k = 2$. Say, the varieties are $d_1$ and $d_2$. There are only $3$ ways to make the basket, i.e., $d_1d_1$, $d_2d_2$, $d_1d_2$. But you are also counting $d_2d_1$ as a separate basket.

Method 1: Finding the number of baskets case by case:

$1.$ $k = 1$: There is only $1$ basket possible

$2.$ $k = 2$: There are $3$ baskets possible (as explained above)

$3.$ $k = 3$: Three subcases follow here:-

$\quad$ $3.1$ AAA: $3$ baskets ($d_1d_1d_1, d_2d_2d_2, d_3d_3d_3$)

$\quad$ $3.2$ AAB: $6$ baskets (${3 \choose 1} \cdot {2 \choose 1}$)

$\quad$ $3.3$ ABC: $1$ basket ($d_1d_2d_3$)

$4.$ $k = 4$: $5$ subcases follow here:

$\quad$AAAA ($4$), AAAB (${4 \choose 1} \cdot {3 \choose 1} = 12$), AABC (${4 \choose 1} \cdot {3 \choose 2} = 12$), AABB (${4 \choose 2} = 6$), ABCD ($1$).

$\quad$So total baskets in this case = $4 + 12 + 12 + 6 + 1 = 35$

Finally, since each value of $k$ is uniformly picked, we find the expected number of ways to make the basket, $E$, as follows:

$$E = \frac14 \cdot \big( 1 + 3 + 10 + 35 \big) = \frac{49}4 = 12.25$$

Method $2$: Using stars and bars in combinatorics

For a given $k$, we want the number of non-negative integral solutions to the equation $d_1 + d_2 + ... + d_k = k$, which is given by ${k + k - 1 \choose k-1}$

Hence, $$E = \frac14 \cdot \big[ {1 \choose 0} + {3 \choose 1} + {5 \choose 2} + {7 \choose 3} \big]$$