I'm currently reading Knuth's proof about O(1) number of probes in linear probing. I have a small question on the page 536 (Volume 3, 2nd Edition). Knuth says
Let $f(M, N)$ be the number of hash sequences such that position 0 of the table will be empty after the keys have been inserted using linear probing. The circular symmetry of linear probing implies that position 0 is empty just as often as any other position, so it is empty with probability $1 - \frac{N}{M}$; in other words $f(M, N) = (1 - \frac{N}{M})M^N$.
I explain to myself as follows. Each hash sequence has $M-N$ empty positions, then the total number of empty positions is $(M-N)M^N$ and -- due to the symmetry -- each position is empty for $(M-N)M^N / M = (1 - \frac{N}{M})M^N$ hash sequences. Thus, the probability of zero position to be empty is $(1 - \frac{N}{M})$.
The problem is that Knuth first states that the probability that 0 position is empty is $(1 - \frac{N}{M})$ and after says that $f(M, N) = (1 - \frac{N}{M})M^N$. I'm able to prove this only in other way around. Could please anybody explain how to prove the probability without showing that the total amount of empty positions is $(M-N)M^N$.
Thank you.