12
$\begingroup$

I found this in my test book, any hints? Given $${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$$ Then find the value of x and y in n. According to the answer provided on last pages of that book, it's $2n \choose n$. What i dont understand is how to get the answer (there's no explanation written there). All i said is thank you so much for every activity to me and i'm sorry for my bad english (english is not my native language) and my messy post.

$\endgroup$
16
$\begingroup$

Let $E=\{a_1,\ldots a_n,b_1,\ldots,b_n\}$ a set with $2n$ elements. There's $2n\choose n$ subsets of $E$ with $n$ elements: $k$ elements from $\{a_1,\ldots,a_n\}$ and $n-k$ elements from $\{b_1,\ldots,b_n\}$ for some $k=0,\ldots,n$ hence we have $${2n\choose n}=\sum_{k=0}^n{n\choose k}{n\choose n-k}=\sum_{k=0}^n{n\choose k}^2$$

$\endgroup$
  • $\begingroup$ This is completely clear, thank you so much :D $\endgroup$ – Jake Timberwood May 28 '13 at 13:00
  • $\begingroup$ You're welcome:) $\endgroup$ – user63181 May 28 '13 at 13:00
  • $\begingroup$ Excellent answer, Sami! $\endgroup$ – Namaste Jul 4 '14 at 12:09
5
$\begingroup$

Hint: compare the coefficient of $x^n$ on both sides of $(1+x)^{2n} = ((1+x)^n))^2$.

$\endgroup$
  • $\begingroup$ It takes me so long to interpret this, but thank you $\endgroup$ – Jake Timberwood May 28 '13 at 13:04
  • $\begingroup$ I prefer this one as it more easily lends itself to generalisation (i.e. $\binom{n}{0}^k+...+\binom{n}{n}^k$ for general $k$) $\endgroup$ – Meow May 31 '13 at 10:32
1
$\begingroup$

Hint: Write it as $${n \choose 0} {n \choose n} + {n \choose 1} {n \choose n-1} + \dots + {n \choose n} {n \choose 0},$$ and use the obvious combinatorial bijection.

$\endgroup$
  • $\begingroup$ Sorry, i still don't get it, i could only see that if we sum up every term with itself, it will result $2n \choose n$, is it related with the hint you explained? $\endgroup$ – Jake Timberwood May 28 '13 at 12:58
  • $\begingroup$ @Jake Timberwood: Sami Ben Romdhane wrote a full solution. The idea is that you divide the set of $2n$ balls in the first $n$ balls and last $n$ balls. Then you want to choose $n$ balls from them, giving ${2n \choose n}$ ways. But you can also choose first how many balls to choose from the first $n$ balls, say $j$, and then you'll get ${n \choose j}{n \choose n-j}$ possible arrangements. Summing over $j$ and noticing that ${n \choose n-j} = {n \choose j}$, you get the result. $\endgroup$ – J. J. May 28 '13 at 13:01
  • $\begingroup$ yes, his explanation could clearly be understood, however thank you for the explanation :) $\endgroup$ – Jake Timberwood May 28 '13 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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