Number of possibilities for a string to contain more instances of one letter then another letter

Question

I need to calculate how many possibilities there are for a string with a length of 500 which contains on the letters $a$ and $b$, in which the letter $a$ appears more times than the letter $b$.

From what I understand, the letter $a$ must have at least 251 instances a given string for it to be a valid possibility. This means that one must first place 251 $a$'s in various indexes of the string. The number of possibilites for doing so is $${500}\choose{251}$$

Now it is irrelevant which letter is placed in the remaining string indexes. There are 249 letters to be assigned in the string and each index may be assigned with on of two letters, meaning that my final calculation is: $${{500}\choose{251}}2^{249}$$

However the textbook answer is: $$\frac{{2^{500} - {{500}\choose{250}}}}{2}$$

No explanation is provided about how this number was calculated and I'm in need for some expert assistance on how one may solve this problem.

Answer 1

Let's consider a simpler problem.

How many strings of length $10$ composed of $a$s and $b$s have more $a$s than $b$s?

Since each position can be filled in two ways, there are a total of $2^{10} = 1024$ possible strings.

Choosing the locations of the $a$s completely determines the string. The number of strings with a majority of $a$s is therefore $$\binom{10}{6} + \binom{10}{7} + \binom{10}{8} + \binom{10}{9} + \binom{10}{10} = 210 + 120 + 45 + 10 + 1 = 386$$ By symmetry, this is also the number of strings with a majority of $b$s. In each of the remaining $$\binom{10}{5} = 252$$ strings, there are an equal number of $a$s and $b$s. Notice that $386 + 252 + 286 = 1024 = 2^{10}$.

Consequently, we can find the number of strings with more $a$s and $b$s by taking half the number of strings that do not have an equal number of $a$s and $b$s.
$$\frac{1}{2}\left[2^{10} - \binom{10}{5}\right] = \frac{1}{2}(1024 - 252) = \frac{1}{2} \cdot 772 = 386$$

For a string of length $500$, we replace $10$ by $500$ and $5$ by $250$ to obtain $$\frac{1}{2}\left[2^{500} - \binom{500}{250}\right]$$ which agrees with the answer in the text.

Where did you go wrong?

Let's again consider the simpler problem above. Using your method for the problem with strings of length $10$, we would obtain $$\binom{10}{6}2^4 = 210 \cdot 16 = 3360 > 1024 = 2^{10}$$ which is an indication that you over counted.

If there are exactly six $a$s in the string, there are $\binom{10}{6}$ ways to place them. The remaining positions must be filled with $b$s. There is only one way to do this, so there are $\binom{10}{6}$ such strings. By similar reasoning, there are $\binom{10}{7}$ strings with exactly $7$ $a$s. However, you count each such case seven times. Consider the string $$aaaaaabbb$$ You count it as

$\color{blue}{aaaaaa}abbb$

$\color{blue}{aaaaa}a\color{blue}{a}bbb$

$\color{blue}{aaaa}a\color{blue}{aa}bbb$

$\color{blue}{aaa}a\color{blue}{aaa}bbb$

$\color{blue}{aa}a\color{blue}{aaaa}bbb$

$\color{blue}{a}a\color{blue}{aaaaa}bbb$

$a\color{blue}{aaaaaa}bbb$

once for each of the $\binom{7}{6}$ ways you could designate six of the seven $a$s as being the $a$s in the six positions you reserved for $a$s. Similarly, you count each string with eight $a$s $\binom{8}{6}$ times, each string with nine $a$s $\binom{9}{6}$ times, and the string with ten $a$s $\binom{10}{6}$ times. Notice that $$\binom{6}{6}\binom{10}{6} + \binom{7}{6}\binom{10}{7} + \binom{8}{6}\binom{10}{8} + \binom{9}{6}\binom{10}{9} + \binom{10}{6}\binom{10}{10} = 3360$$

Answer 2

The answer you post counts the number of strings with the same number of each letter, subtracts from the total number of strings to find the number of strings in which the character counts differ, and halves, since by symmetry half have more $a$ than $b$.