Is there a simple combinatoric interpretation of this identity? [duplicate]
Clash Royale CLAN TAG#URR8PPP
$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
I came across an exercise in which we are asked to prove the identity:
$$2nchoose n=sum_k=0^nnchoose k^2$$
The exercise gives the hint:
$$left(1+xright)^2n=left[(1+x)^nright]^2$$
It's not too difficult to use the hint to prove the identity (the expressions in the identity are the coefficients of $x^n$ in the respective expansions of the expressions in the hint, which of course must be the same number), but I was wondering whether there is a neater equivalent-counting interpretation...
It's clear that $2n choose n$ is the number of ways in which we can choose half the elements in a set (where this is possible): how can we interpret $sum_k=0^nnchoose k^2$ equivalently?
combinatorics binomial-coefficients
asked Feb 1 at 7:08
Richard AmblerRichard Ambler
1,298515
$endgroup$
marked as duplicate by Wojowu, N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function()
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();
);
);
);
Feb 1 at 14:15
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
I came across an exercise in which we are asked to prove the identity:
$$2nchoose n=sum_k=0^nnchoose k^2$$
The exercise gives the hint:
$$left(1+xright)^2n=left[(1+x)^nright]^2$$
It's not too difficult to use the hint to prove the identity (the expressions in the identity are the coefficients of $x^n$ in the respective expansions of the expressions in the hint, which of course must be the same number), but I was wondering whether there is a neater equivalent-counting interpretation...
It's clear that $2n choose n$ is the number of ways in which we can choose half the elements in a set (where this is possible): how can we interpret $sum_k=0^nnchoose k^2$ equivalently?
combinatorics binomial-coefficients
asked Feb 1 at 7:08
Richard AmblerRichard Ambler
1,298515
$endgroup$
marked as duplicate by Wojowu, N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function()
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();
);
);
);
Feb 1 at 14:15
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.
4
$begingroup$
Yes, this can be done very succinctly. Hint: Write $binomnk^2$ as $binomnkbinomnn-k$.
$endgroup$
– Erick Wong
Feb 1 at 7:12
4
$begingroup$
This must be a duplicate, I think. But in choosing $n$ from $2n$ think about choosing $k$ to include from the first half and $k$ to omit from the second half.
$endgroup$
– Mark Bennet
Feb 1 at 7:13
$begingroup$
@ErickWong Very neat. Turn your comment into an answer and I'll accept it!
$endgroup$
– Richard Ambler
Feb 1 at 7:32
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
I came across an exercise in which we are asked to prove the identity:
$$2nchoose n=sum_k=0^nnchoose k^2$$
The exercise gives the hint:
$$left(1+xright)^2n=left[(1+x)^nright]^2$$
It's not too difficult to use the hint to prove the identity (the expressions in the identity are the coefficients of $x^n$ in the respective expansions of the expressions in the hint, which of course must be the same number), but I was wondering whether there is a neater equivalent-counting interpretation...
It's clear that $2n choose n$ is the number of ways in which we can choose half the elements in a set (where this is possible): how can we interpret $sum_k=0^nnchoose k^2$ equivalently?
combinatorics binomial-coefficients
asked Feb 1 at 7:08
Richard AmblerRichard Ambler
1,298515
$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
I came across an exercise in which we are asked to prove the identity:
$$2nchoose n=sum_k=0^nnchoose k^2$$
The exercise gives the hint:
$$left(1+xright)^2n=left[(1+x)^nright]^2$$
It's not too difficult to use the hint to prove the identity (the expressions in the identity are the coefficients of $x^n$ in the respective expansions of the expressions in the hint, which of course must be the same number), but I was wondering whether there is a neater equivalent-counting interpretation...
It's clear that $2n choose n$ is the number of ways in which we can choose half the elements in a set (where this is possible): how can we interpret $sum_k=0^nnchoose k^2$ equivalently?
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 binomial-coefficients
combinatorics binomial-coefficients
asked Feb 1 at 7:08
Richard AmblerRichard Ambler
1,298515
asked Feb 1 at 7:08
Richard AmblerRichard Ambler
1,298515
asked Feb 1 at 7:08
Richard AmblerRichard Ambler
1,298515
asked Feb 1 at 7:08
Richard AmblerRichard Ambler
1,298515
asked Feb 1 at 7:08
Richard AmblerRichard Ambler
1,298515
1,298515
marked as duplicate by Wojowu, N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function()
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();
);
);
);
Feb 1 at 14:15
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 Wojowu, N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function()
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();
);
);
);
Feb 1 at 14:15
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.
4
$begingroup$
Yes, this can be done very succinctly. Hint: Write $binomnk^2$ as $binomnkbinomnn-k$.
$endgroup$
– Erick Wong
Feb 1 at 7:12
4
$begingroup$
This must be a duplicate, I think. But in choosing $n$ from $2n$ think about choosing $k$ to include from the first half and $k$ to omit from the second half.
$endgroup$
– Mark Bennet
Feb 1 at 7:13
$begingroup$
@ErickWong Very neat. Turn your comment into an answer and I'll accept it!
$endgroup$
– Richard Ambler
Feb 1 at 7:32
add a comment |
4
$begingroup$
Yes, this can be done very succinctly. Hint: Write $binomnk^2$ as $binomnkbinomnn-k$.
$endgroup$
– Erick Wong
Feb 1 at 7:12
4
$begingroup$
This must be a duplicate, I think. But in choosing $n$ from $2n$ think about choosing $k$ to include from the first half and $k$ to omit from the second half.
$endgroup$
– Mark Bennet
Feb 1 at 7:13
$begingroup$
@ErickWong Very neat. Turn your comment into an answer and I'll accept it!
$endgroup$
– Richard Ambler
Feb 1 at 7:32
4
4
$begingroup$
Yes, this can be done very succinctly. Hint: Write $binomnk^2$ as $binomnkbinomnn-k$.
$endgroup$
– Erick Wong
Feb 1 at 7:12
$begingroup$
Yes, this can be done very succinctly. Hint: Write $binomnk^2$ as $binomnkbinomnn-k$.
$endgroup$
– Erick Wong
Feb 1 at 7:12
4
4
$begingroup$
This must be a duplicate, I think. But in choosing $n$ from $2n$ think about choosing $k$ to include from the first half and $k$ to omit from the second half.
$endgroup$
– Mark Bennet
Feb 1 at 7:13
$begingroup$
This must be a duplicate, I think. But in choosing $n$ from $2n$ think about choosing $k$ to include from the first half and $k$ to omit from the second half.
$endgroup$
– Mark Bennet
Feb 1 at 7:13
$begingroup$
@ErickWong Very neat. Turn your comment into an answer and I'll accept it!
$endgroup$
– Richard Ambler
Feb 1 at 7:32
$begingroup$
@ErickWong Very neat. Turn your comment into an answer and I'll accept it!
$endgroup$
– Richard Ambler
Feb 1 at 7:32
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Let $A,B$ be disjoint $n$-element sets; the number of $n$-element subsets of $Acup B$ is $binom2nn$. On the other hand, we can get any $n$-element subset of $Acup B$ in the following way: start with the set $A$; pick a number $k$ from $0$ to $n$; throw out $k$ elements of $A$ and replace them with $k$ elements of $B$. In other words, any $n$-element subset of $Acup B$ has the form $(Asetminus X)cup Y$ where $Xsubseteq A$, $Ysubseteq B$, $|X|=|Y|=k$ for some $kin0,dots,n$. The number of different sets we can get in this way is $sum_k=0^nbinom nkbinom nk$.
answered Feb 1 at 12:04
bofbof
52.1k558121
$endgroup$
add a comment |
$begingroup$
This is also a well know interpretation.
Let's think of a shortest way from $(0,0)$ to $(n,n)$ through lattice points and parallel to $x$-axis or $y$-axis.
The number of total way is $2n choose n$.
And each shortest way should pass one and only one of the diagonal points $(0,n), (1,n-1), ldots, (n,0)$.
The sum of all way is $sum_k=0^nnchoose k^2$.
Hence, both value are same.
answered Feb 1 at 8:58
Doyun NamDoyun Nam
67119
$endgroup$
add a comment |
$begingroup$
Another interpretation: As Erick Wong stated in the comments,
$$binomnk^2 = binomnkbinomnn - k$$
We can interpret
$$binom2nn$$
as the number of ways of selecting $n$ people from a group consisting of $n$ men and $n$ women. The expression
$$binomnkbinomnn - k$$
counts the number of ways of selecting exactly $k$ men and $n - k$ women. Since $k$ may vary from $0$ to $n$, the RHS also counts the number of ways of selecting $n$ people from $n$ men and $n$ women. Hence,
$$binom2nn = sum_k = 0^n binomnkbinomnn - k = sum_k = 0^n binomnk^2$$
answered Feb 1 at 12:03
N. F. TaussigN. F. Taussig
44.4k93357
$endgroup$
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $A,B$ be disjoint $n$-element sets; the number of $n$-element subsets of $Acup B$ is $binom2nn$. On the other hand, we can get any $n$-element subset of $Acup B$ in the following way: start with the set $A$; pick a number $k$ from $0$ to $n$; throw out $k$ elements of $A$ and replace them with $k$ elements of $B$. In other words, any $n$-element subset of $Acup B$ has the form $(Asetminus X)cup Y$ where $Xsubseteq A$, $Ysubseteq B$, $|X|=|Y|=k$ for some $kin0,dots,n$. The number of different sets we can get in this way is $sum_k=0^nbinom nkbinom nk$.
answered Feb 1 at 12:04
bofbof
52.1k558121
$endgroup$
add a comment |
$begingroup$
Let $A,B$ be disjoint $n$-element sets; the number of $n$-element subsets of $Acup B$ is $binom2nn$. On the other hand, we can get any $n$-element subset of $Acup B$ in the following way: start with the set $A$; pick a number $k$ from $0$ to $n$; throw out $k$ elements of $A$ and replace them with $k$ elements of $B$. In other words, any $n$-element subset of $Acup B$ has the form $(Asetminus X)cup Y$ where $Xsubseteq A$, $Ysubseteq B$, $|X|=|Y|=k$ for some $kin0,dots,n$. The number of different sets we can get in this way is $sum_k=0^nbinom nkbinom nk$.
answered Feb 1 at 12:04
bofbof
52.1k558121
$endgroup$
add a comment |
$begingroup$
Let $A,B$ be disjoint $n$-element sets; the number of $n$-element subsets of $Acup B$ is $binom2nn$. On the other hand, we can get any $n$-element subset of $Acup B$ in the following way: start with the set $A$; pick a number $k$ from $0$ to $n$; throw out $k$ elements of $A$ and replace them with $k$ elements of $B$. In other words, any $n$-element subset of $Acup B$ has the form $(Asetminus X)cup Y$ where $Xsubseteq A$, $Ysubseteq B$, $|X|=|Y|=k$ for some $kin0,dots,n$. The number of different sets we can get in this way is $sum_k=0^nbinom nkbinom nk$.
answered Feb 1 at 12:04
bofbof
52.1k558121
$endgroup$
Let $A,B$ be disjoint $n$-element sets; the number of $n$-element subsets of $Acup B$ is $binom2nn$. On the other hand, we can get any $n$-element subset of $Acup B$ in the following way: start with the set $A$; pick a number $k$ from $0$ to $n$; throw out $k$ elements of $A$ and replace them with $k$ elements of $B$. In other words, any $n$-element subset of $Acup B$ has the form $(Asetminus X)cup Y$ where $Xsubseteq A$, $Ysubseteq B$, $|X|=|Y|=k$ for some $kin0,dots,n$. The number of different sets we can get in this way is $sum_k=0^nbinom nkbinom nk$.
answered Feb 1 at 12:04
bofbof
52.1k558121
answered Feb 1 at 12:04
bofbof
52.1k558121
answered Feb 1 at 12:04
bofbof
52.1k558121
answered Feb 1 at 12:04
bofbof
52.1k558121
52.1k558121
add a comment |
add a comment |
$begingroup$
This is also a well know interpretation.
Let's think of a shortest way from $(0,0)$ to $(n,n)$ through lattice points and parallel to $x$-axis or $y$-axis.
The number of total way is $2n choose n$.
And each shortest way should pass one and only one of the diagonal points $(0,n), (1,n-1), ldots, (n,0)$.
The sum of all way is $sum_k=0^nnchoose k^2$.
Hence, both value are same.
answered Feb 1 at 8:58
Doyun NamDoyun Nam
67119
$endgroup$
add a comment |
$begingroup$
This is also a well know interpretation.
Let's think of a shortest way from $(0,0)$ to $(n,n)$ through lattice points and parallel to $x$-axis or $y$-axis.
The number of total way is $2n choose n$.
And each shortest way should pass one and only one of the diagonal points $(0,n), (1,n-1), ldots, (n,0)$.
The sum of all way is $sum_k=0^nnchoose k^2$.
Hence, both value are same.
answered Feb 1 at 8:58
Doyun NamDoyun Nam
67119
$endgroup$
add a comment |
$begingroup$
This is also a well know interpretation.
Let's think of a shortest way from $(0,0)$ to $(n,n)$ through lattice points and parallel to $x$-axis or $y$-axis.
The number of total way is $2n choose n$.
And each shortest way should pass one and only one of the diagonal points $(0,n), (1,n-1), ldots, (n,0)$.
The sum of all way is $sum_k=0^nnchoose k^2$.
Hence, both value are same.
answered Feb 1 at 8:58
Doyun NamDoyun Nam
67119
$endgroup$
This is also a well know interpretation.
Let's think of a shortest way from $(0,0)$ to $(n,n)$ through lattice points and parallel to $x$-axis or $y$-axis.
The number of total way is $2n choose n$.
And each shortest way should pass one and only one of the diagonal points $(0,n), (1,n-1), ldots, (n,0)$.
The sum of all way is $sum_k=0^nnchoose k^2$.
Hence, both value are same.
answered Feb 1 at 8:58
Doyun NamDoyun Nam
67119
answered Feb 1 at 8:58
Doyun NamDoyun Nam
67119
answered Feb 1 at 8:58
Doyun NamDoyun Nam
67119
answered Feb 1 at 8:58
Doyun NamDoyun Nam
67119
67119
add a comment |
add a comment |
$begingroup$
Another interpretation: As Erick Wong stated in the comments,
$$binomnk^2 = binomnkbinomnn - k$$
We can interpret
$$binom2nn$$
as the number of ways of selecting $n$ people from a group consisting of $n$ men and $n$ women. The expression
$$binomnkbinomnn - k$$
counts the number of ways of selecting exactly $k$ men and $n - k$ women. Since $k$ may vary from $0$ to $n$, the RHS also counts the number of ways of selecting $n$ people from $n$ men and $n$ women. Hence,
$$binom2nn = sum_k = 0^n binomnkbinomnn - k = sum_k = 0^n binomnk^2$$
answered Feb 1 at 12:03
N. F. TaussigN. F. Taussig
44.4k93357
$endgroup$
add a comment |
$begingroup$
Another interpretation: As Erick Wong stated in the comments,
$$binomnk^2 = binomnkbinomnn - k$$
We can interpret
$$binom2nn$$
as the number of ways of selecting $n$ people from a group consisting of $n$ men and $n$ women. The expression
$$binomnkbinomnn - k$$
counts the number of ways of selecting exactly $k$ men and $n - k$ women. Since $k$ may vary from $0$ to $n$, the RHS also counts the number of ways of selecting $n$ people from $n$ men and $n$ women. Hence,
$$binom2nn = sum_k = 0^n binomnkbinomnn - k = sum_k = 0^n binomnk^2$$
answered Feb 1 at 12:03
N. F. TaussigN. F. Taussig
44.4k93357
$endgroup$
add a comment |
$begingroup$
Another interpretation: As Erick Wong stated in the comments,
$$binomnk^2 = binomnkbinomnn - k$$
We can interpret
$$binom2nn$$
as the number of ways of selecting $n$ people from a group consisting of $n$ men and $n$ women. The expression
$$binomnkbinomnn - k$$
counts the number of ways of selecting exactly $k$ men and $n - k$ women. Since $k$ may vary from $0$ to $n$, the RHS also counts the number of ways of selecting $n$ people from $n$ men and $n$ women. Hence,
$$binom2nn = sum_k = 0^n binomnkbinomnn - k = sum_k = 0^n binomnk^2$$
answered Feb 1 at 12:03
N. F. TaussigN. F. Taussig
44.4k93357
$endgroup$
Another interpretation: As Erick Wong stated in the comments,
$$binomnk^2 = binomnkbinomnn - k$$
We can interpret
$$binom2nn$$
as the number of ways of selecting $n$ people from a group consisting of $n$ men and $n$ women. The expression
$$binomnkbinomnn - k$$
counts the number of ways of selecting exactly $k$ men and $n - k$ women. Since $k$ may vary from $0$ to $n$, the RHS also counts the number of ways of selecting $n$ people from $n$ men and $n$ women. Hence,
$$binom2nn = sum_k = 0^n binomnkbinomnn - k = sum_k = 0^n binomnk^2$$
answered Feb 1 at 12:03
N. F. TaussigN. F. Taussig
44.4k93357
answered Feb 1 at 12:03
N. F. TaussigN. F. Taussig
44.4k93357
answered Feb 1 at 12:03
N. F. TaussigN. F. Taussig
44.4k93357
answered Feb 1 at 12:03
N. F. TaussigN. F. Taussig
44.4k93357
44.4k93357
add a comment |
add a comment |
4
$begingroup$
Yes, this can be done very succinctly. Hint: Write $binomnk^2$ as $binomnkbinomnn-k$.
$endgroup$
– Erick Wong
Feb 1 at 7:12
4
$begingroup$
This must be a duplicate, I think. But in choosing $n$ from $2n$ think about choosing $k$ to include from the first half and $k$ to omit from the second half.
$endgroup$
– Mark Bennet
Feb 1 at 7:13
$begingroup$
@ErickWong Very neat. Turn your comment into an answer and I'll accept it!
$endgroup$
– Richard Ambler
Feb 1 at 7:32