Combinatorial proof of $binomnk2=kbinomn2+n^2binomk2$ The 2019 Stack Overflow Developer Survey Results Are InHow many permutations with this set of rows and columns?How to count matrices with rows and columns with an odd number of ones?How many ways are there to position two black rooks and two white rooks on an 8X8 chessboardGeneral solution for a combinatorial problemRussia (2000) contest:Prove the existence of a pair of rows and columns with intersections differently colouredCombinatorial identity $sumlimits_k=0^nfracn-kk+1binomnk^2 = binom2nn-1$Understanding the combinatorial argument for $binombinomn22 = 3 binomn+14$.ways to color black a $8*8$ square that all of the $1*1$ square that are in the same line or column with a $1*1$ black should be colored?Combinatorial proof that central binomial coefficients are the largest onesDiscrete Mathematics and Combinatorics, Combinatorial proof via counting dots
Star Trek - X-shaped Item on Regula/Orbital Office Starbases
Is it possible for absolutely everyone to attain enlightenment?
What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?
For what reasons would an animal species NOT cross a *horizontal* land bridge?
Can a rogue use sneak attack with weapons that have the thrown property even if they are not thrown?
Can there be female White Walkers?
How much of the clove should I use when using big garlic heads?
Straighten subgroup lattice
Is it okay to consider publishing in my first year of PhD?
Dropping list elements from nested list after evaluation
Geography at the pixel level
What is the motivation for a law requiring 2 parties to consent for recording a conversation
Why are there uneven bright areas in this photo of black hole?
What is this sharp, curved notch on my knife for?
Why does the nucleus not repel itself?
How can I define good in a religion that claims no moral authority?
Why “相同意思的词” is called “同义词” instead of "同意词"？
If a sorcerer casts the Banishment spell on a PC while in Avernus, does the PC return to their home plane?
Flight paths in orbit around Ceres?
What is the most efficient way to store a numeric range?
Slides for 30 min~1 hr Skype tenure track application interview
Why doesn't UInt have a toDouble()?
What is preventing me from simply constructing a hash that's lower than the current target?
Is it safe to harvest rainwater that fell on solar panels?
Combinatorial proof of $binomnk2=kbinomn2+n^2binomk2$
The 2019 Stack Overflow Developer Survey Results Are InHow many permutations with this set of rows and columns?How to count matrices with rows and columns with an odd number of ones?How many ways are there to position two black rooks and two white rooks on an 8X8 chessboardGeneral solution for a combinatorial problemRussia (2000) contest:Prove the existence of a pair of rows and columns with intersections differently colouredCombinatorial identity $sumlimits_k=0^nfracn-kk+1binomnk^2 = binom2nn-1$Understanding the combinatorial argument for $binombinomn22 = 3 binomn+14$.ways to color black a $8*8$ square that all of the $1*1$ square that are in the same line or column with a $1*1$ black should be colored?Combinatorial proof that central binomial coefficients are the largest onesDiscrete Mathematics and Combinatorics, Combinatorial proof via counting dots
$begingroup$
This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good example for future reference.
Also, there was just a flat-out wrong answer which had a couple of upvotes, so I thought to give my own possible proof and sort of 'reopen' the question that was left. Hopefully this time the question will have enough context to stay alive.
As a side note: the given right side does not appear symmetric between $k$ and $n$. However, when $binomm2=m(m-1)/2$ is inserted and the products expanded, only symmetric terms remain uncancelled. Rendering the right side as $k^2binomn2+nbinomk2$ would give the same cancellations and the same net value.
Proof
Suppose you have a grid of $ntimes k$ dots. Firstly, the amount of ways to connect any two dots is $binomnk2$. Now consider the right-hand side. We can split the cases for which the connected dots are on the same column, row, or are in both different columns and rows.
If the two connected dots are in the same column, we can choose two points from any two different rows in $binomn2$ ways, and we have $k$ columns for which the two points can be on the same column, which gives a total of $kbinomn2$ options. The same argument holds for constant rows: $nbinomk2$.
Now if neither the row nor the column can stay constant, we can pick any point in $nk$ ways, and choose the second point from the remaining $(n-1)(k-1)$ points; one column and one row will be unavailable. This gives us $fracnk(n-1)(k-1)2$ options, as we have to rule out the double counting.
We will now show (algebraically) that $nbinomk2+fracnk(n-1)(k-1)2=n^2binomk2$.
We have that $binomk2=frack(k-1)2 =fracnk(n-1)(k-1)2n(n-1) iff n(n-1)binomk2=fracnk(n-1)(k-1)2=n^2binomk2-nbinomk2$ which leads to the equation above.
Combining these cases gives $binomnk2=kbinomn2+nbinomk2+fracnk(n-1)(k-1)2 = kbinomn2+n^2binomk2$
If there are any mistakes or improvements on the arguments, please feel free to point them out.
combinatorics discrete-mathematics binomial-coefficients combinatorial-proofs
edited Mar 30 at 23:11
Oscar Lanzi
13.6k12136
asked Mar 30 at 21:45
MarcMarc
520211
$endgroup$
add a comment |
$begingroup$
This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good example for future reference.
Also, there was just a flat-out wrong answer which had a couple of upvotes, so I thought to give my own possible proof and sort of 'reopen' the question that was left. Hopefully this time the question will have enough context to stay alive.
As a side note: the given right side does not appear symmetric between $k$ and $n$. However, when $binomm2=m(m-1)/2$ is inserted and the products expanded, only symmetric terms remain uncancelled. Rendering the right side as $k^2binomn2+nbinomk2$ would give the same cancellations and the same net value.
Proof
Suppose you have a grid of $ntimes k$ dots. Firstly, the amount of ways to connect any two dots is $binomnk2$. Now consider the right-hand side. We can split the cases for which the connected dots are on the same column, row, or are in both different columns and rows.
If the two connected dots are in the same column, we can choose two points from any two different rows in $binomn2$ ways, and we have $k$ columns for which the two points can be on the same column, which gives a total of $kbinomn2$ options. The same argument holds for constant rows: $nbinomk2$.
Now if neither the row nor the column can stay constant, we can pick any point in $nk$ ways, and choose the second point from the remaining $(n-1)(k-1)$ points; one column and one row will be unavailable. This gives us $fracnk(n-1)(k-1)2$ options, as we have to rule out the double counting.
We will now show (algebraically) that $nbinomk2+fracnk(n-1)(k-1)2=n^2binomk2$.
We have that $binomk2=frack(k-1)2 =fracnk(n-1)(k-1)2n(n-1) iff n(n-1)binomk2=fracnk(n-1)(k-1)2=n^2binomk2-nbinomk2$ which leads to the equation above.
Combining these cases gives $binomnk2=kbinomn2+nbinomk2+fracnk(n-1)(k-1)2 = kbinomn2+n^2binomk2$
If there are any mistakes or improvements on the arguments, please feel free to point them out.
combinatorics discrete-mathematics binomial-coefficients combinatorial-proofs
edited Mar 30 at 23:11
Oscar Lanzi
13.6k12136
asked Mar 30 at 21:45
MarcMarc
520211
$endgroup$
$begingroup$
Uh ... How is the left side symmetric when $n$ and $k$ are interchanged and the right side isn't?
$endgroup$
– Oscar Lanzi
Mar 30 at 22:28
$begingroup$
@OscarLanzi The right side is symmetric too, just not obviously so.
$endgroup$
– Michael Biro
Mar 30 at 22:32
1
$begingroup$
I have now explained it. Feel free to roll back the edit if you feel it is inappropriate.
$endgroup$
– Oscar Lanzi
Mar 30 at 23:11
add a comment |
$begingroup$
This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good example for future reference.
Also, there was just a flat-out wrong answer which had a couple of upvotes, so I thought to give my own possible proof and sort of 'reopen' the question that was left. Hopefully this time the question will have enough context to stay alive.
As a side note: the given right side does not appear symmetric between $k$ and $n$. However, when $binomm2=m(m-1)/2$ is inserted and the products expanded, only symmetric terms remain uncancelled. Rendering the right side as $k^2binomn2+nbinomk2$ would give the same cancellations and the same net value.
Proof
Suppose you have a grid of $ntimes k$ dots. Firstly, the amount of ways to connect any two dots is $binomnk2$. Now consider the right-hand side. We can split the cases for which the connected dots are on the same column, row, or are in both different columns and rows.
If the two connected dots are in the same column, we can choose two points from any two different rows in $binomn2$ ways, and we have $k$ columns for which the two points can be on the same column, which gives a total of $kbinomn2$ options. The same argument holds for constant rows: $nbinomk2$.
Now if neither the row nor the column can stay constant, we can pick any point in $nk$ ways, and choose the second point from the remaining $(n-1)(k-1)$ points; one column and one row will be unavailable. This gives us $fracnk(n-1)(k-1)2$ options, as we have to rule out the double counting.
We will now show (algebraically) that $nbinomk2+fracnk(n-1)(k-1)2=n^2binomk2$.
We have that $binomk2=frack(k-1)2 =fracnk(n-1)(k-1)2n(n-1) iff n(n-1)binomk2=fracnk(n-1)(k-1)2=n^2binomk2-nbinomk2$ which leads to the equation above.
Combining these cases gives $binomnk2=kbinomn2+nbinomk2+fracnk(n-1)(k-1)2 = kbinomn2+n^2binomk2$
If there are any mistakes or improvements on the arguments, please feel free to point them out.
combinatorics discrete-mathematics binomial-coefficients combinatorial-proofs
edited Mar 30 at 23:11
Oscar Lanzi
13.6k12136
asked Mar 30 at 21:45
MarcMarc
520211
$endgroup$
This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good example for future reference.
Also, there was just a flat-out wrong answer which had a couple of upvotes, so I thought to give my own possible proof and sort of 'reopen' the question that was left. Hopefully this time the question will have enough context to stay alive.
As a side note: the given right side does not appear symmetric between $k$ and $n$. However, when $binomm2=m(m-1)/2$ is inserted and the products expanded, only symmetric terms remain uncancelled. Rendering the right side as $k^2binomn2+nbinomk2$ would give the same cancellations and the same net value.
Proof
Suppose you have a grid of $ntimes k$ dots. Firstly, the amount of ways to connect any two dots is $binomnk2$. Now consider the right-hand side. We can split the cases for which the connected dots are on the same column, row, or are in both different columns and rows.
If the two connected dots are in the same column, we can choose two points from any two different rows in $binomn2$ ways, and we have $k$ columns for which the two points can be on the same column, which gives a total of $kbinomn2$ options. The same argument holds for constant rows: $nbinomk2$.
Now if neither the row nor the column can stay constant, we can pick any point in $nk$ ways, and choose the second point from the remaining $(n-1)(k-1)$ points; one column and one row will be unavailable. This gives us $fracnk(n-1)(k-1)2$ options, as we have to rule out the double counting.
We will now show (algebraically) that $nbinomk2+fracnk(n-1)(k-1)2=n^2binomk2$.
We have that $binomk2=frack(k-1)2 =fracnk(n-1)(k-1)2n(n-1) iff n(n-1)binomk2=fracnk(n-1)(k-1)2=n^2binomk2-nbinomk2$ which leads to the equation above.
Combining these cases gives $binomnk2=kbinomn2+nbinomk2+fracnk(n-1)(k-1)2 = kbinomn2+n^2binomk2$
If there are any mistakes or improvements on the arguments, please feel free to point them out.
combinatorics discrete-mathematics binomial-coefficients combinatorial-proofs
combinatorics discrete-mathematics binomial-coefficients combinatorial-proofs
edited Mar 30 at 23:11
Oscar Lanzi
13.6k12136
asked Mar 30 at 21:45
MarcMarc
520211
edited Mar 30 at 23:11
Oscar Lanzi
13.6k12136
asked Mar 30 at 21:45
MarcMarc
520211
edited Mar 30 at 23:11
Oscar Lanzi
13.6k12136
edited Mar 30 at 23:11
Oscar Lanzi
13.6k12136
edited Mar 30 at 23:11
Oscar Lanzi
13.6k12136
13.6k12136
asked Mar 30 at 21:45
MarcMarc
520211
asked Mar 30 at 21:45
MarcMarc
520211
asked Mar 30 at 21:45
MarcMarc
520211
520211
$begingroup$
Uh ... How is the left side symmetric when $n$ and $k$ are interchanged and the right side isn't?
$endgroup$
– Oscar Lanzi
Mar 30 at 22:28
$begingroup$
@OscarLanzi The right side is symmetric too, just not obviously so.
$endgroup$
– Michael Biro
Mar 30 at 22:32
1
$begingroup$
I have now explained it. Feel free to roll back the edit if you feel it is inappropriate.
$endgroup$
– Oscar Lanzi
Mar 30 at 23:11
add a comment |
$begingroup$
Uh ... How is the left side symmetric when $n$ and $k$ are interchanged and the right side isn't?
$endgroup$
– Oscar Lanzi
Mar 30 at 22:28
$begingroup$
@OscarLanzi The right side is symmetric too, just not obviously so.
$endgroup$
– Michael Biro
Mar 30 at 22:32
1
$begingroup$
I have now explained it. Feel free to roll back the edit if you feel it is inappropriate.
$endgroup$
– Oscar Lanzi
Mar 30 at 23:11
$begingroup$
Uh ... How is the left side symmetric when $n$ and $k$ are interchanged and the right side isn't?
$endgroup$
– Oscar Lanzi
Mar 30 at 22:28
$begingroup$
Uh ... How is the left side symmetric when $n$ and $k$ are interchanged and the right side isn't?
$endgroup$
– Oscar Lanzi
Mar 30 at 22:28
$begingroup$
@OscarLanzi The right side is symmetric too, just not obviously so.
$endgroup$
– Michael Biro
Mar 30 at 22:32
$begingroup$
@OscarLanzi The right side is symmetric too, just not obviously so.
$endgroup$
– Michael Biro
Mar 30 at 22:32
1
1
$begingroup$
I have now explained it. Feel free to roll back the edit if you feel it is inappropriate.
$endgroup$
– Oscar Lanzi
Mar 30 at 23:11
$begingroup$
I have now explained it. Feel free to roll back the edit if you feel it is inappropriate.
$endgroup$
– Oscar Lanzi
Mar 30 at 23:11
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I don't think you need as many cases, which saves a little algebra. We have $k$ groups of $n$ dots each, so choosing two of them can be done in $binomnk2$ ways.
Alternatively, both are in the same group of $n$ which has $binomk1 cdot binomn2$ possibilities, or they are in different groups of $n$, which has $binomk2 binomn1^2$ possibilities.
Therefore, $binomnk2 = k binomn2 + n^2 binomk2$
answered Mar 30 at 22:24
Michael BiroMichael Biro
11.7k21831
$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%2f3168820%2fcombinatorial-proof-of-binomnk2-k-binomn2n2-binomk2%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I don't think you need as many cases, which saves a little algebra. We have $k$ groups of $n$ dots each, so choosing two of them can be done in $binomnk2$ ways.
Alternatively, both are in the same group of $n$ which has $binomk1 cdot binomn2$ possibilities, or they are in different groups of $n$, which has $binomk2 binomn1^2$ possibilities.
Therefore, $binomnk2 = k binomn2 + n^2 binomk2$
answered Mar 30 at 22:24
Michael BiroMichael Biro
11.7k21831
$endgroup$
add a comment |
$begingroup$
I don't think you need as many cases, which saves a little algebra. We have $k$ groups of $n$ dots each, so choosing two of them can be done in $binomnk2$ ways.
Alternatively, both are in the same group of $n$ which has $binomk1 cdot binomn2$ possibilities, or they are in different groups of $n$, which has $binomk2 binomn1^2$ possibilities.
Therefore, $binomnk2 = k binomn2 + n^2 binomk2$
answered Mar 30 at 22:24
Michael BiroMichael Biro
11.7k21831
$endgroup$
add a comment |
$begingroup$
I don't think you need as many cases, which saves a little algebra. We have $k$ groups of $n$ dots each, so choosing two of them can be done in $binomnk2$ ways.
Alternatively, both are in the same group of $n$ which has $binomk1 cdot binomn2$ possibilities, or they are in different groups of $n$, which has $binomk2 binomn1^2$ possibilities.
Therefore, $binomnk2 = k binomn2 + n^2 binomk2$
answered Mar 30 at 22:24
Michael BiroMichael Biro
11.7k21831
$endgroup$
I don't think you need as many cases, which saves a little algebra. We have $k$ groups of $n$ dots each, so choosing two of them can be done in $binomnk2$ ways.
Alternatively, both are in the same group of $n$ which has $binomk1 cdot binomn2$ possibilities, or they are in different groups of $n$, which has $binomk2 binomn1^2$ possibilities.
Therefore, $binomnk2 = k binomn2 + n^2 binomk2$
answered Mar 30 at 22:24
Michael BiroMichael Biro
11.7k21831
answered Mar 30 at 22:24
Michael BiroMichael Biro
11.7k21831
answered Mar 30 at 22:24
Michael BiroMichael Biro
11.7k21831
answered Mar 30 at 22:24
Michael BiroMichael Biro
11.7k21831
11.7k21831
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%2f3168820%2fcombinatorial-proof-of-binomnk2-k-binomn2n2-binomk2%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$
Uh ... How is the left side symmetric when $n$ and $k$ are interchanged and the right side isn't?
$endgroup$
– Oscar Lanzi
Mar 30 at 22:28
$begingroup$
@OscarLanzi The right side is symmetric too, just not obviously so.
$endgroup$
– Michael Biro
Mar 30 at 22:32
1
$begingroup$
I have now explained it. Feel free to roll back the edit if you feel it is inappropriate.
$endgroup$
– Oscar Lanzi
Mar 30 at 23:11