For those who haven't seen it, here is how you can show with a counting and divisibility argument that a common algorithm many come up with to shuffle is not a fair shuffle.
Here's the algorithm, in pseudo code (yes, with 1-based arrays!):
let a = [1, 2, 3, ...., N] # the items to shuffle
for i = 1 to N
j = random_in(1, N)
swap(a[i], a[j])
Imagine that random_in() makes a log of all its return values. In this program every time it is called it returns an integer >= 1 and That means that there are N^N distinct possible traces. Each of these traces is equally likely. We can associate with each of the traces a shuffle, namely the shuffle that results from the run of the program that produced that trace.
This gives us a list of N^N shuffles. This list will contain duplicates, because there are only N! distinct shuffles, and N! The shuffle is fair if and only if each possible shuffle occurs the same number of times in the list of N^N shuffles. For it to be even possible for that to happen, we must have N! divides N^N.
But if N > 2, that cannot happen. To show this note that if N! divides N^N, then every divisor of N! must divide N^N. Pick a prime P such that (1) p Can we really always pick such a prime? Yes. If N is divisible by every prime p Note that you cannot save this class of algorithm by doing more passes. Those just change the size of the trace from N^N to N^(kN) for some integer N. Nor can you save it by changing it to pick both indices at random for the swap instead of picking only one at random. That just changes N^N to (N^2)^N = N^(2N). As long as the random number generator is always asked for a number in {1, 2, ..., N} and it is called the same number of times every time the program is run, the trace size is going to be a power of N, and cannot be divide evenly by N!
Now we can see why Fisher-Yates might work. It asks for a random number up to N the first iteration, up to N-1 the second iteration, and so on. That means its trace is N! long. There is no problem dividing N! by N!. Since N!/N! = 1, if we can show that each shuffle is included, that will also show that each is included the same number of times, and hence that Fisher-Yates is fair.
All we have to do now to see that Fisher-Yates is fair is show that each shuffle can be produced by it. Given a desired shuffle, it is easy to construct the trace that results in it, and we are done.