Mixing
Combinatorial interpretation of identity: $sumlimits_{j=0}^bbinom{b}{j}^2binom{n+j}{2b}=binom{n}{b}^2$
$begingroup$
Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently:
begin{equation}
sum_{j=0}^bbinom{b}{j}^2binom{n+j}{2b}=binom{n}{b}^2
end{equation}
begin{equation}
sum_{j=0}^b(-1)^jbinom{b}{j}binom{n+j}{2b} = left(-1right)^b binom{n}{b}
end{equation}
In particular, the first identity appeared as a remark in Volume 4 of Henry Gould's Combinatorial Identities.
Out of curiosity, I am wondering if there is a combinatorial proof for any of these two identities?
EDIT: I have managed to prove the second identity, by considering the coefficient of $x^{n-b}$ in the expansion of $(1+x)^{-(b+1)}=(1+x)^b(1+x)^{-(2b+1)}$.
EDIT 2: I have also managed to find a proof for the first identity by using the Vandermonde identity. I would still be interested however, in a proof of the second identity using a more combinatorial approach.
combinatorics binomial-coefficients combinatorial-proofs
edited Nov 23 '18 at 18:36
darij grinberg
11.3k33164
asked Apr 14 '15 at 10:44
yoshiyoshi
421212
$endgroup$
add a comment |
$begingroup$
Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently:
begin{equation}
sum_{j=0}^bbinom{b}{j}^2binom{n+j}{2b}=binom{n}{b}^2
end{equation}
begin{equation}
sum_{j=0}^b(-1)^jbinom{b}{j}binom{n+j}{2b} = left(-1right)^b binom{n}{b}
end{equation}
In particular, the first identity appeared as a remark in Volume 4 of Henry Gould's Combinatorial Identities.
Out of curiosity, I am wondering if there is a combinatorial proof for any of these two identities?
EDIT: I have managed to prove the second identity, by considering the coefficient of $x^{n-b}$ in the expansion of $(1+x)^{-(b+1)}=(1+x)^b(1+x)^{-(2b+1)}$.
EDIT 2: I have also managed to find a proof for the first identity by using the Vandermonde identity. I would still be interested however, in a proof of the second identity using a more combinatorial approach.
combinatorics binomial-coefficients combinatorial-proofs
edited Nov 23 '18 at 18:36
darij grinberg
11.3k33164
asked Apr 14 '15 at 10:44
yoshiyoshi
421212
$endgroup$
$begingroup$
I'm not sure if this is going anywhere at all, but in the first identity, the RHS is the number of ways to pick two subsets of ${ 1,2, ldots , n }$ with $b$ elements. I was trying to come up with a bijection to get to the LHS; my intuition is that maybe the $j$ on the LHS represents the number of elements that the two sets have in common, but I wasn't able to get anywhere with that.
$endgroup$
– Marcus M
Apr 15 '15 at 2:48
add a comment |
$begingroup$
Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently:
begin{equation}
sum_{j=0}^bbinom{b}{j}^2binom{n+j}{2b}=binom{n}{b}^2
end{equation}
begin{equation}
sum_{j=0}^b(-1)^jbinom{b}{j}binom{n+j}{2b} = left(-1right)^b binom{n}{b}
end{equation}
In particular, the first identity appeared as a remark in Volume 4 of Henry Gould's Combinatorial Identities.
Out of curiosity, I am wondering if there is a combinatorial proof for any of these two identities?
EDIT: I have managed to prove the second identity, by considering the coefficient of $x^{n-b}$ in the expansion of $(1+x)^{-(b+1)}=(1+x)^b(1+x)^{-(2b+1)}$.
EDIT 2: I have also managed to find a proof for the first identity by using the Vandermonde identity. I would still be interested however, in a proof of the second identity using a more combinatorial approach.
combinatorics binomial-coefficients combinatorial-proofs
edited Nov 23 '18 at 18:36
darij grinberg
11.3k33164
asked Apr 14 '15 at 10:44
yoshiyoshi
421212
$endgroup$
Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently:
begin{equation}
sum_{j=0}^bbinom{b}{j}^2binom{n+j}{2b}=binom{n}{b}^2
end{equation}
begin{equation}
sum_{j=0}^b(-1)^jbinom{b}{j}binom{n+j}{2b} = left(-1right)^b binom{n}{b}
end{equation}
In particular, the first identity appeared as a remark in Volume 4 of Henry Gould's Combinatorial Identities.
Out of curiosity, I am wondering if there is a combinatorial proof for any of these two identities?
EDIT: I have managed to prove the second identity, by considering the coefficient of $x^{n-b}$ in the expansion of $(1+x)^{-(b+1)}=(1+x)^b(1+x)^{-(2b+1)}$.
EDIT 2: I have also managed to find a proof for the first identity by using the Vandermonde identity. I would still be interested however, in a proof of the second identity using a more combinatorial approach.
combinatorics binomial-coefficients combinatorial-proofs
combinatorics binomial-coefficients combinatorial-proofs
edited Nov 23 '18 at 18:36
darij grinberg
11.3k33164
asked Apr 14 '15 at 10:44
yoshiyoshi
421212
edited Nov 23 '18 at 18:36
darij grinberg
11.3k33164
asked Apr 14 '15 at 10:44
yoshiyoshi
421212
edited Nov 23 '18 at 18:36
darij grinberg
11.3k33164
edited Nov 23 '18 at 18:36
darij grinberg
11.3k33164
edited Nov 23 '18 at 18:36
darij grinberg
11.3k33164
11.3k33164
asked Apr 14 '15 at 10:44
yoshiyoshi
421212
asked Apr 14 '15 at 10:44
yoshiyoshi
421212
asked Apr 14 '15 at 10:44
yoshiyoshi
421212
421212
$begingroup$
I'm not sure if this is going anywhere at all, but in the first identity, the RHS is the number of ways to pick two subsets of ${ 1,2, ldots , n }$ with $b$ elements. I was trying to come up with a bijection to get to the LHS; my intuition is that maybe the $j$ on the LHS represents the number of elements that the two sets have in common, but I wasn't able to get anywhere with that.
$endgroup$
– Marcus M
Apr 15 '15 at 2:48
add a comment |
$begingroup$
I'm not sure if this is going anywhere at all, but in the first identity, the RHS is the number of ways to pick two subsets of ${ 1,2, ldots , n }$ with $b$ elements. I was trying to come up with a bijection to get to the LHS; my intuition is that maybe the $j$ on the LHS represents the number of elements that the two sets have in common, but I wasn't able to get anywhere with that.
$endgroup$
– Marcus M
Apr 15 '15 at 2:48
$begingroup$
I'm not sure if this is going anywhere at all, but in the first identity, the RHS is the number of ways to pick two subsets of ${ 1,2, ldots , n }$ with $b$ elements. I was trying to come up with a bijection to get to the LHS; my intuition is that maybe the $j$ on the LHS represents the number of elements that the two sets have in common, but I wasn't able to get anywhere with that.
$endgroup$
– Marcus M
Apr 15 '15 at 2:48
$begingroup$
I'm not sure if this is going anywhere at all, but in the first identity, the RHS is the number of ways to pick two subsets of ${ 1,2, ldots , n }$ with $b$ elements. I was trying to come up with a bijection to get to the LHS; my intuition is that maybe the $j$ on the LHS represents the number of elements that the two sets have in common, but I wasn't able to get anywhere with that.
$endgroup$
– Marcus M
Apr 15 '15 at 2:48
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
The first identity is the particular case (for $a=b$ and $x=n$) of the identity
$$
sum_{i=0}^b dbinom{a}{i} dbinom{b}{i} dbinom{x+i}{a+b} = dbinom{x}{a} dbinom{x}{b} ,
$$
which has appeared in math.stackexchange question #280481. For combinatorial proofs, see
George E. Andrews, Identities in combinatorics, I: on sorting two ordered sets, Discrete Mathematics, Volume 11, Issue 2, 1975, Pages 97--106.
George E. Andrews, David M. Bressoud, Identities in combinatorics III: Further aspects of ordered set sorting, Discrete Mathematics, Volume 49, Issue 3, May 1984, Pages 223--236.
I also give an algebraic proof in Proposition 3.39 (f) of my Notes on the combinatorial fundamentals of algebra (search for "assortment of other identities" if the numbering has changed, or else look at the archived version of 10 January 2019).
The second identity is the particular case (for $d=2b$) of the following identity:
$$
sum_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b} ,
$$
where $d$ and $b$ are two nonnegative integers and $n$ is an arbitrary (e.g., rational) number.
This can be easily proven by induction over $b$.
Alternatively, one can WLOG assume that $n in left{d, d+1, d+2, ldotsright}$, and then apply some symmetry and upper negation to reduce it to the Vandermonde convolution.
For yet another proof, try using finite differences (the necessary ideas are in Marc van Leeuwen's answer https://math.stackexchange.com/a/381939/ ).
This does not give a combinatorial proof, but it makes me suspect that it is well-known, and hopefully someone has collected combinatorial proofs of such identities.
answered Sep 28 '15 at 1:21
darij grinbergdarij grinberg
11.3k33164
$endgroup$
$begingroup$
(+1). The references and observations are a good improvement of the page.
$endgroup$
– Marko Riedel
Sep 28 '15 at 1:44
add a comment |
$begingroup$
By way of enrichment permit me to present an algebraic proof.
Suppose we seek to verify that
$$sum_{j=0}^b {bchoose j}^2
{n+jchoose 2b} = {nchoose b}^2.$$
where $0le ble n.$
Introduce
$${bchoose j} =
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-j+1}}
frac{1}{(1-z)^{j+1}} ; dz$$
and
$${n+jchoose 2b} =
frac{1}{2pi i}
int_{|w|=epsilon} frac{1}{w^{2b+1}}
(1+w)^{n+j} ; dw.$$
This yields for the sum
$$frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
sum_{j=0}^b {bchoose j} (1+w)^j frac{z^j}{(1-z)^j}
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
left(1+frac{(1+w)z}{1-z}right)^b
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{(1-z)^{b+1}}
(1+wz)^b ; dz ; dw.$$
The inner residue is
$$sum_{q=0}^b {bchoose q} w^q {b-q+bchoose b}.$$
Substitute this into the outer integral to get
$$sum_{q=0}^b {bchoose q} {2b-qchoose b}
{nchoose 2b-q}.$$
Observe that
$${2b-qchoose b}{nchoose 2b-q}
= frac{(2b-q)!}{b! (b-q)!}frac{n!}{(2b-q)! (n-2b+q)!}
\ = frac{(n-b)!}{b! (b-q)!}frac{n!}{(n-b)! (n-2b+q)!}
= {nchoose b} {n-bchoose b-q}.$$
This yields for the sum
$${nchoose b} sum_{q=0}^b {bchoose q}
{n-bchoose b-q}.$$
which evaluates to
$${nchoose b}^2$$
by inspection.
It can also be done with the integral
$$frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-q+1}} (1+z)^{n-b} ; dz$$
which yields
$${nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n-b}
sum_{q=0}^b {bchoose q} z^q ; dz
\ = {nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n} ; dz
= {nchoose b}^2.$$
answered Sep 27 '15 at 23:44
Marko RiedelMarko Riedel
40.3k339109
$endgroup$
add a comment |
$begingroup$
Combinatorial proof of the second identity
Let $B$ be a $b$-element set and let $N$ be an $n$-element set disjoint to $B$.
The sum $sum_jbinom b{b-j}binom{n+j}{2b}$ counts the number of pairs of sets $Tsubset B$, $Xsubset Ncup B$ s.t. $|X|=2b$ and $Xcap T=varnothing$. (Indeed, one summand corresponds to choosing first $(b-j)$-element set $Tsubset B$ and then $2b$-element set $Xsubset Ncup(Bsetminus T)$.) And LHS counts such pairs with signs $(-1)^{|B setminus T|}$.
Now there is a sign-reversing involution: find the smallest element of $Bsetminus X$ and then add it to $T$ if it's not already in $T$, otherwise remove it from $T$. So in LHS everything with non-empty $Bsetminus X$ cancels out; and there are exactly $binom nb$ variants with $Xsupset B$ and they are counted with sign $(-1)^b$.
(And the RHS is, in fact, $(-1)^bbinom nb$.)
edited Nov 23 '18 at 18:33
darij grinberg
11.3k33164
answered Jun 20 '15 at 20:02
Grigory MGrigory M
13.6k357104
$endgroup$
1
$begingroup$
I guess this argument also applies to the generalization $sumlimits_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b}$ ?
$endgroup$
– darij grinberg
Sep 28 '15 at 1:48
$begingroup$
(Re: generalization) indeed
$endgroup$
– Grigory M
Oct 1 '15 at 14:14
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1234156%2fcombinatorial-interpretation-of-identity-sum-limits-j-0b-binombj2-bin%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The first identity is the particular case (for $a=b$ and $x=n$) of the identity
$$
sum_{i=0}^b dbinom{a}{i} dbinom{b}{i} dbinom{x+i}{a+b} = dbinom{x}{a} dbinom{x}{b} ,
$$
which has appeared in math.stackexchange question #280481. For combinatorial proofs, see
George E. Andrews, Identities in combinatorics, I: on sorting two ordered sets, Discrete Mathematics, Volume 11, Issue 2, 1975, Pages 97--106.
George E. Andrews, David M. Bressoud, Identities in combinatorics III: Further aspects of ordered set sorting, Discrete Mathematics, Volume 49, Issue 3, May 1984, Pages 223--236.
I also give an algebraic proof in Proposition 3.39 (f) of my Notes on the combinatorial fundamentals of algebra (search for "assortment of other identities" if the numbering has changed, or else look at the archived version of 10 January 2019).
The second identity is the particular case (for $d=2b$) of the following identity:
$$
sum_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b} ,
$$
where $d$ and $b$ are two nonnegative integers and $n$ is an arbitrary (e.g., rational) number.
This can be easily proven by induction over $b$.
Alternatively, one can WLOG assume that $n in left{d, d+1, d+2, ldotsright}$, and then apply some symmetry and upper negation to reduce it to the Vandermonde convolution.
For yet another proof, try using finite differences (the necessary ideas are in Marc van Leeuwen's answer https://math.stackexchange.com/a/381939/ ).
This does not give a combinatorial proof, but it makes me suspect that it is well-known, and hopefully someone has collected combinatorial proofs of such identities.
answered Sep 28 '15 at 1:21
darij grinbergdarij grinberg
11.3k33164
$endgroup$
$begingroup$
(+1). The references and observations are a good improvement of the page.
$endgroup$
– Marko Riedel
Sep 28 '15 at 1:44
add a comment |
$begingroup$
The first identity is the particular case (for $a=b$ and $x=n$) of the identity
$$
sum_{i=0}^b dbinom{a}{i} dbinom{b}{i} dbinom{x+i}{a+b} = dbinom{x}{a} dbinom{x}{b} ,
$$
which has appeared in math.stackexchange question #280481. For combinatorial proofs, see
George E. Andrews, Identities in combinatorics, I: on sorting two ordered sets, Discrete Mathematics, Volume 11, Issue 2, 1975, Pages 97--106.
George E. Andrews, David M. Bressoud, Identities in combinatorics III: Further aspects of ordered set sorting, Discrete Mathematics, Volume 49, Issue 3, May 1984, Pages 223--236.
I also give an algebraic proof in Proposition 3.39 (f) of my Notes on the combinatorial fundamentals of algebra (search for "assortment of other identities" if the numbering has changed, or else look at the archived version of 10 January 2019).
The second identity is the particular case (for $d=2b$) of the following identity:
$$
sum_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b} ,
$$
where $d$ and $b$ are two nonnegative integers and $n$ is an arbitrary (e.g., rational) number.
This can be easily proven by induction over $b$.
Alternatively, one can WLOG assume that $n in left{d, d+1, d+2, ldotsright}$, and then apply some symmetry and upper negation to reduce it to the Vandermonde convolution.
For yet another proof, try using finite differences (the necessary ideas are in Marc van Leeuwen's answer https://math.stackexchange.com/a/381939/ ).
This does not give a combinatorial proof, but it makes me suspect that it is well-known, and hopefully someone has collected combinatorial proofs of such identities.
answered Sep 28 '15 at 1:21
darij grinbergdarij grinberg
11.3k33164
$endgroup$
$begingroup$
(+1). The references and observations are a good improvement of the page.
$endgroup$
– Marko Riedel
Sep 28 '15 at 1:44
add a comment |
$begingroup$
The first identity is the particular case (for $a=b$ and $x=n$) of the identity
$$
sum_{i=0}^b dbinom{a}{i} dbinom{b}{i} dbinom{x+i}{a+b} = dbinom{x}{a} dbinom{x}{b} ,
$$
which has appeared in math.stackexchange question #280481. For combinatorial proofs, see
George E. Andrews, Identities in combinatorics, I: on sorting two ordered sets, Discrete Mathematics, Volume 11, Issue 2, 1975, Pages 97--106.
George E. Andrews, David M. Bressoud, Identities in combinatorics III: Further aspects of ordered set sorting, Discrete Mathematics, Volume 49, Issue 3, May 1984, Pages 223--236.
I also give an algebraic proof in Proposition 3.39 (f) of my Notes on the combinatorial fundamentals of algebra (search for "assortment of other identities" if the numbering has changed, or else look at the archived version of 10 January 2019).
The second identity is the particular case (for $d=2b$) of the following identity:
$$
sum_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b} ,
$$
where $d$ and $b$ are two nonnegative integers and $n$ is an arbitrary (e.g., rational) number.
This can be easily proven by induction over $b$.
Alternatively, one can WLOG assume that $n in left{d, d+1, d+2, ldotsright}$, and then apply some symmetry and upper negation to reduce it to the Vandermonde convolution.
For yet another proof, try using finite differences (the necessary ideas are in Marc van Leeuwen's answer https://math.stackexchange.com/a/381939/ ).
This does not give a combinatorial proof, but it makes me suspect that it is well-known, and hopefully someone has collected combinatorial proofs of such identities.
answered Sep 28 '15 at 1:21
darij grinbergdarij grinberg
11.3k33164
$endgroup$
The first identity is the particular case (for $a=b$ and $x=n$) of the identity
$$
sum_{i=0}^b dbinom{a}{i} dbinom{b}{i} dbinom{x+i}{a+b} = dbinom{x}{a} dbinom{x}{b} ,
$$
which has appeared in math.stackexchange question #280481. For combinatorial proofs, see
George E. Andrews, Identities in combinatorics, I: on sorting two ordered sets, Discrete Mathematics, Volume 11, Issue 2, 1975, Pages 97--106.
George E. Andrews, David M. Bressoud, Identities in combinatorics III: Further aspects of ordered set sorting, Discrete Mathematics, Volume 49, Issue 3, May 1984, Pages 223--236.
I also give an algebraic proof in Proposition 3.39 (f) of my Notes on the combinatorial fundamentals of algebra (search for "assortment of other identities" if the numbering has changed, or else look at the archived version of 10 January 2019).
The second identity is the particular case (for $d=2b$) of the following identity:
$$
sum_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b} ,
$$
where $d$ and $b$ are two nonnegative integers and $n$ is an arbitrary (e.g., rational) number.
This can be easily proven by induction over $b$.
Alternatively, one can WLOG assume that $n in left{d, d+1, d+2, ldotsright}$, and then apply some symmetry and upper negation to reduce it to the Vandermonde convolution.
For yet another proof, try using finite differences (the necessary ideas are in Marc van Leeuwen's answer https://math.stackexchange.com/a/381939/ ).
This does not give a combinatorial proof, but it makes me suspect that it is well-known, and hopefully someone has collected combinatorial proofs of such identities.
answered Sep 28 '15 at 1:21
darij grinbergdarij grinberg
11.3k33164
edited Jan 15 at 22:17
answered Sep 28 '15 at 1:21
darij grinbergdarij grinberg
11.3k33164
answered Sep 28 '15 at 1:21
darij grinbergdarij grinberg
11.3k33164
answered Sep 28 '15 at 1:21
darij grinbergdarij grinberg
11.3k33164
11.3k33164
$begingroup$
(+1). The references and observations are a good improvement of the page.
$endgroup$
– Marko Riedel
Sep 28 '15 at 1:44
add a comment |
$begingroup$
(+1). The references and observations are a good improvement of the page.
$endgroup$
– Marko Riedel
Sep 28 '15 at 1:44
$begingroup$
(+1). The references and observations are a good improvement of the page.
$endgroup$
– Marko Riedel
Sep 28 '15 at 1:44
$begingroup$
(+1). The references and observations are a good improvement of the page.
$endgroup$
– Marko Riedel
Sep 28 '15 at 1:44
add a comment |
$begingroup$
By way of enrichment permit me to present an algebraic proof.
Suppose we seek to verify that
$$sum_{j=0}^b {bchoose j}^2
{n+jchoose 2b} = {nchoose b}^2.$$
where $0le ble n.$
Introduce
$${bchoose j} =
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-j+1}}
frac{1}{(1-z)^{j+1}} ; dz$$
and
$${n+jchoose 2b} =
frac{1}{2pi i}
int_{|w|=epsilon} frac{1}{w^{2b+1}}
(1+w)^{n+j} ; dw.$$
This yields for the sum
$$frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
sum_{j=0}^b {bchoose j} (1+w)^j frac{z^j}{(1-z)^j}
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
left(1+frac{(1+w)z}{1-z}right)^b
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{(1-z)^{b+1}}
(1+wz)^b ; dz ; dw.$$
The inner residue is
$$sum_{q=0}^b {bchoose q} w^q {b-q+bchoose b}.$$
Substitute this into the outer integral to get
$$sum_{q=0}^b {bchoose q} {2b-qchoose b}
{nchoose 2b-q}.$$
Observe that
$${2b-qchoose b}{nchoose 2b-q}
= frac{(2b-q)!}{b! (b-q)!}frac{n!}{(2b-q)! (n-2b+q)!}
\ = frac{(n-b)!}{b! (b-q)!}frac{n!}{(n-b)! (n-2b+q)!}
= {nchoose b} {n-bchoose b-q}.$$
This yields for the sum
$${nchoose b} sum_{q=0}^b {bchoose q}
{n-bchoose b-q}.$$
which evaluates to
$${nchoose b}^2$$
by inspection.
It can also be done with the integral
$$frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-q+1}} (1+z)^{n-b} ; dz$$
which yields
$${nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n-b}
sum_{q=0}^b {bchoose q} z^q ; dz
\ = {nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n} ; dz
= {nchoose b}^2.$$
answered Sep 27 '15 at 23:44
Marko RiedelMarko Riedel
40.3k339109
$endgroup$
add a comment |
$begingroup$
By way of enrichment permit me to present an algebraic proof.
Suppose we seek to verify that
$$sum_{j=0}^b {bchoose j}^2
{n+jchoose 2b} = {nchoose b}^2.$$
where $0le ble n.$
Introduce
$${bchoose j} =
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-j+1}}
frac{1}{(1-z)^{j+1}} ; dz$$
and
$${n+jchoose 2b} =
frac{1}{2pi i}
int_{|w|=epsilon} frac{1}{w^{2b+1}}
(1+w)^{n+j} ; dw.$$
This yields for the sum
$$frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
sum_{j=0}^b {bchoose j} (1+w)^j frac{z^j}{(1-z)^j}
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
left(1+frac{(1+w)z}{1-z}right)^b
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{(1-z)^{b+1}}
(1+wz)^b ; dz ; dw.$$
The inner residue is
$$sum_{q=0}^b {bchoose q} w^q {b-q+bchoose b}.$$
Substitute this into the outer integral to get
$$sum_{q=0}^b {bchoose q} {2b-qchoose b}
{nchoose 2b-q}.$$
Observe that
$${2b-qchoose b}{nchoose 2b-q}
= frac{(2b-q)!}{b! (b-q)!}frac{n!}{(2b-q)! (n-2b+q)!}
\ = frac{(n-b)!}{b! (b-q)!}frac{n!}{(n-b)! (n-2b+q)!}
= {nchoose b} {n-bchoose b-q}.$$
This yields for the sum
$${nchoose b} sum_{q=0}^b {bchoose q}
{n-bchoose b-q}.$$
which evaluates to
$${nchoose b}^2$$
by inspection.
It can also be done with the integral
$$frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-q+1}} (1+z)^{n-b} ; dz$$
which yields
$${nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n-b}
sum_{q=0}^b {bchoose q} z^q ; dz
\ = {nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n} ; dz
= {nchoose b}^2.$$
answered Sep 27 '15 at 23:44
Marko RiedelMarko Riedel
40.3k339109
$endgroup$
add a comment |
$begingroup$
By way of enrichment permit me to present an algebraic proof.
Suppose we seek to verify that
$$sum_{j=0}^b {bchoose j}^2
{n+jchoose 2b} = {nchoose b}^2.$$
where $0le ble n.$
Introduce
$${bchoose j} =
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-j+1}}
frac{1}{(1-z)^{j+1}} ; dz$$
and
$${n+jchoose 2b} =
frac{1}{2pi i}
int_{|w|=epsilon} frac{1}{w^{2b+1}}
(1+w)^{n+j} ; dw.$$
This yields for the sum
$$frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
sum_{j=0}^b {bchoose j} (1+w)^j frac{z^j}{(1-z)^j}
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
left(1+frac{(1+w)z}{1-z}right)^b
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{(1-z)^{b+1}}
(1+wz)^b ; dz ; dw.$$
The inner residue is
$$sum_{q=0}^b {bchoose q} w^q {b-q+bchoose b}.$$
Substitute this into the outer integral to get
$$sum_{q=0}^b {bchoose q} {2b-qchoose b}
{nchoose 2b-q}.$$
Observe that
$${2b-qchoose b}{nchoose 2b-q}
= frac{(2b-q)!}{b! (b-q)!}frac{n!}{(2b-q)! (n-2b+q)!}
\ = frac{(n-b)!}{b! (b-q)!}frac{n!}{(n-b)! (n-2b+q)!}
= {nchoose b} {n-bchoose b-q}.$$
This yields for the sum
$${nchoose b} sum_{q=0}^b {bchoose q}
{n-bchoose b-q}.$$
which evaluates to
$${nchoose b}^2$$
by inspection.
It can also be done with the integral
$$frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-q+1}} (1+z)^{n-b} ; dz$$
which yields
$${nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n-b}
sum_{q=0}^b {bchoose q} z^q ; dz
\ = {nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n} ; dz
= {nchoose b}^2.$$
answered Sep 27 '15 at 23:44
Marko RiedelMarko Riedel
40.3k339109
$endgroup$
By way of enrichment permit me to present an algebraic proof.
Suppose we seek to verify that
$$sum_{j=0}^b {bchoose j}^2
{n+jchoose 2b} = {nchoose b}^2.$$
where $0le ble n.$
Introduce
$${bchoose j} =
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-j+1}}
frac{1}{(1-z)^{j+1}} ; dz$$
and
$${n+jchoose 2b} =
frac{1}{2pi i}
int_{|w|=epsilon} frac{1}{w^{2b+1}}
(1+w)^{n+j} ; dw.$$
This yields for the sum
$$frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
sum_{j=0}^b {bchoose j} (1+w)^j frac{z^j}{(1-z)^j}
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
left(1+frac{(1+w)z}{1-z}right)^b
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{(1-z)^{b+1}}
(1+wz)^b ; dz ; dw.$$
The inner residue is
$$sum_{q=0}^b {bchoose q} w^q {b-q+bchoose b}.$$
Substitute this into the outer integral to get
$$sum_{q=0}^b {bchoose q} {2b-qchoose b}
{nchoose 2b-q}.$$
Observe that
$${2b-qchoose b}{nchoose 2b-q}
= frac{(2b-q)!}{b! (b-q)!}frac{n!}{(2b-q)! (n-2b+q)!}
\ = frac{(n-b)!}{b! (b-q)!}frac{n!}{(n-b)! (n-2b+q)!}
= {nchoose b} {n-bchoose b-q}.$$
This yields for the sum
$${nchoose b} sum_{q=0}^b {bchoose q}
{n-bchoose b-q}.$$
which evaluates to
$${nchoose b}^2$$
by inspection.
It can also be done with the integral
$$frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b-q+1}} (1+z)^{n-b} ; dz$$
which yields
$${nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n-b}
sum_{q=0}^b {bchoose q} z^q ; dz
\ = {nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n} ; dz
= {nchoose b}^2.$$
answered Sep 27 '15 at 23:44
Marko RiedelMarko Riedel
40.3k339109
edited Sep 28 '15 at 0:24
answered Sep 27 '15 at 23:44
Marko RiedelMarko Riedel
40.3k339109
answered Sep 27 '15 at 23:44
Marko RiedelMarko Riedel
40.3k339109
answered Sep 27 '15 at 23:44
Marko RiedelMarko Riedel
40.3k339109
40.3k339109
add a comment |
add a comment |
$begingroup$
Combinatorial proof of the second identity
Let $B$ be a $b$-element set and let $N$ be an $n$-element set disjoint to $B$.
The sum $sum_jbinom b{b-j}binom{n+j}{2b}$ counts the number of pairs of sets $Tsubset B$, $Xsubset Ncup B$ s.t. $|X|=2b$ and $Xcap T=varnothing$. (Indeed, one summand corresponds to choosing first $(b-j)$-element set $Tsubset B$ and then $2b$-element set $Xsubset Ncup(Bsetminus T)$.) And LHS counts such pairs with signs $(-1)^{|B setminus T|}$.
Now there is a sign-reversing involution: find the smallest element of $Bsetminus X$ and then add it to $T$ if it's not already in $T$, otherwise remove it from $T$. So in LHS everything with non-empty $Bsetminus X$ cancels out; and there are exactly $binom nb$ variants with $Xsupset B$ and they are counted with sign $(-1)^b$.
(And the RHS is, in fact, $(-1)^bbinom nb$.)
edited Nov 23 '18 at 18:33
darij grinberg
11.3k33164
answered Jun 20 '15 at 20:02
Grigory MGrigory M
13.6k357104
$endgroup$
1
$begingroup$
I guess this argument also applies to the generalization $sumlimits_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b}$ ?
$endgroup$
– darij grinberg
Sep 28 '15 at 1:48
$begingroup$
(Re: generalization) indeed
$endgroup$
– Grigory M
Oct 1 '15 at 14:14
add a comment |
$begingroup$
Combinatorial proof of the second identity
Let $B$ be a $b$-element set and let $N$ be an $n$-element set disjoint to $B$.
The sum $sum_jbinom b{b-j}binom{n+j}{2b}$ counts the number of pairs of sets $Tsubset B$, $Xsubset Ncup B$ s.t. $|X|=2b$ and $Xcap T=varnothing$. (Indeed, one summand corresponds to choosing first $(b-j)$-element set $Tsubset B$ and then $2b$-element set $Xsubset Ncup(Bsetminus T)$.) And LHS counts such pairs with signs $(-1)^{|B setminus T|}$.
Now there is a sign-reversing involution: find the smallest element of $Bsetminus X$ and then add it to $T$ if it's not already in $T$, otherwise remove it from $T$. So in LHS everything with non-empty $Bsetminus X$ cancels out; and there are exactly $binom nb$ variants with $Xsupset B$ and they are counted with sign $(-1)^b$.
(And the RHS is, in fact, $(-1)^bbinom nb$.)
edited Nov 23 '18 at 18:33
darij grinberg
11.3k33164
answered Jun 20 '15 at 20:02
Grigory MGrigory M
13.6k357104
$endgroup$
1
$begingroup$
I guess this argument also applies to the generalization $sumlimits_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b}$ ?
$endgroup$
– darij grinberg
Sep 28 '15 at 1:48
$begingroup$
(Re: generalization) indeed
$endgroup$
– Grigory M
Oct 1 '15 at 14:14
add a comment |
$begingroup$
Combinatorial proof of the second identity
Let $B$ be a $b$-element set and let $N$ be an $n$-element set disjoint to $B$.
The sum $sum_jbinom b{b-j}binom{n+j}{2b}$ counts the number of pairs of sets $Tsubset B$, $Xsubset Ncup B$ s.t. $|X|=2b$ and $Xcap T=varnothing$. (Indeed, one summand corresponds to choosing first $(b-j)$-element set $Tsubset B$ and then $2b$-element set $Xsubset Ncup(Bsetminus T)$.) And LHS counts such pairs with signs $(-1)^{|B setminus T|}$.
Now there is a sign-reversing involution: find the smallest element of $Bsetminus X$ and then add it to $T$ if it's not already in $T$, otherwise remove it from $T$. So in LHS everything with non-empty $Bsetminus X$ cancels out; and there are exactly $binom nb$ variants with $Xsupset B$ and they are counted with sign $(-1)^b$.
(And the RHS is, in fact, $(-1)^bbinom nb$.)
edited Nov 23 '18 at 18:33
darij grinberg
11.3k33164
answered Jun 20 '15 at 20:02
Grigory MGrigory M
13.6k357104
$endgroup$
Combinatorial proof of the second identity
Let $B$ be a $b$-element set and let $N$ be an $n$-element set disjoint to $B$.
The sum $sum_jbinom b{b-j}binom{n+j}{2b}$ counts the number of pairs of sets $Tsubset B$, $Xsubset Ncup B$ s.t. $|X|=2b$ and $Xcap T=varnothing$. (Indeed, one summand corresponds to choosing first $(b-j)$-element set $Tsubset B$ and then $2b$-element set $Xsubset Ncup(Bsetminus T)$.) And LHS counts such pairs with signs $(-1)^{|B setminus T|}$.
Now there is a sign-reversing involution: find the smallest element of $Bsetminus X$ and then add it to $T$ if it's not already in $T$, otherwise remove it from $T$. So in LHS everything with non-empty $Bsetminus X$ cancels out; and there are exactly $binom nb$ variants with $Xsupset B$ and they are counted with sign $(-1)^b$.
(And the RHS is, in fact, $(-1)^bbinom nb$.)
edited Nov 23 '18 at 18:33
darij grinberg
11.3k33164
answered Jun 20 '15 at 20:02
Grigory MGrigory M
13.6k357104
edited Nov 23 '18 at 18:33
darij grinberg
11.3k33164
edited Nov 23 '18 at 18:33
darij grinberg
11.3k33164
edited Nov 23 '18 at 18:33
darij grinberg
11.3k33164
11.3k33164
answered Jun 20 '15 at 20:02
Grigory MGrigory M
13.6k357104
answered Jun 20 '15 at 20:02
Grigory MGrigory M
13.6k357104
answered Jun 20 '15 at 20:02
Grigory MGrigory M
13.6k357104
13.6k357104
1
$begingroup$
I guess this argument also applies to the generalization $sumlimits_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b}$ ?
$endgroup$
– darij grinberg
Sep 28 '15 at 1:48
$begingroup$
(Re: generalization) indeed
$endgroup$
– Grigory M
Oct 1 '15 at 14:14
add a comment |
1
$begingroup$
I guess this argument also applies to the generalization $sumlimits_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b}$ ?
$endgroup$
– darij grinberg
Sep 28 '15 at 1:48
$begingroup$
(Re: generalization) indeed
$endgroup$
– Grigory M
Oct 1 '15 at 14:14
1
1
$begingroup$
I guess this argument also applies to the generalization $sumlimits_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b}$ ?
$endgroup$
– darij grinberg
Sep 28 '15 at 1:48
$begingroup$
I guess this argument also applies to the generalization $sumlimits_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b}$ ?
$endgroup$
– darij grinberg
Sep 28 '15 at 1:48
$begingroup$
(Re: generalization) indeed
$endgroup$
– Grigory M
Oct 1 '15 at 14:14
$begingroup$
(Re: generalization) indeed
$endgroup$
– Grigory M
Oct 1 '15 at 14:14
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1234156%2fcombinatorial-interpretation-of-identity-sum-limits-j-0b-binombj2-bin%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I'm not sure if this is going anywhere at all, but in the first identity, the RHS is the number of ways to pick two subsets of ${ 1,2, ldots , n }$ with $b$ elements. I was trying to come up with a bijection to get to the LHS; my intuition is that maybe the $j$ on the LHS represents the number of elements that the two sets have in common, but I wasn't able to get anywhere with that.
$endgroup$
– Marcus M
Apr 15 '15 at 2:48