[anArbitraryOne]

It would be more straightforward to remove the permutations and just display the combinations and the symmetry between heads and tails. And solve it analytically Eg: if p is the probability that the NPC is correct

  P(A|AAAA) = p^4 
  P(A|BBBB) = (1-p)^4

Anyway, the apparent strangeness of the tie case comes from the fact that the binomial PMF is symmetric with respect to n (the number of participants) and n-k.

  PMF = (n choose k) * p^k * (1-p)^(n-k)

So when k = n/2, the symmetry means that the likelihood is identical under p and 1-p, so we're not gaining any information. This is a really good illustration of that; interesting post! (edit: apparently i suck at formatting)