A little help here. Exercise 21, Ch. 2 from Feller's book reads
In a town a $n+1$ inhabitants, a person tells a rumor to a second person, who in turn repeats it to a third person, etc. At each step, the recipient of the rumor is chosen at random from the $n$ people available. Find the probability that the rumor will be told $r$ times without: a) returning to the originator, b) being repeated to any person. Do the same problem when at each step the rumor is told by one person to a gathering of $N$ randomly chosen people. (The first question is the special case N=1).
I already did a) and b) for the first description of the problem and a) for the case when the rumor is spreading through a gathering of $N$ people, however, my solution for b) in this second case is not correct.
I reasoned in the following way: In a first instance, $n$ people to receive the rumor, however, it's needed to spread such rumor through a group of $N$ people, therefore, there are $\displaystyle n \choose N$ ways to choose those gatherings. Once one of these people is chosen, he/she can choose from another gathering of $N$ people, taking care of not choosing someone who already know the rumor, which is, there are $\displaystyle n-1 \choose N$, and so on, until we reach the $r$ step in this process. Therefore, the probability I get is:
$$\frac{\displaystyle {n \choose N} {n-1 \choose N} {n-2 \choose N} … {n-r+1 \choose N}}{\displaystyle {n \choose N}^{r}}$$
According to the book, the solution must be $\displaystyle \frac{(n)_{Nr}}{(n_{N})^{r}}$ (which is not equivalent to the first expression).
I will appreciate any help.
Best Answer
Liberalkid is right. Using his suggestion, you get $$\frac{\binom{n}{N}\binom{n-N}{N}\cdots\binom{n-(r-1)N}{N}}{\binom{n}{N}^r} = \frac{n_N (n-N)_N \cdots (n-(r-1)N)_N}{(n_N)^r} = \frac{n_{Nr}}{(n_N)^r}.$$ In the first step you cancel $N!$ from each side $r$ times.