Context:
I watched a kid at one of those gumball/prize machines often found at stores throwing money into them, trying to get a certain prize.
This made me think "what would the probability be if they emptied the machine, that somewhere along the task they'd have a run where each of the possible distinct prizes showed up?".
Work done:
It was clear to me that if the "machine" was spitting out prizes, with equal probability for all prizes, from an "infinite pool" (or a "generator") of prizes, the probability of such a sequence of all distinct prizes showing up in a consecutive sequence can be handled with a simple Markov chain.
Where I'm stuck:
If instead of the above prize "generator" it is a machine that has a fixed (and known) inventory that you empty, I'm a bit lost. I thought perhaps taking one of each distinct prize from inventory, treating them as a separate "prize", and calculating the number of possible permutations of the inventory including that grouping and dividing by total number of permutations possible for the bare inventory would to the trick, but that appears to be a dead end.
Simple example:
Say the machine starts with an inventory of $\{1,1,1,2,2,2,3\}$. Take a random permutation of the inventory. What is the probability that permutation contains the substring $1,2,3$ without respect to order (that is, $3,2,1$ or $2,1,3$, etc., any of the six possible orderings of $1,2,3$ is a valid substring of the distinct prizes available in inventory at the start of the emptying task)?