Subset counting for even numbers












2












$begingroup$


Let $S$ be a set of twelve integers ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$. How many subsets of $S$ are there such that the sum of all the elements in the subset is an odd number?



Here's what I tried. There are $2^{12}=4096$ ways to create a subset from $S$. I tried to find the number of what I call "even" subsets, or subsets whose elements only summed to even numbers. I divided $S$ into two subsets, one for all even numbers, and one for all odd numbers, knowing that all the subsets of those two subsets must have an even sum. Counting the sum and subtracting from $4096$, I get $2^{12}-2^6-2^6=3968$. However, now I realize that there are more ways to create "even" subsets, for example, two odds, four evens. I am now stuck. Can someone help?










share|cite|improve this question









$endgroup$












  • $begingroup$
    Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
    $endgroup$
    – Song
    7 mins ago










  • $begingroup$
    Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
    $endgroup$
    – Song
    6 mins ago
















2












$begingroup$


Let $S$ be a set of twelve integers ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$. How many subsets of $S$ are there such that the sum of all the elements in the subset is an odd number?



Here's what I tried. There are $2^{12}=4096$ ways to create a subset from $S$. I tried to find the number of what I call "even" subsets, or subsets whose elements only summed to even numbers. I divided $S$ into two subsets, one for all even numbers, and one for all odd numbers, knowing that all the subsets of those two subsets must have an even sum. Counting the sum and subtracting from $4096$, I get $2^{12}-2^6-2^6=3968$. However, now I realize that there are more ways to create "even" subsets, for example, two odds, four evens. I am now stuck. Can someone help?










share|cite|improve this question









$endgroup$












  • $begingroup$
    Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
    $endgroup$
    – Song
    7 mins ago










  • $begingroup$
    Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
    $endgroup$
    – Song
    6 mins ago














2












2








2





$begingroup$


Let $S$ be a set of twelve integers ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$. How many subsets of $S$ are there such that the sum of all the elements in the subset is an odd number?



Here's what I tried. There are $2^{12}=4096$ ways to create a subset from $S$. I tried to find the number of what I call "even" subsets, or subsets whose elements only summed to even numbers. I divided $S$ into two subsets, one for all even numbers, and one for all odd numbers, knowing that all the subsets of those two subsets must have an even sum. Counting the sum and subtracting from $4096$, I get $2^{12}-2^6-2^6=3968$. However, now I realize that there are more ways to create "even" subsets, for example, two odds, four evens. I am now stuck. Can someone help?










share|cite|improve this question









$endgroup$




Let $S$ be a set of twelve integers ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$. How many subsets of $S$ are there such that the sum of all the elements in the subset is an odd number?



Here's what I tried. There are $2^{12}=4096$ ways to create a subset from $S$. I tried to find the number of what I call "even" subsets, or subsets whose elements only summed to even numbers. I divided $S$ into two subsets, one for all even numbers, and one for all odd numbers, knowing that all the subsets of those two subsets must have an even sum. Counting the sum and subtracting from $4096$, I get $2^{12}-2^6-2^6=3968$. However, now I realize that there are more ways to create "even" subsets, for example, two odds, four evens. I am now stuck. Can someone help?







combinatorics number-theory elementary-set-theory






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 2 hours ago









A RA R

585




585












  • $begingroup$
    Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
    $endgroup$
    – Song
    7 mins ago










  • $begingroup$
    Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
    $endgroup$
    – Song
    6 mins ago


















  • $begingroup$
    Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
    $endgroup$
    – Song
    7 mins ago










  • $begingroup$
    Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
    $endgroup$
    – Song
    6 mins ago
















$begingroup$
Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
$endgroup$
– Song
7 mins ago




$begingroup$
Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
$endgroup$
– Song
7 mins ago












$begingroup$
Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
$endgroup$
– Song
6 mins ago




$begingroup$
Possible duplicate of How many non empty subsets of {1, 2, ..., n} satisfy that the sum of their elements is even?
$endgroup$
– Song
6 mins ago










4 Answers
4






active

oldest

votes


















6












$begingroup$

Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$



Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.



Apply the rule of product and conclude.




There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$






Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
    $endgroup$
    – A R
    2 hours ago





















2












$begingroup$

Hint:



If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.



This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.



Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.






share|cite|improve this answer









$endgroup$





















    1












    $begingroup$

    The credit for this strategy goes entirely to JMoravitz.



    What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.



    Thank you all so much for the help!






    share|cite|improve this answer









    $endgroup$





















      1












      $begingroup$

      The number of such subsets is half the number of all subsets of $S$, i.e. $frac{1}{2}cdot2^{12}=2^{11}$.



      Let $P_e(S)$ (respectively, $P_o(S)$) be the sets of subsets of $S$, where the sum of the elements is even (respectively, odd). Consider a map $f:P_e(S)to P_o(S)$ defined as follows: for a subset $Asubseteq S$ such that $Ain P_e(S)$, let
      $$
      f(A)=
      begin{cases}
      Asetminus{1}, &text{ if } 1in A,\
      Acup{1}, &text{ if } 1notin A.
      end{cases}
      $$

      In other words, if $1$ is in $A$, delete it; if $1$ is not in $A$, adjoin it.



      This changes the parity of the sum of elements of $A$, so $f(A)in P_o(S)$. Moveover, $f$ is a bijection since $f^{-1}=f$ (i.e. to undo $f$, apply $f$ again). Therefore, $P_e(S)$ or $P_o(S)$ have the same number of elements. But every subset of $S$ belongs to exactly one of $P_e(S)$ or $P_o(S)$, so each of $P_e(S)$ and $P_o(S)$ has half the total number of subsets of $S$, i.e. $2^{|S|-1}=2^{11}$.






      share|cite|improve this answer









      $endgroup$













        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
        });


        }
        });














        draft saved

        draft discarded


















        StackExchange.ready(
        function () {
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3145885%2fsubset-counting-for-even-numbers%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        4 Answers
        4






        active

        oldest

        votes








        4 Answers
        4






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        6












        $begingroup$

        Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$



        Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.



        Apply the rule of product and conclude.




        There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$






        Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.






        share|cite|improve this answer









        $endgroup$













        • $begingroup$
          That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
          $endgroup$
          – A R
          2 hours ago


















        6












        $begingroup$

        Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$



        Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.



        Apply the rule of product and conclude.




        There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$






        Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.






        share|cite|improve this answer









        $endgroup$













        • $begingroup$
          That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
          $endgroup$
          – A R
          2 hours ago
















        6












        6








        6





        $begingroup$

        Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$



        Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.



        Apply the rule of product and conclude.




        There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$






        Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.






        share|cite|improve this answer









        $endgroup$



        Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$



        Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.



        Apply the rule of product and conclude.




        There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$






        Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 2 hours ago









        JMoravitzJMoravitz

        48.5k33987




        48.5k33987












        • $begingroup$
          That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
          $endgroup$
          – A R
          2 hours ago




















        • $begingroup$
          That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
          $endgroup$
          – A R
          2 hours ago


















        $begingroup$
        That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
        $endgroup$
        – A R
        2 hours ago






        $begingroup$
        That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
        $endgroup$
        – A R
        2 hours ago













        2












        $begingroup$

        Hint:



        If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.



        This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.



        Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.






        share|cite|improve this answer









        $endgroup$


















          2












          $begingroup$

          Hint:



          If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.



          This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.



          Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.






          share|cite|improve this answer









          $endgroup$
















            2












            2








            2





            $begingroup$

            Hint:



            If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.



            This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.



            Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.






            share|cite|improve this answer









            $endgroup$



            Hint:



            If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.



            This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.



            Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered 2 hours ago









            Eevee TrainerEevee Trainer

            7,80621339




            7,80621339























                1












                $begingroup$

                The credit for this strategy goes entirely to JMoravitz.



                What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.



                Thank you all so much for the help!






                share|cite|improve this answer









                $endgroup$


















                  1












                  $begingroup$

                  The credit for this strategy goes entirely to JMoravitz.



                  What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.



                  Thank you all so much for the help!






                  share|cite|improve this answer









                  $endgroup$
















                    1












                    1








                    1





                    $begingroup$

                    The credit for this strategy goes entirely to JMoravitz.



                    What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.



                    Thank you all so much for the help!






                    share|cite|improve this answer









                    $endgroup$



                    The credit for this strategy goes entirely to JMoravitz.



                    What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.



                    Thank you all so much for the help!







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered 2 hours ago









                    A RA R

                    585




                    585























                        1












                        $begingroup$

                        The number of such subsets is half the number of all subsets of $S$, i.e. $frac{1}{2}cdot2^{12}=2^{11}$.



                        Let $P_e(S)$ (respectively, $P_o(S)$) be the sets of subsets of $S$, where the sum of the elements is even (respectively, odd). Consider a map $f:P_e(S)to P_o(S)$ defined as follows: for a subset $Asubseteq S$ such that $Ain P_e(S)$, let
                        $$
                        f(A)=
                        begin{cases}
                        Asetminus{1}, &text{ if } 1in A,\
                        Acup{1}, &text{ if } 1notin A.
                        end{cases}
                        $$

                        In other words, if $1$ is in $A$, delete it; if $1$ is not in $A$, adjoin it.



                        This changes the parity of the sum of elements of $A$, so $f(A)in P_o(S)$. Moveover, $f$ is a bijection since $f^{-1}=f$ (i.e. to undo $f$, apply $f$ again). Therefore, $P_e(S)$ or $P_o(S)$ have the same number of elements. But every subset of $S$ belongs to exactly one of $P_e(S)$ or $P_o(S)$, so each of $P_e(S)$ and $P_o(S)$ has half the total number of subsets of $S$, i.e. $2^{|S|-1}=2^{11}$.






                        share|cite|improve this answer









                        $endgroup$


















                          1












                          $begingroup$

                          The number of such subsets is half the number of all subsets of $S$, i.e. $frac{1}{2}cdot2^{12}=2^{11}$.



                          Let $P_e(S)$ (respectively, $P_o(S)$) be the sets of subsets of $S$, where the sum of the elements is even (respectively, odd). Consider a map $f:P_e(S)to P_o(S)$ defined as follows: for a subset $Asubseteq S$ such that $Ain P_e(S)$, let
                          $$
                          f(A)=
                          begin{cases}
                          Asetminus{1}, &text{ if } 1in A,\
                          Acup{1}, &text{ if } 1notin A.
                          end{cases}
                          $$

                          In other words, if $1$ is in $A$, delete it; if $1$ is not in $A$, adjoin it.



                          This changes the parity of the sum of elements of $A$, so $f(A)in P_o(S)$. Moveover, $f$ is a bijection since $f^{-1}=f$ (i.e. to undo $f$, apply $f$ again). Therefore, $P_e(S)$ or $P_o(S)$ have the same number of elements. But every subset of $S$ belongs to exactly one of $P_e(S)$ or $P_o(S)$, so each of $P_e(S)$ and $P_o(S)$ has half the total number of subsets of $S$, i.e. $2^{|S|-1}=2^{11}$.






                          share|cite|improve this answer









                          $endgroup$
















                            1












                            1








                            1





                            $begingroup$

                            The number of such subsets is half the number of all subsets of $S$, i.e. $frac{1}{2}cdot2^{12}=2^{11}$.



                            Let $P_e(S)$ (respectively, $P_o(S)$) be the sets of subsets of $S$, where the sum of the elements is even (respectively, odd). Consider a map $f:P_e(S)to P_o(S)$ defined as follows: for a subset $Asubseteq S$ such that $Ain P_e(S)$, let
                            $$
                            f(A)=
                            begin{cases}
                            Asetminus{1}, &text{ if } 1in A,\
                            Acup{1}, &text{ if } 1notin A.
                            end{cases}
                            $$

                            In other words, if $1$ is in $A$, delete it; if $1$ is not in $A$, adjoin it.



                            This changes the parity of the sum of elements of $A$, so $f(A)in P_o(S)$. Moveover, $f$ is a bijection since $f^{-1}=f$ (i.e. to undo $f$, apply $f$ again). Therefore, $P_e(S)$ or $P_o(S)$ have the same number of elements. But every subset of $S$ belongs to exactly one of $P_e(S)$ or $P_o(S)$, so each of $P_e(S)$ and $P_o(S)$ has half the total number of subsets of $S$, i.e. $2^{|S|-1}=2^{11}$.






                            share|cite|improve this answer









                            $endgroup$



                            The number of such subsets is half the number of all subsets of $S$, i.e. $frac{1}{2}cdot2^{12}=2^{11}$.



                            Let $P_e(S)$ (respectively, $P_o(S)$) be the sets of subsets of $S$, where the sum of the elements is even (respectively, odd). Consider a map $f:P_e(S)to P_o(S)$ defined as follows: for a subset $Asubseteq S$ such that $Ain P_e(S)$, let
                            $$
                            f(A)=
                            begin{cases}
                            Asetminus{1}, &text{ if } 1in A,\
                            Acup{1}, &text{ if } 1notin A.
                            end{cases}
                            $$

                            In other words, if $1$ is in $A$, delete it; if $1$ is not in $A$, adjoin it.



                            This changes the parity of the sum of elements of $A$, so $f(A)in P_o(S)$. Moveover, $f$ is a bijection since $f^{-1}=f$ (i.e. to undo $f$, apply $f$ again). Therefore, $P_e(S)$ or $P_o(S)$ have the same number of elements. But every subset of $S$ belongs to exactly one of $P_e(S)$ or $P_o(S)$, so each of $P_e(S)$ and $P_o(S)$ has half the total number of subsets of $S$, i.e. $2^{|S|-1}=2^{11}$.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered 2 hours ago









                            Alexander BursteinAlexander Burstein

                            1,194218




                            1,194218






























                                draft saved

                                draft discarded




















































                                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.




                                draft saved


                                draft discarded














                                StackExchange.ready(
                                function () {
                                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3145885%2fsubset-counting-for-even-numbers%23new-answer', 'question_page');
                                }
                                );

                                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







                                Popular posts from this blog

                                A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

                                Calculate evaluation metrics using cross_val_predict sklearn

                                Insert data from modal to MySQL (multiple modal on website)