Combinatorial proof of summation of $sumlimits_{k = 0}^n {n choose k}^2= {2n choose n}$
$begingroup$
I was hoping to find a more "mathematical" proof, instead of proving logically $displaystyle sum_{k = 0}^n {n choose k}^2= {2n choose n}$.
I already know the logical Proof:
$${n choose k}^2 = {n choose k}{ n choose n-k}$$
Hence summation can be expressed as:
$$binom{n}{0}binom{n}{n} + binom{n}{1}binom{n}{n-1} + cdots + binom{n}{n}binom{n}{0}$$
One can think of it as choosing $n$ people from a group of $2n$
(imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$.
combinatorics summation binomial-coefficients combinatorial-proofs
$endgroup$
|
show 3 more comments
$begingroup$
I was hoping to find a more "mathematical" proof, instead of proving logically $displaystyle sum_{k = 0}^n {n choose k}^2= {2n choose n}$.
I already know the logical Proof:
$${n choose k}^2 = {n choose k}{ n choose n-k}$$
Hence summation can be expressed as:
$$binom{n}{0}binom{n}{n} + binom{n}{1}binom{n}{n-1} + cdots + binom{n}{n}binom{n}{0}$$
One can think of it as choosing $n$ people from a group of $2n$
(imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$.
combinatorics summation binomial-coefficients combinatorial-proofs
$endgroup$
16
$begingroup$
Just FYI, what you call a "logical proof" is known as a "combinatorial proof", and such a proof is perfectly valid and often very insightful. What I suspect you mean by "mathematical proof" is one dealing with the numerical structure of sums and combinations, which would be better called an "analytical proof". Both styles of proof are equally mathematical.
$endgroup$
– Austin Mohr
May 23 '12 at 4:57
6
$begingroup$
This is secretly subsumed by this question
$endgroup$
– davidlowryduda♦
May 23 '12 at 5:00
1
$begingroup$
You could obtain the same combinatorial proof by noting that $binom{2n}{n}$ counts the number of paths from $(0,0)$ to $(n,n)$ on an $ntimes n$ grid.
$endgroup$
– Holdsworth88
May 23 '12 at 6:03
7
$begingroup$
I think your combinatorial proof is really nice, and you should not be unhappy with it.
$endgroup$
– MJD
May 23 '12 at 13:54
2
$begingroup$
Incidentally, this is a special case of math.stackexchange.com/questions/337923/….
$endgroup$
– Greek - Area 51 Proposal
Nov 16 '13 at 10:26
|
show 3 more comments
$begingroup$
I was hoping to find a more "mathematical" proof, instead of proving logically $displaystyle sum_{k = 0}^n {n choose k}^2= {2n choose n}$.
I already know the logical Proof:
$${n choose k}^2 = {n choose k}{ n choose n-k}$$
Hence summation can be expressed as:
$$binom{n}{0}binom{n}{n} + binom{n}{1}binom{n}{n-1} + cdots + binom{n}{n}binom{n}{0}$$
One can think of it as choosing $n$ people from a group of $2n$
(imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$.
combinatorics summation binomial-coefficients combinatorial-proofs
$endgroup$
I was hoping to find a more "mathematical" proof, instead of proving logically $displaystyle sum_{k = 0}^n {n choose k}^2= {2n choose n}$.
I already know the logical Proof:
$${n choose k}^2 = {n choose k}{ n choose n-k}$$
Hence summation can be expressed as:
$$binom{n}{0}binom{n}{n} + binom{n}{1}binom{n}{n-1} + cdots + binom{n}{n}binom{n}{0}$$
One can think of it as choosing $n$ people from a group of $2n$
(imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$.
combinatorics summation binomial-coefficients combinatorial-proofs
combinatorics summation binomial-coefficients combinatorial-proofs
edited May 9 '18 at 4:59
Greek - Area 51 Proposal
3,168769103
3,168769103
asked May 23 '12 at 4:52
Lance CLance C
286143
286143
16
$begingroup$
Just FYI, what you call a "logical proof" is known as a "combinatorial proof", and such a proof is perfectly valid and often very insightful. What I suspect you mean by "mathematical proof" is one dealing with the numerical structure of sums and combinations, which would be better called an "analytical proof". Both styles of proof are equally mathematical.
$endgroup$
– Austin Mohr
May 23 '12 at 4:57
6
$begingroup$
This is secretly subsumed by this question
$endgroup$
– davidlowryduda♦
May 23 '12 at 5:00
1
$begingroup$
You could obtain the same combinatorial proof by noting that $binom{2n}{n}$ counts the number of paths from $(0,0)$ to $(n,n)$ on an $ntimes n$ grid.
$endgroup$
– Holdsworth88
May 23 '12 at 6:03
7
$begingroup$
I think your combinatorial proof is really nice, and you should not be unhappy with it.
$endgroup$
– MJD
May 23 '12 at 13:54
2
$begingroup$
Incidentally, this is a special case of math.stackexchange.com/questions/337923/….
$endgroup$
– Greek - Area 51 Proposal
Nov 16 '13 at 10:26
|
show 3 more comments
16
$begingroup$
Just FYI, what you call a "logical proof" is known as a "combinatorial proof", and such a proof is perfectly valid and often very insightful. What I suspect you mean by "mathematical proof" is one dealing with the numerical structure of sums and combinations, which would be better called an "analytical proof". Both styles of proof are equally mathematical.
$endgroup$
– Austin Mohr
May 23 '12 at 4:57
6
$begingroup$
This is secretly subsumed by this question
$endgroup$
– davidlowryduda♦
May 23 '12 at 5:00
1
$begingroup$
You could obtain the same combinatorial proof by noting that $binom{2n}{n}$ counts the number of paths from $(0,0)$ to $(n,n)$ on an $ntimes n$ grid.
$endgroup$
– Holdsworth88
May 23 '12 at 6:03
7
$begingroup$
I think your combinatorial proof is really nice, and you should not be unhappy with it.
$endgroup$
– MJD
May 23 '12 at 13:54
2
$begingroup$
Incidentally, this is a special case of math.stackexchange.com/questions/337923/….
$endgroup$
– Greek - Area 51 Proposal
Nov 16 '13 at 10:26
16
16
$begingroup$
Just FYI, what you call a "logical proof" is known as a "combinatorial proof", and such a proof is perfectly valid and often very insightful. What I suspect you mean by "mathematical proof" is one dealing with the numerical structure of sums and combinations, which would be better called an "analytical proof". Both styles of proof are equally mathematical.
$endgroup$
– Austin Mohr
May 23 '12 at 4:57
$begingroup$
Just FYI, what you call a "logical proof" is known as a "combinatorial proof", and such a proof is perfectly valid and often very insightful. What I suspect you mean by "mathematical proof" is one dealing with the numerical structure of sums and combinations, which would be better called an "analytical proof". Both styles of proof are equally mathematical.
$endgroup$
– Austin Mohr
May 23 '12 at 4:57
6
6
$begingroup$
This is secretly subsumed by this question
$endgroup$
– davidlowryduda♦
May 23 '12 at 5:00
$begingroup$
This is secretly subsumed by this question
$endgroup$
– davidlowryduda♦
May 23 '12 at 5:00
1
1
$begingroup$
You could obtain the same combinatorial proof by noting that $binom{2n}{n}$ counts the number of paths from $(0,0)$ to $(n,n)$ on an $ntimes n$ grid.
$endgroup$
– Holdsworth88
May 23 '12 at 6:03
$begingroup$
You could obtain the same combinatorial proof by noting that $binom{2n}{n}$ counts the number of paths from $(0,0)$ to $(n,n)$ on an $ntimes n$ grid.
$endgroup$
– Holdsworth88
May 23 '12 at 6:03
7
7
$begingroup$
I think your combinatorial proof is really nice, and you should not be unhappy with it.
$endgroup$
– MJD
May 23 '12 at 13:54
$begingroup$
I think your combinatorial proof is really nice, and you should not be unhappy with it.
$endgroup$
– MJD
May 23 '12 at 13:54
2
2
$begingroup$
Incidentally, this is a special case of math.stackexchange.com/questions/337923/….
$endgroup$
– Greek - Area 51 Proposal
Nov 16 '13 at 10:26
$begingroup$
Incidentally, this is a special case of math.stackexchange.com/questions/337923/….
$endgroup$
– Greek - Area 51 Proposal
Nov 16 '13 at 10:26
|
show 3 more comments
6 Answers
6
active
oldest
votes
$begingroup$
The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that
$$(1+x)^n(x+1)^n=left(sum_{a=0}^nbinom{n}{a}x^aright)left(sum_{b=0}^nbinom{n}{b}x^{n-b}right)=sum_{c=0}^{2n}left(sum_{a+n-b=c}binom{n}{a}binom{n}{b}right)x^c$$
The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is
$$sum_{a+n-b=n}binom{n}{a}binom{n}{b}=sum_{a=0}^nbinom{n}{a}^2.$$
However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is
$$binom{2n}{n}. $$
Equating the two gives the result.
$endgroup$
$begingroup$
+1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion.
$endgroup$
– user17762
May 23 '12 at 5:12
$begingroup$
Can you explain me in more detail... why $sum_{a=0}^nbinom{n}{a}x^a $ * $sum_{b=0}^nbinom{n}{b}x^{n-b}$ is equal to $sum_{c=0}^{2n} sum_{a+n-b=c}binom{n}{a}binom{n}{b} x^c$ please
$endgroup$
– Salvattore
Jul 25 '14 at 4:59
$begingroup$
@Salvattore $sum_{a,b}binom{n}{a}binom{n}{b}x^{a+n-b}$, then collect all the coefficients of $x^c$ for fixed $c$ into $sum_{a+n-b=c}binom{n}{a}binom{n}{b}$ to get $sum_cleft[sum_{a+n-b=c}binom{n}{a}binom{n}{b}right]x^c$. If you want to work with generating functions, or even just plain polynomials, you need to be able to collect like terms, it is virtually a requirement.
$endgroup$
– anon
Jul 29 '14 at 17:23
add a comment |
$begingroup$
Since $dbinom n k= dbinom n {n-k}$, the identity
$$
sum_{k=0}^n binom n k ^2 = binom {2n} n
$$
is the same as
$$
sum_{k=0}^n binom n k binom n {n-k} = binom {2n} n.
$$
So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $dbinom n k cdot dbinom n {n-k}$ ways. The number of Democrats is in the set ${0,1,2,ldots,n}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.
$endgroup$
add a comment |
$begingroup$
Consider the graph underlying Pascal's triangle:
In this graph, the number at each node is a binomial coefficient and can also be thought of as the number of downward paths from the apex to that node.
The left side of the identity is the number of paths that start at the apex, go down to the $n$th row and return to the apex (let's call them round trips to $n$). By reflecting the return path about the $n$th row, we get a bijective correspondence between return trips to $n$ and paths from the apex to the central node of the $2n$th row. This is nothing but the central binomial coefficient $binom{2n}n$.
$endgroup$
add a comment |
$begingroup$
$newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
newcommand{dd}{{rm d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{fermi}{,{rm f}}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}
newcommand{pars}[1]{left(, #1 ,right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert, #1 ,rightvert}$
begin{align}
color{#66f}{largesum_{k = 0}^{n}{n choose k}^{2}}&=
sum_{k = 0}^{n}{n choose k}
oint_{verts{z} = 1}{pars{1 + z}^{n} over z^{k + 1}},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
sum_{k = 0}^{n}{n choose k}pars{1 over z}^{k},{dd z over 2piic}
\[5mm]&=oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
pars{1 + {1 over z}}^{n},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{2n} over z^{n + 1}},{dd z over 2piic}
\[5mm] & =color{#66f}{large{2n choose n}}
end{align}
$endgroup$
$begingroup$
Can we change integral and summation? What is the reason behind that ?
$endgroup$
– Siddhant Trivedi
Jan 4 '17 at 4:23
$begingroup$
@SiddhantTrivedi In this case, it's just a $finite$ sum.
$endgroup$
– Felix Marin
Jan 5 '17 at 22:27
add a comment |
$begingroup$
Okey this one is easy(if you seen this one once)
We have to show:
$${n choose 0}^2+{n choose 1}^2+cdots+{n choose n}^2={2n choose n} $$
Define a set A, $$A={a_1,ldots,a_n,a_{n+1},ldots,a_{2n}}$$ consisting of $2n$ - Elements. Now we declare $V$, is a set of $n$-sets of $A$. Obviously the cardinality of $V,$ $$|V|={2n choose n}.$$ Since one can choose $n$ Elements from $2n$ Elements in $${2n choose n}$$ ways.
Okey now we have the right side.
The for the left side you have give a disjunctive partition of the $V$ set. This should be done in the following way:
$V_i$ has exactly $i$-Elements from ${a_1,ldots,a_n}$, then the cardinality
$|V_i|={n choose i}{n choose n-i}={n choose i}{n choose i}={n choose i}^2$. Then with the Rule of Sum we have the left side. And we are done.
The Tricky Part ist to create the Partition to use the rule of sum.
$endgroup$
add a comment |
$begingroup$
Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are $${n+k-1choose k-1}$$ ways to do this. Alternatively, we can first give $0le ile n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, $${n+k-1choose k-1}=sum_{i=0}^n{n+k-2-ichoose k-2}$$, which simplifies to the desired result.
$endgroup$
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%2f148583%2fcombinatorial-proof-of-summation-of-sum-limits-k-0n-n-choose-k2-2n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that
$$(1+x)^n(x+1)^n=left(sum_{a=0}^nbinom{n}{a}x^aright)left(sum_{b=0}^nbinom{n}{b}x^{n-b}right)=sum_{c=0}^{2n}left(sum_{a+n-b=c}binom{n}{a}binom{n}{b}right)x^c$$
The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is
$$sum_{a+n-b=n}binom{n}{a}binom{n}{b}=sum_{a=0}^nbinom{n}{a}^2.$$
However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is
$$binom{2n}{n}. $$
Equating the two gives the result.
$endgroup$
$begingroup$
+1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion.
$endgroup$
– user17762
May 23 '12 at 5:12
$begingroup$
Can you explain me in more detail... why $sum_{a=0}^nbinom{n}{a}x^a $ * $sum_{b=0}^nbinom{n}{b}x^{n-b}$ is equal to $sum_{c=0}^{2n} sum_{a+n-b=c}binom{n}{a}binom{n}{b} x^c$ please
$endgroup$
– Salvattore
Jul 25 '14 at 4:59
$begingroup$
@Salvattore $sum_{a,b}binom{n}{a}binom{n}{b}x^{a+n-b}$, then collect all the coefficients of $x^c$ for fixed $c$ into $sum_{a+n-b=c}binom{n}{a}binom{n}{b}$ to get $sum_cleft[sum_{a+n-b=c}binom{n}{a}binom{n}{b}right]x^c$. If you want to work with generating functions, or even just plain polynomials, you need to be able to collect like terms, it is virtually a requirement.
$endgroup$
– anon
Jul 29 '14 at 17:23
add a comment |
$begingroup$
The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that
$$(1+x)^n(x+1)^n=left(sum_{a=0}^nbinom{n}{a}x^aright)left(sum_{b=0}^nbinom{n}{b}x^{n-b}right)=sum_{c=0}^{2n}left(sum_{a+n-b=c}binom{n}{a}binom{n}{b}right)x^c$$
The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is
$$sum_{a+n-b=n}binom{n}{a}binom{n}{b}=sum_{a=0}^nbinom{n}{a}^2.$$
However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is
$$binom{2n}{n}. $$
Equating the two gives the result.
$endgroup$
$begingroup$
+1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion.
$endgroup$
– user17762
May 23 '12 at 5:12
$begingroup$
Can you explain me in more detail... why $sum_{a=0}^nbinom{n}{a}x^a $ * $sum_{b=0}^nbinom{n}{b}x^{n-b}$ is equal to $sum_{c=0}^{2n} sum_{a+n-b=c}binom{n}{a}binom{n}{b} x^c$ please
$endgroup$
– Salvattore
Jul 25 '14 at 4:59
$begingroup$
@Salvattore $sum_{a,b}binom{n}{a}binom{n}{b}x^{a+n-b}$, then collect all the coefficients of $x^c$ for fixed $c$ into $sum_{a+n-b=c}binom{n}{a}binom{n}{b}$ to get $sum_cleft[sum_{a+n-b=c}binom{n}{a}binom{n}{b}right]x^c$. If you want to work with generating functions, or even just plain polynomials, you need to be able to collect like terms, it is virtually a requirement.
$endgroup$
– anon
Jul 29 '14 at 17:23
add a comment |
$begingroup$
The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that
$$(1+x)^n(x+1)^n=left(sum_{a=0}^nbinom{n}{a}x^aright)left(sum_{b=0}^nbinom{n}{b}x^{n-b}right)=sum_{c=0}^{2n}left(sum_{a+n-b=c}binom{n}{a}binom{n}{b}right)x^c$$
The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is
$$sum_{a+n-b=n}binom{n}{a}binom{n}{b}=sum_{a=0}^nbinom{n}{a}^2.$$
However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is
$$binom{2n}{n}. $$
Equating the two gives the result.
$endgroup$
The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that
$$(1+x)^n(x+1)^n=left(sum_{a=0}^nbinom{n}{a}x^aright)left(sum_{b=0}^nbinom{n}{b}x^{n-b}right)=sum_{c=0}^{2n}left(sum_{a+n-b=c}binom{n}{a}binom{n}{b}right)x^c$$
The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is
$$sum_{a+n-b=n}binom{n}{a}binom{n}{b}=sum_{a=0}^nbinom{n}{a}^2.$$
However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is
$$binom{2n}{n}. $$
Equating the two gives the result.
answered May 23 '12 at 5:07
anonanon
72k5110213
72k5110213
$begingroup$
+1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion.
$endgroup$
– user17762
May 23 '12 at 5:12
$begingroup$
Can you explain me in more detail... why $sum_{a=0}^nbinom{n}{a}x^a $ * $sum_{b=0}^nbinom{n}{b}x^{n-b}$ is equal to $sum_{c=0}^{2n} sum_{a+n-b=c}binom{n}{a}binom{n}{b} x^c$ please
$endgroup$
– Salvattore
Jul 25 '14 at 4:59
$begingroup$
@Salvattore $sum_{a,b}binom{n}{a}binom{n}{b}x^{a+n-b}$, then collect all the coefficients of $x^c$ for fixed $c$ into $sum_{a+n-b=c}binom{n}{a}binom{n}{b}$ to get $sum_cleft[sum_{a+n-b=c}binom{n}{a}binom{n}{b}right]x^c$. If you want to work with generating functions, or even just plain polynomials, you need to be able to collect like terms, it is virtually a requirement.
$endgroup$
– anon
Jul 29 '14 at 17:23
add a comment |
$begingroup$
+1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion.
$endgroup$
– user17762
May 23 '12 at 5:12
$begingroup$
Can you explain me in more detail... why $sum_{a=0}^nbinom{n}{a}x^a $ * $sum_{b=0}^nbinom{n}{b}x^{n-b}$ is equal to $sum_{c=0}^{2n} sum_{a+n-b=c}binom{n}{a}binom{n}{b} x^c$ please
$endgroup$
– Salvattore
Jul 25 '14 at 4:59
$begingroup$
@Salvattore $sum_{a,b}binom{n}{a}binom{n}{b}x^{a+n-b}$, then collect all the coefficients of $x^c$ for fixed $c$ into $sum_{a+n-b=c}binom{n}{a}binom{n}{b}$ to get $sum_cleft[sum_{a+n-b=c}binom{n}{a}binom{n}{b}right]x^c$. If you want to work with generating functions, or even just plain polynomials, you need to be able to collect like terms, it is virtually a requirement.
$endgroup$
– anon
Jul 29 '14 at 17:23
$begingroup$
+1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion.
$endgroup$
– user17762
May 23 '12 at 5:12
$begingroup$
+1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion.
$endgroup$
– user17762
May 23 '12 at 5:12
$begingroup$
Can you explain me in more detail... why $sum_{a=0}^nbinom{n}{a}x^a $ * $sum_{b=0}^nbinom{n}{b}x^{n-b}$ is equal to $sum_{c=0}^{2n} sum_{a+n-b=c}binom{n}{a}binom{n}{b} x^c$ please
$endgroup$
– Salvattore
Jul 25 '14 at 4:59
$begingroup$
Can you explain me in more detail... why $sum_{a=0}^nbinom{n}{a}x^a $ * $sum_{b=0}^nbinom{n}{b}x^{n-b}$ is equal to $sum_{c=0}^{2n} sum_{a+n-b=c}binom{n}{a}binom{n}{b} x^c$ please
$endgroup$
– Salvattore
Jul 25 '14 at 4:59
$begingroup$
@Salvattore $sum_{a,b}binom{n}{a}binom{n}{b}x^{a+n-b}$, then collect all the coefficients of $x^c$ for fixed $c$ into $sum_{a+n-b=c}binom{n}{a}binom{n}{b}$ to get $sum_cleft[sum_{a+n-b=c}binom{n}{a}binom{n}{b}right]x^c$. If you want to work with generating functions, or even just plain polynomials, you need to be able to collect like terms, it is virtually a requirement.
$endgroup$
– anon
Jul 29 '14 at 17:23
$begingroup$
@Salvattore $sum_{a,b}binom{n}{a}binom{n}{b}x^{a+n-b}$, then collect all the coefficients of $x^c$ for fixed $c$ into $sum_{a+n-b=c}binom{n}{a}binom{n}{b}$ to get $sum_cleft[sum_{a+n-b=c}binom{n}{a}binom{n}{b}right]x^c$. If you want to work with generating functions, or even just plain polynomials, you need to be able to collect like terms, it is virtually a requirement.
$endgroup$
– anon
Jul 29 '14 at 17:23
add a comment |
$begingroup$
Since $dbinom n k= dbinom n {n-k}$, the identity
$$
sum_{k=0}^n binom n k ^2 = binom {2n} n
$$
is the same as
$$
sum_{k=0}^n binom n k binom n {n-k} = binom {2n} n.
$$
So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $dbinom n k cdot dbinom n {n-k}$ ways. The number of Democrats is in the set ${0,1,2,ldots,n}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.
$endgroup$
add a comment |
$begingroup$
Since $dbinom n k= dbinom n {n-k}$, the identity
$$
sum_{k=0}^n binom n k ^2 = binom {2n} n
$$
is the same as
$$
sum_{k=0}^n binom n k binom n {n-k} = binom {2n} n.
$$
So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $dbinom n k cdot dbinom n {n-k}$ ways. The number of Democrats is in the set ${0,1,2,ldots,n}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.
$endgroup$
add a comment |
$begingroup$
Since $dbinom n k= dbinom n {n-k}$, the identity
$$
sum_{k=0}^n binom n k ^2 = binom {2n} n
$$
is the same as
$$
sum_{k=0}^n binom n k binom n {n-k} = binom {2n} n.
$$
So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $dbinom n k cdot dbinom n {n-k}$ ways. The number of Democrats is in the set ${0,1,2,ldots,n}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.
$endgroup$
Since $dbinom n k= dbinom n {n-k}$, the identity
$$
sum_{k=0}^n binom n k ^2 = binom {2n} n
$$
is the same as
$$
sum_{k=0}^n binom n k binom n {n-k} = binom {2n} n.
$$
So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $dbinom n k cdot dbinom n {n-k}$ ways. The number of Democrats is in the set ${0,1,2,ldots,n}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.
answered Dec 22 '14 at 22:05
Michael HardyMichael Hardy
1
1
add a comment |
add a comment |
$begingroup$
Consider the graph underlying Pascal's triangle:
In this graph, the number at each node is a binomial coefficient and can also be thought of as the number of downward paths from the apex to that node.
The left side of the identity is the number of paths that start at the apex, go down to the $n$th row and return to the apex (let's call them round trips to $n$). By reflecting the return path about the $n$th row, we get a bijective correspondence between return trips to $n$ and paths from the apex to the central node of the $2n$th row. This is nothing but the central binomial coefficient $binom{2n}n$.
$endgroup$
add a comment |
$begingroup$
Consider the graph underlying Pascal's triangle:
In this graph, the number at each node is a binomial coefficient and can also be thought of as the number of downward paths from the apex to that node.
The left side of the identity is the number of paths that start at the apex, go down to the $n$th row and return to the apex (let's call them round trips to $n$). By reflecting the return path about the $n$th row, we get a bijective correspondence between return trips to $n$ and paths from the apex to the central node of the $2n$th row. This is nothing but the central binomial coefficient $binom{2n}n$.
$endgroup$
add a comment |
$begingroup$
Consider the graph underlying Pascal's triangle:
In this graph, the number at each node is a binomial coefficient and can also be thought of as the number of downward paths from the apex to that node.
The left side of the identity is the number of paths that start at the apex, go down to the $n$th row and return to the apex (let's call them round trips to $n$). By reflecting the return path about the $n$th row, we get a bijective correspondence between return trips to $n$ and paths from the apex to the central node of the $2n$th row. This is nothing but the central binomial coefficient $binom{2n}n$.
$endgroup$
Consider the graph underlying Pascal's triangle:
In this graph, the number at each node is a binomial coefficient and can also be thought of as the number of downward paths from the apex to that node.
The left side of the identity is the number of paths that start at the apex, go down to the $n$th row and return to the apex (let's call them round trips to $n$). By reflecting the return path about the $n$th row, we get a bijective correspondence between return trips to $n$ and paths from the apex to the central node of the $2n$th row. This is nothing but the central binomial coefficient $binom{2n}n$.
answered Dec 16 '15 at 12:50
Amritanshu PrasadAmritanshu Prasad
1,0461013
1,0461013
add a comment |
add a comment |
$begingroup$
$newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
newcommand{dd}{{rm d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{fermi}{,{rm f}}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}
newcommand{pars}[1]{left(, #1 ,right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert, #1 ,rightvert}$
begin{align}
color{#66f}{largesum_{k = 0}^{n}{n choose k}^{2}}&=
sum_{k = 0}^{n}{n choose k}
oint_{verts{z} = 1}{pars{1 + z}^{n} over z^{k + 1}},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
sum_{k = 0}^{n}{n choose k}pars{1 over z}^{k},{dd z over 2piic}
\[5mm]&=oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
pars{1 + {1 over z}}^{n},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{2n} over z^{n + 1}},{dd z over 2piic}
\[5mm] & =color{#66f}{large{2n choose n}}
end{align}
$endgroup$
$begingroup$
Can we change integral and summation? What is the reason behind that ?
$endgroup$
– Siddhant Trivedi
Jan 4 '17 at 4:23
$begingroup$
@SiddhantTrivedi In this case, it's just a $finite$ sum.
$endgroup$
– Felix Marin
Jan 5 '17 at 22:27
add a comment |
$begingroup$
$newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
newcommand{dd}{{rm d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{fermi}{,{rm f}}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}
newcommand{pars}[1]{left(, #1 ,right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert, #1 ,rightvert}$
begin{align}
color{#66f}{largesum_{k = 0}^{n}{n choose k}^{2}}&=
sum_{k = 0}^{n}{n choose k}
oint_{verts{z} = 1}{pars{1 + z}^{n} over z^{k + 1}},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
sum_{k = 0}^{n}{n choose k}pars{1 over z}^{k},{dd z over 2piic}
\[5mm]&=oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
pars{1 + {1 over z}}^{n},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{2n} over z^{n + 1}},{dd z over 2piic}
\[5mm] & =color{#66f}{large{2n choose n}}
end{align}
$endgroup$
$begingroup$
Can we change integral and summation? What is the reason behind that ?
$endgroup$
– Siddhant Trivedi
Jan 4 '17 at 4:23
$begingroup$
@SiddhantTrivedi In this case, it's just a $finite$ sum.
$endgroup$
– Felix Marin
Jan 5 '17 at 22:27
add a comment |
$begingroup$
$newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
newcommand{dd}{{rm d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{fermi}{,{rm f}}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}
newcommand{pars}[1]{left(, #1 ,right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert, #1 ,rightvert}$
begin{align}
color{#66f}{largesum_{k = 0}^{n}{n choose k}^{2}}&=
sum_{k = 0}^{n}{n choose k}
oint_{verts{z} = 1}{pars{1 + z}^{n} over z^{k + 1}},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
sum_{k = 0}^{n}{n choose k}pars{1 over z}^{k},{dd z over 2piic}
\[5mm]&=oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
pars{1 + {1 over z}}^{n},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{2n} over z^{n + 1}},{dd z over 2piic}
\[5mm] & =color{#66f}{large{2n choose n}}
end{align}
$endgroup$
$newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
newcommand{dd}{{rm d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{fermi}{,{rm f}}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}
newcommand{pars}[1]{left(, #1 ,right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert, #1 ,rightvert}$
begin{align}
color{#66f}{largesum_{k = 0}^{n}{n choose k}^{2}}&=
sum_{k = 0}^{n}{n choose k}
oint_{verts{z} = 1}{pars{1 + z}^{n} over z^{k + 1}},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
sum_{k = 0}^{n}{n choose k}pars{1 over z}^{k},{dd z over 2piic}
\[5mm]&=oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
pars{1 + {1 over z}}^{n},{dd z over 2piic}
\[5mm] & =
oint_{verts{z} = 1}{pars{1 + z}^{2n} over z^{n + 1}},{dd z over 2piic}
\[5mm] & =color{#66f}{large{2n choose n}}
end{align}
edited Jan 6 at 19:48
answered Sep 27 '14 at 7:06
Felix MarinFelix Marin
67.5k7107141
67.5k7107141
$begingroup$
Can we change integral and summation? What is the reason behind that ?
$endgroup$
– Siddhant Trivedi
Jan 4 '17 at 4:23
$begingroup$
@SiddhantTrivedi In this case, it's just a $finite$ sum.
$endgroup$
– Felix Marin
Jan 5 '17 at 22:27
add a comment |
$begingroup$
Can we change integral and summation? What is the reason behind that ?
$endgroup$
– Siddhant Trivedi
Jan 4 '17 at 4:23
$begingroup$
@SiddhantTrivedi In this case, it's just a $finite$ sum.
$endgroup$
– Felix Marin
Jan 5 '17 at 22:27
$begingroup$
Can we change integral and summation? What is the reason behind that ?
$endgroup$
– Siddhant Trivedi
Jan 4 '17 at 4:23
$begingroup$
Can we change integral and summation? What is the reason behind that ?
$endgroup$
– Siddhant Trivedi
Jan 4 '17 at 4:23
$begingroup$
@SiddhantTrivedi In this case, it's just a $finite$ sum.
$endgroup$
– Felix Marin
Jan 5 '17 at 22:27
$begingroup$
@SiddhantTrivedi In this case, it's just a $finite$ sum.
$endgroup$
– Felix Marin
Jan 5 '17 at 22:27
add a comment |
$begingroup$
Okey this one is easy(if you seen this one once)
We have to show:
$${n choose 0}^2+{n choose 1}^2+cdots+{n choose n}^2={2n choose n} $$
Define a set A, $$A={a_1,ldots,a_n,a_{n+1},ldots,a_{2n}}$$ consisting of $2n$ - Elements. Now we declare $V$, is a set of $n$-sets of $A$. Obviously the cardinality of $V,$ $$|V|={2n choose n}.$$ Since one can choose $n$ Elements from $2n$ Elements in $${2n choose n}$$ ways.
Okey now we have the right side.
The for the left side you have give a disjunctive partition of the $V$ set. This should be done in the following way:
$V_i$ has exactly $i$-Elements from ${a_1,ldots,a_n}$, then the cardinality
$|V_i|={n choose i}{n choose n-i}={n choose i}{n choose i}={n choose i}^2$. Then with the Rule of Sum we have the left side. And we are done.
The Tricky Part ist to create the Partition to use the rule of sum.
$endgroup$
add a comment |
$begingroup$
Okey this one is easy(if you seen this one once)
We have to show:
$${n choose 0}^2+{n choose 1}^2+cdots+{n choose n}^2={2n choose n} $$
Define a set A, $$A={a_1,ldots,a_n,a_{n+1},ldots,a_{2n}}$$ consisting of $2n$ - Elements. Now we declare $V$, is a set of $n$-sets of $A$. Obviously the cardinality of $V,$ $$|V|={2n choose n}.$$ Since one can choose $n$ Elements from $2n$ Elements in $${2n choose n}$$ ways.
Okey now we have the right side.
The for the left side you have give a disjunctive partition of the $V$ set. This should be done in the following way:
$V_i$ has exactly $i$-Elements from ${a_1,ldots,a_n}$, then the cardinality
$|V_i|={n choose i}{n choose n-i}={n choose i}{n choose i}={n choose i}^2$. Then with the Rule of Sum we have the left side. And we are done.
The Tricky Part ist to create the Partition to use the rule of sum.
$endgroup$
add a comment |
$begingroup$
Okey this one is easy(if you seen this one once)
We have to show:
$${n choose 0}^2+{n choose 1}^2+cdots+{n choose n}^2={2n choose n} $$
Define a set A, $$A={a_1,ldots,a_n,a_{n+1},ldots,a_{2n}}$$ consisting of $2n$ - Elements. Now we declare $V$, is a set of $n$-sets of $A$. Obviously the cardinality of $V,$ $$|V|={2n choose n}.$$ Since one can choose $n$ Elements from $2n$ Elements in $${2n choose n}$$ ways.
Okey now we have the right side.
The for the left side you have give a disjunctive partition of the $V$ set. This should be done in the following way:
$V_i$ has exactly $i$-Elements from ${a_1,ldots,a_n}$, then the cardinality
$|V_i|={n choose i}{n choose n-i}={n choose i}{n choose i}={n choose i}^2$. Then with the Rule of Sum we have the left side. And we are done.
The Tricky Part ist to create the Partition to use the rule of sum.
$endgroup$
Okey this one is easy(if you seen this one once)
We have to show:
$${n choose 0}^2+{n choose 1}^2+cdots+{n choose n}^2={2n choose n} $$
Define a set A, $$A={a_1,ldots,a_n,a_{n+1},ldots,a_{2n}}$$ consisting of $2n$ - Elements. Now we declare $V$, is a set of $n$-sets of $A$. Obviously the cardinality of $V,$ $$|V|={2n choose n}.$$ Since one can choose $n$ Elements from $2n$ Elements in $${2n choose n}$$ ways.
Okey now we have the right side.
The for the left side you have give a disjunctive partition of the $V$ set. This should be done in the following way:
$V_i$ has exactly $i$-Elements from ${a_1,ldots,a_n}$, then the cardinality
$|V_i|={n choose i}{n choose n-i}={n choose i}{n choose i}={n choose i}^2$. Then with the Rule of Sum we have the left side. And we are done.
The Tricky Part ist to create the Partition to use the rule of sum.
edited Jul 10 '17 at 21:06
Michael Hardy
1
1
answered Jul 3 '17 at 17:27
thethathetha
268115
268115
add a comment |
add a comment |
$begingroup$
Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are $${n+k-1choose k-1}$$ ways to do this. Alternatively, we can first give $0le ile n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, $${n+k-1choose k-1}=sum_{i=0}^n{n+k-2-ichoose k-2}$$, which simplifies to the desired result.
$endgroup$
add a comment |
$begingroup$
Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are $${n+k-1choose k-1}$$ ways to do this. Alternatively, we can first give $0le ile n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, $${n+k-1choose k-1}=sum_{i=0}^n{n+k-2-ichoose k-2}$$, which simplifies to the desired result.
$endgroup$
add a comment |
$begingroup$
Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are $${n+k-1choose k-1}$$ ways to do this. Alternatively, we can first give $0le ile n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, $${n+k-1choose k-1}=sum_{i=0}^n{n+k-2-ichoose k-2}$$, which simplifies to the desired result.
$endgroup$
Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are $${n+k-1choose k-1}$$ ways to do this. Alternatively, we can first give $0le ile n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, $${n+k-1choose k-1}=sum_{i=0}^n{n+k-2-ichoose k-2}$$, which simplifies to the desired result.
answered Jan 16 '18 at 3:44
DigammaDigamma
6,1621440
6,1621440
add a comment |
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%2f148583%2fcombinatorial-proof-of-summation-of-sum-limits-k-0n-n-choose-k2-2n%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
16
$begingroup$
Just FYI, what you call a "logical proof" is known as a "combinatorial proof", and such a proof is perfectly valid and often very insightful. What I suspect you mean by "mathematical proof" is one dealing with the numerical structure of sums and combinations, which would be better called an "analytical proof". Both styles of proof are equally mathematical.
$endgroup$
– Austin Mohr
May 23 '12 at 4:57
6
$begingroup$
This is secretly subsumed by this question
$endgroup$
– davidlowryduda♦
May 23 '12 at 5:00
1
$begingroup$
You could obtain the same combinatorial proof by noting that $binom{2n}{n}$ counts the number of paths from $(0,0)$ to $(n,n)$ on an $ntimes n$ grid.
$endgroup$
– Holdsworth88
May 23 '12 at 6:03
7
$begingroup$
I think your combinatorial proof is really nice, and you should not be unhappy with it.
$endgroup$
– MJD
May 23 '12 at 13:54
2
$begingroup$
Incidentally, this is a special case of math.stackexchange.com/questions/337923/….
$endgroup$
– Greek - Area 51 Proposal
Nov 16 '13 at 10:26