Odds of 500,000 heads and 500,000 tails

If you flip a perfect coin* 1 million times, what are the odds that you would get exactly 500,000 heads and 500,000 tails?

A) 0%
B) 0.08%
C) 1%
D) 10%
E) 50%
F) 100%

Go ahead and try and explain your answer.

*perfect coin: A coin that has exactly a 50% chance of landing on either heads or tails.

Think of the simplest case. 2 coin flips. There are 4 possible outcomes, both heads, both tails, or 1 of each.

Wait, I just said 4 possible outcomes, then described 3?  Why?

Well, think of it like this:

HH, TT, HT, TH

Getting heads then tails is a different outcome than tails then heads, but both result in 1 of each. So, judging from that, you say, well 2 of 4, that's 50%, I knew the answer was E! Hah, not so fast...

Now, let's look at the next simplest case.  4 coin flips. Here are the possible outcomes:

HHHH, HHHT, HHTH, [HHTT], HTHH, [HTHT], [HTTH], HTTT, THHH, [THHT], [THTH], THTT, [TTHH], TTHT, TTTH, TTTT

So, there's 16 possibilities, and only 6 have equal numbers of heads and tails, I surrounded them in square brackets.  Uh Oh, that's 37.5% and it's probably going to get worse as we increase the flips towards 1 million. So maybe you're leaning towards answer C or D now, right?

From here I could go into the topics of binomial coefficients, pascal's triangle and other worthwhile, interesting topics, but I'll skip the heavy math and just show you dude's triangle.

     1
    1 1
  1 (2) 1   summed = (4)
 1 3   3 1
1 4 (6) 4 1 summed = (16)

Hopefully you recognize Pascal's triangle, but if you don't there's always Wikipedia.

We only care about every other case, as you need an even number of flips to obtain a perfectly even split of heads and tails.  You might recognize the numbers I put in parentheses. Those are the results we saw for 2 and 4 flips. So, now we just have to draw the next 999,996 lines of the triangle.

Don't worry, I did this on a separate sheet of paper, and the result was roughly 0.08%.

If you don't believe me, you can ask WolframAlpha