Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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? –  Qiaochu Yuan Jun 25 '11 at 20:49
    
@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. –  muffel Jun 25 '11 at 21:06
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$? –  Qiaochu Yuan Jun 25 '11 at 21:10
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! –  muffel Jun 25 '11 at 21:14

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
@brian-m-scott just great, thanks! –  muffel Jun 25 '11 at 21:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.