I'm working on a bigger problem, where a smaller subproblem is essentially:
Consider $N$ chips and $k$ cookies. What is the recursive formula for the number of ways we can place $N$ chips on $k$ cookies.
The solution shows the following formula: $$ C_{n,k} = k\times C_{n-1,k-1} + k\times C_{n-1,k} $$
with the following explanation:
In order to get a success when placing the $N$-th chip, it must be either that the previous $N − 1$ chips already distributed a chip to each cookie (success already!) and the $N$-th chip can go into any of the $k$ cookies, or the previous $N −1$ chips distributed a chip to $k − 1$ of the cookies and the $N$-th chip will go into the empty cookie; there are $k$ ways that the latter event could take place.
The second term makes sense to me, but I don't understand the first term $k\times C_{n-1,k-1}$. I don't understand why there are $k$ ways for this event to take place. Consider $n-1$ chips distributed to $k-1$ chips. There are $C_{n-1,k-1}$ of these events. Consider a single such event. For simplicity, let's say $n=k=3$. And we're looking at a single event of $C_{2,2}$. Say this single event has the first $2$ cookies each with a chip and the 3rd cookie is unfilled. Then to get from this state to the corresponding event in $C_{n,k}$, we simply add the remaining chip to the 3rd cookie. But there is only 1 such way to do so. Why is the solution claiming there are $k$ ways to do this?
The original question is:
You are making chocolate chip cookies. You add N chips randomly to the cookie dough, and you randomly split the dough into 100 equal cookies. How many chips should go into the dough to give a probability of at least 90% that every cookie has at least one chip?
The extended solution is:
The problem is somewhat ambiguous, since the term "distribution" is not defined. From the way that the formula is worked out, it appears that the chips, as well as the cookies are considered to be distinguishable.
If all that matters is how many chips are placed on each cookie, then you're right, there is a lot of double-counting going on. If the chips aren't distinguishable, then it doesn't matter whether the first chip or the last chip is placed on a particular cookie and the argument given doesn't make any sense.
If the chips are different, then of course it matters which cookie gets the last chip.
Consider the case $n=k$. If the chips are indistinguishable, there is only one way to do the distribution: put one chip on each cookie. But then the formula is wrong on its face. The left-hand side is $1$ and the right-hand side is divisible by $k$.
Once we consider distinct chips, the formula is transparent, I think.