Gift baskets with a random number of item types

A bakery manager picks $k$ uniformly at random from $\{1,2,3,4\}$. He then puts together a gift basket of $k$ items, choosing from $k$ distinct dessert types; repeats are allowed and only how many of each type matters. What is the expected number of different baskets he could make?

$49/4$. For a given $k$, baskets correspond to non-negative solutions of $x_1+\dots+x_k=k$, of which there are $\binom{2k-1}{k-1}$ by stars and bars: $1,3,10,35$. Averaging, $(1+3+10+35)/4=\tfrac{49}{4}$.