Combinatorial proof that the number of even cardinality subsets is equal to the number of odd cardinality...
$begingroup$
Given a set of cardinality $ngeq 1$, the number of subsets of even cardinality is equal to the number of subsets of odd cardinality
I am looking for a combinatorial proof of this statement- I know an algebraic proof is easy, for instance by expanding $(1-1)^n$. If $n$ is odd it is easy to see there is a one-to-one correspondence between even-cardinality subsets an odd-cardinality subsets using the complement. However, I can't think of a combinatorial proof if $n$ is even. Any ideas?
combinatorial-proofs
asked Dec 19 '18 at 6:39
Darren OngDarren Ong
30219
$endgroup$
add a comment |
$begingroup$
Given a set of cardinality $ngeq 1$, the number of subsets of even cardinality is equal to the number of subsets of odd cardinality
I am looking for a combinatorial proof of this statement- I know an algebraic proof is easy, for instance by expanding $(1-1)^n$. If $n$ is odd it is easy to see there is a one-to-one correspondence between even-cardinality subsets an odd-cardinality subsets using the complement. However, I can't think of a combinatorial proof if $n$ is even. Any ideas?
combinatorial-proofs
asked Dec 19 '18 at 6:39
Darren OngDarren Ong
30219
$endgroup$
add a comment |
$begingroup$
Given a set of cardinality $ngeq 1$, the number of subsets of even cardinality is equal to the number of subsets of odd cardinality
I am looking for a combinatorial proof of this statement- I know an algebraic proof is easy, for instance by expanding $(1-1)^n$. If $n$ is odd it is easy to see there is a one-to-one correspondence between even-cardinality subsets an odd-cardinality subsets using the complement. However, I can't think of a combinatorial proof if $n$ is even. Any ideas?
combinatorial-proofs
asked Dec 19 '18 at 6:39
Darren OngDarren Ong
30219
$endgroup$
Given a set of cardinality $ngeq 1$, the number of subsets of even cardinality is equal to the number of subsets of odd cardinality
I am looking for a combinatorial proof of this statement- I know an algebraic proof is easy, for instance by expanding $(1-1)^n$. If $n$ is odd it is easy to see there is a one-to-one correspondence between even-cardinality subsets an odd-cardinality subsets using the complement. However, I can't think of a combinatorial proof if $n$ is even. Any ideas?
combinatorial-proofs
combinatorial-proofs
asked Dec 19 '18 at 6:39
Darren OngDarren Ong
30219
asked Dec 19 '18 at 6:39
Darren OngDarren Ong
30219
asked Dec 19 '18 at 6:39
Darren OngDarren Ong
30219
asked Dec 19 '18 at 6:39
Darren OngDarren Ong
30219
asked Dec 19 '18 at 6:39
Darren OngDarren Ong
30219
30219
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Just pick your favourite element $a$. Now take a subset $X$ and add $a$ if $anotin X$
and delete it if $ain X$. One gets a pairing of the subsets, and in each pair
one subset is even, the other odd.
answered Dec 19 '18 at 6:49
Lord Shark the UnknownLord Shark the Unknown
107k1162135
$endgroup$
add a comment |
$begingroup$
use the case for odd $n$, and consider adding a single additional element to the set. the old subsets are still subsets, together with new ones which contain the additional element.
answered Dec 19 '18 at 6:48
David HoldenDavid Holden
14.9k21225
$endgroup$
add a comment |
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%2f3046084%2fcombinatorial-proof-that-the-number-of-even-cardinality-subsets-is-equal-to-the%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Just pick your favourite element $a$. Now take a subset $X$ and add $a$ if $anotin X$
and delete it if $ain X$. One gets a pairing of the subsets, and in each pair
one subset is even, the other odd.
answered Dec 19 '18 at 6:49
Lord Shark the UnknownLord Shark the Unknown
107k1162135
$endgroup$
add a comment |
$begingroup$
Just pick your favourite element $a$. Now take a subset $X$ and add $a$ if $anotin X$
and delete it if $ain X$. One gets a pairing of the subsets, and in each pair
one subset is even, the other odd.
answered Dec 19 '18 at 6:49
Lord Shark the UnknownLord Shark the Unknown
107k1162135
$endgroup$
add a comment |
$begingroup$
Just pick your favourite element $a$. Now take a subset $X$ and add $a$ if $anotin X$
and delete it if $ain X$. One gets a pairing of the subsets, and in each pair
one subset is even, the other odd.
answered Dec 19 '18 at 6:49
Lord Shark the UnknownLord Shark the Unknown
107k1162135
$endgroup$
Just pick your favourite element $a$. Now take a subset $X$ and add $a$ if $anotin X$
and delete it if $ain X$. One gets a pairing of the subsets, and in each pair
one subset is even, the other odd.
answered Dec 19 '18 at 6:49
Lord Shark the UnknownLord Shark the Unknown
107k1162135
answered Dec 19 '18 at 6:49
Lord Shark the UnknownLord Shark the Unknown
107k1162135
answered Dec 19 '18 at 6:49
Lord Shark the UnknownLord Shark the Unknown
107k1162135
answered Dec 19 '18 at 6:49
Lord Shark the UnknownLord Shark the Unknown
107k1162135
107k1162135
add a comment |
add a comment |
$begingroup$
use the case for odd $n$, and consider adding a single additional element to the set. the old subsets are still subsets, together with new ones which contain the additional element.
answered Dec 19 '18 at 6:48
David HoldenDavid Holden
14.9k21225
$endgroup$
add a comment |
$begingroup$
use the case for odd $n$, and consider adding a single additional element to the set. the old subsets are still subsets, together with new ones which contain the additional element.
answered Dec 19 '18 at 6:48
David HoldenDavid Holden
14.9k21225
$endgroup$
add a comment |
$begingroup$
use the case for odd $n$, and consider adding a single additional element to the set. the old subsets are still subsets, together with new ones which contain the additional element.
answered Dec 19 '18 at 6:48
David HoldenDavid Holden
14.9k21225
$endgroup$
use the case for odd $n$, and consider adding a single additional element to the set. the old subsets are still subsets, together with new ones which contain the additional element.
answered Dec 19 '18 at 6:48
David HoldenDavid Holden
14.9k21225
answered Dec 19 '18 at 6:48
David HoldenDavid Holden
14.9k21225
answered Dec 19 '18 at 6:48
David HoldenDavid Holden
14.9k21225
answered Dec 19 '18 at 6:48
David HoldenDavid Holden
14.9k21225
14.9k21225
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%2f3046084%2fcombinatorial-proof-that-the-number-of-even-cardinality-subsets-is-equal-to-the%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
