# Looking for a combinatorical explanation

Let $X_n$ be the set of all word of the length $2 n$ over the alphabet $\{A,B\}$ which contain as many A's as B's.

The amount of elements of $X_n$ is $\displaystyle \binom{2n}{n}$, but why?

I thought about it for a long time but really am a bit slow today. Does anybody have a (simple) combinatorical explanation why this applies?

The number of words of length $n$ with $k$ $A$s is ${n \choose k}$. Do you know how to prove this? What interpretations of the binomial coefficients are you familiar with? –  Qiaochu Yuan Jun 25 '11 at 20:49
Cool. So, consider a word of length $n$ with $k$ $A$s. How can you convert this into a specification of a $k$-element subset of a set of size $n$? –  Qiaochu Yuan Jun 25 '11 at 21:10
@qiaochu-yuan a word can be representated by its indices (1,2,3,$\cdots$,n), and a k -element subset is just that set of indices that may turn into an A. Thanks! –  muffel Jun 25 '11 at 21:14
There are $2n$ positions to be filled in a word of length $2n$. Once you know which $n$ positions are filled with $A$'s, the other $n$ positions must contain $B$'s, so the word is completely determined. There are ${2n} \choose {n}$ ways to choose which $n$ positions get the $A$'s, so there are ${2n} \choose {n}$ such words.