Simplification of a Combinatoric problem (n k)^2 [duplicate]
$begingroup$
This question already has an answer here:
Combinatorial proof of summation of $sumlimits_{k = 0}^n {n choose k}^2= {2n choose n}$
6 answers
How do I simplify the sum $$sum_{k=0}^{n} {n choose k}
^2?$$
I have tried, but the best I did was
$$sum_{k=0}^{n} {frac{n!n!}{k!k!(n-k)!(n-k)!}}.$$
combinatorics summation
asked Jan 5 at 7:36
Michael WangMichael Wang
359
$endgroup$
marked as duplicate by Nosrati, mrtaurho, Community♦ Jan 5 at 19:47
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Combinatorial proof of summation of $sumlimits_{k = 0}^n {n choose k}^2= {2n choose n}$
6 answers
How do I simplify the sum $$sum_{k=0}^{n} {n choose k}
^2?$$
I have tried, but the best I did was
$$sum_{k=0}^{n} {frac{n!n!}{k!k!(n-k)!(n-k)!}}.$$
combinatorics summation
asked Jan 5 at 7:36
Michael WangMichael Wang
359
$endgroup$
marked as duplicate by Nosrati, mrtaurho, Community♦ Jan 5 at 19:47
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Have you tried evaluating this numerically? For $n=1$, $2$, $3$, $4$ say?
$endgroup$
– Lord Shark the Unknown
Jan 5 at 7:41
$begingroup$
see: oeis.org/…
$endgroup$
– Aleksas Domarkas
Jan 5 at 8:04
add a comment |
$begingroup$
This question already has an answer here:
Combinatorial proof of summation of $sumlimits_{k = 0}^n {n choose k}^2= {2n choose n}$
6 answers
How do I simplify the sum $$sum_{k=0}^{n} {n choose k}
^2?$$
I have tried, but the best I did was
$$sum_{k=0}^{n} {frac{n!n!}{k!k!(n-k)!(n-k)!}}.$$
combinatorics summation
asked Jan 5 at 7:36
Michael WangMichael Wang
359
$endgroup$
This question already has an answer here:
Combinatorial proof of summation of $sumlimits_{k = 0}^n {n choose k}^2= {2n choose n}$
6 answers
How do I simplify the sum $$sum_{k=0}^{n} {n choose k}
^2?$$
I have tried, but the best I did was
$$sum_{k=0}^{n} {frac{n!n!}{k!k!(n-k)!(n-k)!}}.$$
This question already has an answer here:
Combinatorial proof of summation of $sumlimits_{k = 0}^n {n choose k}^2= {2n choose n}$
6 answers
combinatorics summation
combinatorics summation
asked Jan 5 at 7:36
Michael WangMichael Wang
359
asked Jan 5 at 7:36
Michael WangMichael Wang
359
asked Jan 5 at 7:36
Michael WangMichael Wang
359
asked Jan 5 at 7:36
Michael WangMichael Wang
359
asked Jan 5 at 7:36
Michael WangMichael Wang
359
359
marked as duplicate by Nosrati, mrtaurho, Community♦ Jan 5 at 19:47
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Nosrati, mrtaurho, Community♦ Jan 5 at 19:47
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Have you tried evaluating this numerically? For $n=1$, $2$, $3$, $4$ say?
$endgroup$
– Lord Shark the Unknown
Jan 5 at 7:41
$begingroup$
see: oeis.org/…
$endgroup$
– Aleksas Domarkas
Jan 5 at 8:04
add a comment |
$begingroup$
Have you tried evaluating this numerically? For $n=1$, $2$, $3$, $4$ say?
$endgroup$
– Lord Shark the Unknown
Jan 5 at 7:41
$begingroup$
see: oeis.org/…
$endgroup$
– Aleksas Domarkas
Jan 5 at 8:04
$begingroup$
Have you tried evaluating this numerically? For $n=1$, $2$, $3$, $4$ say?
$endgroup$
– Lord Shark the Unknown
Jan 5 at 7:41
$begingroup$
Have you tried evaluating this numerically? For $n=1$, $2$, $3$, $4$ say?
$endgroup$
– Lord Shark the Unknown
Jan 5 at 7:41
$begingroup$
see: oeis.org/…
$endgroup$
– Aleksas Domarkas
Jan 5 at 8:04
$begingroup$
see: oeis.org/…
$endgroup$
– Aleksas Domarkas
Jan 5 at 8:04
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here is a trick that reduces it. First we can say that
$$sum_{k=0}^n{nchoose k}^2 = sum_{k=0}^n{nchoose k}{nchoose n-k}$$
Now let's think about what this means. ${nchoose k}{nchoose n-k}$ is the number of ways to pick $k$ things from a group of $n$, and then pick $n-k$ things from another group of $n$. So if we have a group of $2n$ things that we split it two, it is the number of ways to pick $k$ things from the first group and $n-k$ things from the second group. The crucial observation is that summing this over all k gives the total number of ways to pick $n$ things from the whole group! So the answer is
$$sum_{k=0}^n{nchoose k}^2 = {2nchoose n}$$
answered Jan 5 at 8:09
Erik ParkinsonErik Parkinson
9159
New contributor
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Thank you so much! Why did I not think of that before?
$endgroup$
– Michael Wang
Jan 5 at 8:10
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is a trick that reduces it. First we can say that
$$sum_{k=0}^n{nchoose k}^2 = sum_{k=0}^n{nchoose k}{nchoose n-k}$$
Now let's think about what this means. ${nchoose k}{nchoose n-k}$ is the number of ways to pick $k$ things from a group of $n$, and then pick $n-k$ things from another group of $n$. So if we have a group of $2n$ things that we split it two, it is the number of ways to pick $k$ things from the first group and $n-k$ things from the second group. The crucial observation is that summing this over all k gives the total number of ways to pick $n$ things from the whole group! So the answer is
$$sum_{k=0}^n{nchoose k}^2 = {2nchoose n}$$
answered Jan 5 at 8:09
Erik ParkinsonErik Parkinson
9159
New contributor
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Thank you so much! Why did I not think of that before?
$endgroup$
– Michael Wang
Jan 5 at 8:10
add a comment |
$begingroup$
Here is a trick that reduces it. First we can say that
$$sum_{k=0}^n{nchoose k}^2 = sum_{k=0}^n{nchoose k}{nchoose n-k}$$
Now let's think about what this means. ${nchoose k}{nchoose n-k}$ is the number of ways to pick $k$ things from a group of $n$, and then pick $n-k$ things from another group of $n$. So if we have a group of $2n$ things that we split it two, it is the number of ways to pick $k$ things from the first group and $n-k$ things from the second group. The crucial observation is that summing this over all k gives the total number of ways to pick $n$ things from the whole group! So the answer is
$$sum_{k=0}^n{nchoose k}^2 = {2nchoose n}$$
answered Jan 5 at 8:09
Erik ParkinsonErik Parkinson
9159
New contributor
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Thank you so much! Why did I not think of that before?
$endgroup$
– Michael Wang
Jan 5 at 8:10
add a comment |
$begingroup$
Here is a trick that reduces it. First we can say that
$$sum_{k=0}^n{nchoose k}^2 = sum_{k=0}^n{nchoose k}{nchoose n-k}$$
Now let's think about what this means. ${nchoose k}{nchoose n-k}$ is the number of ways to pick $k$ things from a group of $n$, and then pick $n-k$ things from another group of $n$. So if we have a group of $2n$ things that we split it two, it is the number of ways to pick $k$ things from the first group and $n-k$ things from the second group. The crucial observation is that summing this over all k gives the total number of ways to pick $n$ things from the whole group! So the answer is
$$sum_{k=0}^n{nchoose k}^2 = {2nchoose n}$$
answered Jan 5 at 8:09
Erik ParkinsonErik Parkinson
9159
New contributor
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Here is a trick that reduces it. First we can say that
$$sum_{k=0}^n{nchoose k}^2 = sum_{k=0}^n{nchoose k}{nchoose n-k}$$
Now let's think about what this means. ${nchoose k}{nchoose n-k}$ is the number of ways to pick $k$ things from a group of $n$, and then pick $n-k$ things from another group of $n$. So if we have a group of $2n$ things that we split it two, it is the number of ways to pick $k$ things from the first group and $n-k$ things from the second group. The crucial observation is that summing this over all k gives the total number of ways to pick $n$ things from the whole group! So the answer is
$$sum_{k=0}^n{nchoose k}^2 = {2nchoose n}$$
answered Jan 5 at 8:09
Erik ParkinsonErik Parkinson
9159
New contributor
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Jan 5 at 8:09
Erik ParkinsonErik Parkinson
9159
New contributor
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Jan 5 at 8:09
Erik ParkinsonErik Parkinson
9159
answered Jan 5 at 8:09
Erik ParkinsonErik Parkinson
9159
9159
New contributor
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
Thank you so much! Why did I not think of that before?
$endgroup$
– Michael Wang
Jan 5 at 8:10
add a comment |
$begingroup$
Thank you so much! Why did I not think of that before?
$endgroup$
– Michael Wang
Jan 5 at 8:10
$begingroup$
Thank you so much! Why did I not think of that before?
$endgroup$
– Michael Wang
Jan 5 at 8:10
$begingroup$
Thank you so much! Why did I not think of that before?
$endgroup$
– Michael Wang
Jan 5 at 8:10
add a comment |
$begingroup$
Have you tried evaluating this numerically? For $n=1$, $2$, $3$, $4$ say?
$endgroup$
– Lord Shark the Unknown
Jan 5 at 7:41
$begingroup$
see: oeis.org/…
$endgroup$
– Aleksas Domarkas
Jan 5 at 8:04