Help finding a combinatorial proof of ${kn choose 2}= k{n choose 2}+n^2{k choose 2}$ [closed]
$begingroup$
Hi I have been trying to find a way to find a combinatorial proof for ${kn choose 2}= k{n choose 2}+n^2{k choose 2}$.
combinatorics discrete-mathematics
asked Dec 6 '18 at 23:28
Lauren SmithLauren Smith
291
$endgroup$
closed as off-topic by RRL, jgon, KReiser, Cesareo, amWhy Jan 5 at 1:57
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – RRL, jgon, KReiser, Cesareo, amWhy
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Hi I have been trying to find a way to find a combinatorial proof for ${kn choose 2}= k{n choose 2}+n^2{k choose 2}$.
combinatorics discrete-mathematics
asked Dec 6 '18 at 23:28
Lauren SmithLauren Smith
291
$endgroup$
closed as off-topic by RRL, jgon, KReiser, Cesareo, amWhy Jan 5 at 1:57
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – RRL, jgon, KReiser, Cesareo, amWhy
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Hi I have been trying to find a way to find a combinatorial proof for ${kn choose 2}= k{n choose 2}+n^2{k choose 2}$.
combinatorics discrete-mathematics
asked Dec 6 '18 at 23:28
Lauren SmithLauren Smith
291
$endgroup$
Hi I have been trying to find a way to find a combinatorial proof for ${kn choose 2}= k{n choose 2}+n^2{k choose 2}$.
combinatorics discrete-mathematics
combinatorics discrete-mathematics
asked Dec 6 '18 at 23:28
Lauren SmithLauren Smith
291
asked Dec 6 '18 at 23:28
Lauren SmithLauren Smith
291
asked Dec 6 '18 at 23:28
Lauren SmithLauren Smith
291
asked Dec 6 '18 at 23:28
Lauren SmithLauren Smith
291
asked Dec 6 '18 at 23:28
Lauren SmithLauren Smith
291
291
closed as off-topic by RRL, jgon, KReiser, Cesareo, amWhy Jan 5 at 1:57
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – RRL, jgon, KReiser, Cesareo, amWhy
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by RRL, jgon, KReiser, Cesareo, amWhy Jan 5 at 1:57
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – RRL, jgon, KReiser, Cesareo, amWhy
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Hint: You want to pick $2$ elements out of $k$ buckets of $n$ elements each. You have two possible ways to do it: either you pick a bucket, and then you take $2$ elements from this bucket, or you pick $2$ buckets and then you choose one element from each of those $2$ buckets.
answered Dec 6 '18 at 23:30
Daniel Robert-NicoudDaniel Robert-Nicoud
20.4k33696
$endgroup$
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:38
add a comment |
$begingroup$
Consider a set of $kcdot n$ elements allocated in a grid with $n$ rows and $k$ columns then
- on the LHS we have the ways to choose $2$ elements among all of them
- on the RHS we have the cases with 2 elements choseen from a same row $k{n choose 2}$ and the cases 2 elements choseen from a same column $n{k choose 2}$ and the orther cases with $2$ elements chosen form different columns and rows $nk+(n-1)(k-1)$, indeed
$$k{n choose 2}+n{k choose 2}+nk+(n-1)(k-1)=k{n choose 2}+n^2{k choose 2}$$
answered Dec 6 '18 at 23:46
gimusigimusi
92.8k84494
$endgroup$
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:39
add a comment |
$begingroup$
As an addendum to Daniel Robert-Nicoud’s excellent hint, I find it helpful to rewrite the equality in the following way:
$$binom{kn}{2} = binom{k}{1}binom{n}{2} + binom{k}{2}binom{n}{1}binom{n}{1}.$$
By reading multiplication as “and then,” and addition as “or,” try to recover Daniel’s narrative by reading off the right-hand side.
With this thought process in mind, try to come up with a formula for $binom{nk}{3}$. Can you generalize this pattern?
answered Dec 7 '18 at 0:05
Santana AftonSantana Afton
2,6692629
$endgroup$
$begingroup$
Thank you so much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:37
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint: You want to pick $2$ elements out of $k$ buckets of $n$ elements each. You have two possible ways to do it: either you pick a bucket, and then you take $2$ elements from this bucket, or you pick $2$ buckets and then you choose one element from each of those $2$ buckets.
answered Dec 6 '18 at 23:30
Daniel Robert-NicoudDaniel Robert-Nicoud
20.4k33696
$endgroup$
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:38
add a comment |
$begingroup$
Hint: You want to pick $2$ elements out of $k$ buckets of $n$ elements each. You have two possible ways to do it: either you pick a bucket, and then you take $2$ elements from this bucket, or you pick $2$ buckets and then you choose one element from each of those $2$ buckets.
answered Dec 6 '18 at 23:30
Daniel Robert-NicoudDaniel Robert-Nicoud
20.4k33696
$endgroup$
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:38
add a comment |
$begingroup$
Hint: You want to pick $2$ elements out of $k$ buckets of $n$ elements each. You have two possible ways to do it: either you pick a bucket, and then you take $2$ elements from this bucket, or you pick $2$ buckets and then you choose one element from each of those $2$ buckets.
answered Dec 6 '18 at 23:30
Daniel Robert-NicoudDaniel Robert-Nicoud
20.4k33696
$endgroup$
Hint: You want to pick $2$ elements out of $k$ buckets of $n$ elements each. You have two possible ways to do it: either you pick a bucket, and then you take $2$ elements from this bucket, or you pick $2$ buckets and then you choose one element from each of those $2$ buckets.
answered Dec 6 '18 at 23:30
Daniel Robert-NicoudDaniel Robert-Nicoud
20.4k33696
answered Dec 6 '18 at 23:30
Daniel Robert-NicoudDaniel Robert-Nicoud
20.4k33696
answered Dec 6 '18 at 23:30
Daniel Robert-NicoudDaniel Robert-Nicoud
20.4k33696
answered Dec 6 '18 at 23:30
Daniel Robert-NicoudDaniel Robert-Nicoud
20.4k33696
20.4k33696
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:38
add a comment |
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:38
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:38
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:38
add a comment |
$begingroup$
Consider a set of $kcdot n$ elements allocated in a grid with $n$ rows and $k$ columns then
- on the LHS we have the ways to choose $2$ elements among all of them
- on the RHS we have the cases with 2 elements choseen from a same row $k{n choose 2}$ and the cases 2 elements choseen from a same column $n{k choose 2}$ and the orther cases with $2$ elements chosen form different columns and rows $nk+(n-1)(k-1)$, indeed
$$k{n choose 2}+n{k choose 2}+nk+(n-1)(k-1)=k{n choose 2}+n^2{k choose 2}$$
answered Dec 6 '18 at 23:46
gimusigimusi
92.8k84494
$endgroup$
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:39
add a comment |
$begingroup$
Consider a set of $kcdot n$ elements allocated in a grid with $n$ rows and $k$ columns then
- on the LHS we have the ways to choose $2$ elements among all of them
- on the RHS we have the cases with 2 elements choseen from a same row $k{n choose 2}$ and the cases 2 elements choseen from a same column $n{k choose 2}$ and the orther cases with $2$ elements chosen form different columns and rows $nk+(n-1)(k-1)$, indeed
$$k{n choose 2}+n{k choose 2}+nk+(n-1)(k-1)=k{n choose 2}+n^2{k choose 2}$$
answered Dec 6 '18 at 23:46
gimusigimusi
92.8k84494
$endgroup$
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:39
add a comment |
$begingroup$
Consider a set of $kcdot n$ elements allocated in a grid with $n$ rows and $k$ columns then
- on the LHS we have the ways to choose $2$ elements among all of them
- on the RHS we have the cases with 2 elements choseen from a same row $k{n choose 2}$ and the cases 2 elements choseen from a same column $n{k choose 2}$ and the orther cases with $2$ elements chosen form different columns and rows $nk+(n-1)(k-1)$, indeed
$$k{n choose 2}+n{k choose 2}+nk+(n-1)(k-1)=k{n choose 2}+n^2{k choose 2}$$
answered Dec 6 '18 at 23:46
gimusigimusi
92.8k84494
$endgroup$
Consider a set of $kcdot n$ elements allocated in a grid with $n$ rows and $k$ columns then
- on the LHS we have the ways to choose $2$ elements among all of them
- on the RHS we have the cases with 2 elements choseen from a same row $k{n choose 2}$ and the cases 2 elements choseen from a same column $n{k choose 2}$ and the orther cases with $2$ elements chosen form different columns and rows $nk+(n-1)(k-1)$, indeed
$$k{n choose 2}+n{k choose 2}+nk+(n-1)(k-1)=k{n choose 2}+n^2{k choose 2}$$
answered Dec 6 '18 at 23:46
gimusigimusi
92.8k84494
answered Dec 6 '18 at 23:46
gimusigimusi
92.8k84494
answered Dec 6 '18 at 23:46
gimusigimusi
92.8k84494
answered Dec 6 '18 at 23:46
gimusigimusi
92.8k84494
92.8k84494
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:39
add a comment |
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:39
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:39
$begingroup$
Thank you very much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:39
add a comment |
$begingroup$
As an addendum to Daniel Robert-Nicoud’s excellent hint, I find it helpful to rewrite the equality in the following way:
$$binom{kn}{2} = binom{k}{1}binom{n}{2} + binom{k}{2}binom{n}{1}binom{n}{1}.$$
By reading multiplication as “and then,” and addition as “or,” try to recover Daniel’s narrative by reading off the right-hand side.
With this thought process in mind, try to come up with a formula for $binom{nk}{3}$. Can you generalize this pattern?
answered Dec 7 '18 at 0:05
Santana AftonSantana Afton
2,6692629
$endgroup$
$begingroup$
Thank you so much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:37
add a comment |
$begingroup$
As an addendum to Daniel Robert-Nicoud’s excellent hint, I find it helpful to rewrite the equality in the following way:
$$binom{kn}{2} = binom{k}{1}binom{n}{2} + binom{k}{2}binom{n}{1}binom{n}{1}.$$
By reading multiplication as “and then,” and addition as “or,” try to recover Daniel’s narrative by reading off the right-hand side.
With this thought process in mind, try to come up with a formula for $binom{nk}{3}$. Can you generalize this pattern?
answered Dec 7 '18 at 0:05
Santana AftonSantana Afton
2,6692629
$endgroup$
$begingroup$
Thank you so much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:37
add a comment |
$begingroup$
As an addendum to Daniel Robert-Nicoud’s excellent hint, I find it helpful to rewrite the equality in the following way:
$$binom{kn}{2} = binom{k}{1}binom{n}{2} + binom{k}{2}binom{n}{1}binom{n}{1}.$$
By reading multiplication as “and then,” and addition as “or,” try to recover Daniel’s narrative by reading off the right-hand side.
With this thought process in mind, try to come up with a formula for $binom{nk}{3}$. Can you generalize this pattern?
answered Dec 7 '18 at 0:05
Santana AftonSantana Afton
2,6692629
$endgroup$
As an addendum to Daniel Robert-Nicoud’s excellent hint, I find it helpful to rewrite the equality in the following way:
$$binom{kn}{2} = binom{k}{1}binom{n}{2} + binom{k}{2}binom{n}{1}binom{n}{1}.$$
By reading multiplication as “and then,” and addition as “or,” try to recover Daniel’s narrative by reading off the right-hand side.
With this thought process in mind, try to come up with a formula for $binom{nk}{3}$. Can you generalize this pattern?
answered Dec 7 '18 at 0:05
Santana AftonSantana Afton
2,6692629
edited Dec 7 '18 at 0:21
answered Dec 7 '18 at 0:05
Santana AftonSantana Afton
2,6692629
answered Dec 7 '18 at 0:05
Santana AftonSantana Afton
2,6692629
answered Dec 7 '18 at 0:05
Santana AftonSantana Afton
2,6692629
2,6692629
$begingroup$
Thank you so much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:37
add a comment |
$begingroup$
Thank you so much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:37
$begingroup$
Thank you so much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:37
$begingroup$
Thank you so much. This was very helpful.
$endgroup$
– Lauren Smith
Dec 7 '18 at 7:37
add a comment |
