Combinatorial proof $sum_{i=k}^n {i-1 choose k-1} = {n choose k}$ [duplicate]
$begingroup$
This question already has an answer here:
Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$
3 answers
Combinatorial Analysis: Fermat's Combinatorial Identity
1 answer
Could someone help me as I am stuck with coming up with a proof for this?
Assume n is the total number of people in a town. Assume k is the number of possible ways to select a chief of the town. So the RHS is saying that there are k ways to choose a chief from n people.
on the LHS, From $i=k$, and $k=n$, it is referring to from k to n, which is the sum of the remaining people in the town who were not selected $(n-k)$, that there is $k-1$ ways to choose from $i-1$ objects. Since $i=k$, i could be the number of ways to possibly select a chief. If one person is chosen from i, who also belongs to $k, k-1$. But how does this lead to $${n choose k}$$?
combinatorics discrete-mathematics permutations combinations
edited Dec 16 '18 at 15:25
Sik Feng Cheong
1579
asked Dec 16 '18 at 15:21
MunchiesOatsMunchiesOats
323
$endgroup$
marked as duplicate by Sil, N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 16 '18 at 16:03
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$
3 answers
Combinatorial Analysis: Fermat's Combinatorial Identity
1 answer
Could someone help me as I am stuck with coming up with a proof for this?
Assume n is the total number of people in a town. Assume k is the number of possible ways to select a chief of the town. So the RHS is saying that there are k ways to choose a chief from n people.
on the LHS, From $i=k$, and $k=n$, it is referring to from k to n, which is the sum of the remaining people in the town who were not selected $(n-k)$, that there is $k-1$ ways to choose from $i-1$ objects. Since $i=k$, i could be the number of ways to possibly select a chief. If one person is chosen from i, who also belongs to $k, k-1$. But how does this lead to $${n choose k}$$?
combinatorics discrete-mathematics permutations combinations
edited Dec 16 '18 at 15:25
Sik Feng Cheong
1579
asked Dec 16 '18 at 15:21
MunchiesOatsMunchiesOats
323
$endgroup$
marked as duplicate by Sil, N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 16 '18 at 16:03
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
Possible duplicate of Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$, and also Combinatorial Analysis: Fermat's Combinatorial Identity
$endgroup$
– Sil
Dec 16 '18 at 15:28
$begingroup$
The linked question may help you to obtain an answer, but I think an important prerequisite is to learn how to interpret combinatorial expressions properly. In the quantity $binom{n}{k}$, the number $k$ is the number being chosen, not the number of ways to choose. The very first thing you need to get straight is that $binom{n}{k}$ is the number of ways to choose $k$ items out of a set of $n$ items. In the problem of choosing a single chief from a town of $n$ people, the answer would be $binom{n}{1}$ or $n$.
$endgroup$
– Will Orrick
Dec 16 '18 at 16:18
add a comment |
$begingroup$
This question already has an answer here:
Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$
3 answers
Combinatorial Analysis: Fermat's Combinatorial Identity
1 answer
Could someone help me as I am stuck with coming up with a proof for this?
Assume n is the total number of people in a town. Assume k is the number of possible ways to select a chief of the town. So the RHS is saying that there are k ways to choose a chief from n people.
on the LHS, From $i=k$, and $k=n$, it is referring to from k to n, which is the sum of the remaining people in the town who were not selected $(n-k)$, that there is $k-1$ ways to choose from $i-1$ objects. Since $i=k$, i could be the number of ways to possibly select a chief. If one person is chosen from i, who also belongs to $k, k-1$. But how does this lead to $${n choose k}$$?
combinatorics discrete-mathematics permutations combinations
edited Dec 16 '18 at 15:25
Sik Feng Cheong
1579
asked Dec 16 '18 at 15:21
MunchiesOatsMunchiesOats
323
$endgroup$
This question already has an answer here:
Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$
3 answers
Combinatorial Analysis: Fermat's Combinatorial Identity
1 answer
Could someone help me as I am stuck with coming up with a proof for this?
Assume n is the total number of people in a town. Assume k is the number of possible ways to select a chief of the town. So the RHS is saying that there are k ways to choose a chief from n people.
on the LHS, From $i=k$, and $k=n$, it is referring to from k to n, which is the sum of the remaining people in the town who were not selected $(n-k)$, that there is $k-1$ ways to choose from $i-1$ objects. Since $i=k$, i could be the number of ways to possibly select a chief. If one person is chosen from i, who also belongs to $k, k-1$. But how does this lead to $${n choose k}$$?
This question already has an answer here:
Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$
3 answers
Combinatorial Analysis: Fermat's Combinatorial Identity
1 answer
combinatorics discrete-mathematics permutations combinations
combinatorics discrete-mathematics permutations combinations
edited Dec 16 '18 at 15:25
Sik Feng Cheong
1579
asked Dec 16 '18 at 15:21
MunchiesOatsMunchiesOats
323
edited Dec 16 '18 at 15:25
Sik Feng Cheong
1579
asked Dec 16 '18 at 15:21
MunchiesOatsMunchiesOats
323
edited Dec 16 '18 at 15:25
Sik Feng Cheong
1579
edited Dec 16 '18 at 15:25
Sik Feng Cheong
1579
edited Dec 16 '18 at 15:25
Sik Feng Cheong
1579
1579
asked Dec 16 '18 at 15:21
MunchiesOatsMunchiesOats
323
asked Dec 16 '18 at 15:21
MunchiesOatsMunchiesOats
323
asked Dec 16 '18 at 15:21
MunchiesOatsMunchiesOats
323
323
marked as duplicate by Sil, N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 16 '18 at 16:03
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Sil, N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 16 '18 at 16:03
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
Possible duplicate of Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$, and also Combinatorial Analysis: Fermat's Combinatorial Identity
$endgroup$
– Sil
Dec 16 '18 at 15:28
$begingroup$
The linked question may help you to obtain an answer, but I think an important prerequisite is to learn how to interpret combinatorial expressions properly. In the quantity $binom{n}{k}$, the number $k$ is the number being chosen, not the number of ways to choose. The very first thing you need to get straight is that $binom{n}{k}$ is the number of ways to choose $k$ items out of a set of $n$ items. In the problem of choosing a single chief from a town of $n$ people, the answer would be $binom{n}{1}$ or $n$.
$endgroup$
– Will Orrick
Dec 16 '18 at 16:18
add a comment |
1
$begingroup$
Possible duplicate of Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$, and also Combinatorial Analysis: Fermat's Combinatorial Identity
$endgroup$
– Sil
Dec 16 '18 at 15:28
$begingroup$
The linked question may help you to obtain an answer, but I think an important prerequisite is to learn how to interpret combinatorial expressions properly. In the quantity $binom{n}{k}$, the number $k$ is the number being chosen, not the number of ways to choose. The very first thing you need to get straight is that $binom{n}{k}$ is the number of ways to choose $k$ items out of a set of $n$ items. In the problem of choosing a single chief from a town of $n$ people, the answer would be $binom{n}{1}$ or $n$.
$endgroup$
– Will Orrick
Dec 16 '18 at 16:18
1
1
$begingroup$
Possible duplicate of Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$, and also Combinatorial Analysis: Fermat's Combinatorial Identity
$endgroup$
– Sil
Dec 16 '18 at 15:28
$begingroup$
Possible duplicate of Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$, and also Combinatorial Analysis: Fermat's Combinatorial Identity
$endgroup$
– Sil
Dec 16 '18 at 15:28
$begingroup$
The linked question may help you to obtain an answer, but I think an important prerequisite is to learn how to interpret combinatorial expressions properly. In the quantity $binom{n}{k}$, the number $k$ is the number being chosen, not the number of ways to choose. The very first thing you need to get straight is that $binom{n}{k}$ is the number of ways to choose $k$ items out of a set of $n$ items. In the problem of choosing a single chief from a town of $n$ people, the answer would be $binom{n}{1}$ or $n$.
$endgroup$
– Will Orrick
Dec 16 '18 at 16:18
$begingroup$
The linked question may help you to obtain an answer, but I think an important prerequisite is to learn how to interpret combinatorial expressions properly. In the quantity $binom{n}{k}$, the number $k$ is the number being chosen, not the number of ways to choose. The very first thing you need to get straight is that $binom{n}{k}$ is the number of ways to choose $k$ items out of a set of $n$ items. In the problem of choosing a single chief from a town of $n$ people, the answer would be $binom{n}{1}$ or $n$.
$endgroup$
– Will Orrick
Dec 16 '18 at 16:18
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint: Partition the set of all $k$-element subsets of $[n] = { 1, 2, dots, n }$ according to their greatest elements.
If you must use a 'real-world' example, consider putting the $n$ townfolk in order—say, by height—and counting the number of ways to choose a committee of $k$ people which will be chaired by the tallest person on the committee. The left-hand side partitions the set of all possible committees according to who will be the committee chair.
answered Dec 16 '18 at 15:27
Clive NewsteadClive Newstead
51.9k474136
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint: Partition the set of all $k$-element subsets of $[n] = { 1, 2, dots, n }$ according to their greatest elements.
If you must use a 'real-world' example, consider putting the $n$ townfolk in order—say, by height—and counting the number of ways to choose a committee of $k$ people which will be chaired by the tallest person on the committee. The left-hand side partitions the set of all possible committees according to who will be the committee chair.
answered Dec 16 '18 at 15:27
Clive NewsteadClive Newstead
51.9k474136
$endgroup$
add a comment |
$begingroup$
Hint: Partition the set of all $k$-element subsets of $[n] = { 1, 2, dots, n }$ according to their greatest elements.
If you must use a 'real-world' example, consider putting the $n$ townfolk in order—say, by height—and counting the number of ways to choose a committee of $k$ people which will be chaired by the tallest person on the committee. The left-hand side partitions the set of all possible committees according to who will be the committee chair.
answered Dec 16 '18 at 15:27
Clive NewsteadClive Newstead
51.9k474136
$endgroup$
add a comment |
$begingroup$
Hint: Partition the set of all $k$-element subsets of $[n] = { 1, 2, dots, n }$ according to their greatest elements.
If you must use a 'real-world' example, consider putting the $n$ townfolk in order—say, by height—and counting the number of ways to choose a committee of $k$ people which will be chaired by the tallest person on the committee. The left-hand side partitions the set of all possible committees according to who will be the committee chair.
answered Dec 16 '18 at 15:27
Clive NewsteadClive Newstead
51.9k474136
$endgroup$
Hint: Partition the set of all $k$-element subsets of $[n] = { 1, 2, dots, n }$ according to their greatest elements.
If you must use a 'real-world' example, consider putting the $n$ townfolk in order—say, by height—and counting the number of ways to choose a committee of $k$ people which will be chaired by the tallest person on the committee. The left-hand side partitions the set of all possible committees according to who will be the committee chair.
answered Dec 16 '18 at 15:27
Clive NewsteadClive Newstead
51.9k474136
answered Dec 16 '18 at 15:27
Clive NewsteadClive Newstead
51.9k474136
answered Dec 16 '18 at 15:27
Clive NewsteadClive Newstead
51.9k474136
answered Dec 16 '18 at 15:27
Clive NewsteadClive Newstead
51.9k474136
51.9k474136
add a comment |
add a comment |
1
$begingroup$
Possible duplicate of Prove ${n - 1 choose k - 1} + {n - 2 choose k - 1} + {n - 3 choose k - 1} + dots + {k - 1 choose k - 1} = {n choose k}$, and also Combinatorial Analysis: Fermat's Combinatorial Identity
$endgroup$
– Sil
Dec 16 '18 at 15:28
$begingroup$
The linked question may help you to obtain an answer, but I think an important prerequisite is to learn how to interpret combinatorial expressions properly. In the quantity $binom{n}{k}$, the number $k$ is the number being chosen, not the number of ways to choose. The very first thing you need to get straight is that $binom{n}{k}$ is the number of ways to choose $k$ items out of a set of $n$ items. In the problem of choosing a single chief from a town of $n$ people, the answer would be $binom{n}{1}$ or $n$.
$endgroup$
– Will Orrick
Dec 16 '18 at 16:18