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
    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?2011-06-25
  • 0
    @qiaochu-yuan As I know the binomial coefficient is the amount of possibilities of building k-element subsets of an original set containing n elements. Your definition can be easily proved when considering the subsets as the indices where an *A* is inserted.2011-06-25
  • 1
    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$?2011-06-25
  • 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