1
$\begingroup$

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?

Thanks in advance!

  • 1
    @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!2011-06-25

1 Answers 1

6

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.

  • 0
    @brian-m-scott just great, thanks!2011-06-25