'selfish' set to be a set which has its own cardinality (number of elements) as an element











up vote
4
down vote

favorite
1












Define a $textbf{selfish}$ set to be a set which has its own
cardinality (number of elements) as an element. Find, with proof, the
number of subsets of ${1, 2, ldots, n}$ which are textit{minimal}
selfish sets, that is, selfish sets none of whose proper subsets is selfish.



My Attempt.
Assume $textbf{A}$ to be a selfish set. If the cardinality of $textbf{A}$ is $c$, then can $textbf{A}$ contain $1,2,3....c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $textbf{A}$ gives a subset of k elements contradicting the fact that $textbf{A}$ is minimal selfish.
Thus $textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?










share|cite|improve this question




























    up vote
    4
    down vote

    favorite
    1












    Define a $textbf{selfish}$ set to be a set which has its own
    cardinality (number of elements) as an element. Find, with proof, the
    number of subsets of ${1, 2, ldots, n}$ which are textit{minimal}
    selfish sets, that is, selfish sets none of whose proper subsets is selfish.



    My Attempt.
    Assume $textbf{A}$ to be a selfish set. If the cardinality of $textbf{A}$ is $c$, then can $textbf{A}$ contain $1,2,3....c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $textbf{A}$ gives a subset of k elements contradicting the fact that $textbf{A}$ is minimal selfish.
    Thus $textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?










    share|cite|improve this question


























      up vote
      4
      down vote

      favorite
      1









      up vote
      4
      down vote

      favorite
      1






      1





      Define a $textbf{selfish}$ set to be a set which has its own
      cardinality (number of elements) as an element. Find, with proof, the
      number of subsets of ${1, 2, ldots, n}$ which are textit{minimal}
      selfish sets, that is, selfish sets none of whose proper subsets is selfish.



      My Attempt.
      Assume $textbf{A}$ to be a selfish set. If the cardinality of $textbf{A}$ is $c$, then can $textbf{A}$ contain $1,2,3....c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $textbf{A}$ gives a subset of k elements contradicting the fact that $textbf{A}$ is minimal selfish.
      Thus $textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?










      share|cite|improve this question















      Define a $textbf{selfish}$ set to be a set which has its own
      cardinality (number of elements) as an element. Find, with proof, the
      number of subsets of ${1, 2, ldots, n}$ which are textit{minimal}
      selfish sets, that is, selfish sets none of whose proper subsets is selfish.



      My Attempt.
      Assume $textbf{A}$ to be a selfish set. If the cardinality of $textbf{A}$ is $c$, then can $textbf{A}$ contain $1,2,3....c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $textbf{A}$ gives a subset of k elements contradicting the fact that $textbf{A}$ is minimal selfish.
      Thus $textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?







      combinatorics discrete-mathematics






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 1 hour ago









      Kemono Chen

      1,762332




      1,762332










      asked 1 hour ago









      Suraj

      898




      898






















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          4
          down vote



          accepted










          Your argument is correct.



          Lets see if recursion helps.



          Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
          number of minimal selfish subsets of $[n]$. Then the number of
          minimal selfish subsets of $[n]$ not containing $n$ is equal to
          $f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
          containing $n$, by subtracting 1 from each element, and then taking
          away the element $n-1$ from the set, we obtain a minimal selfish
          subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
          set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
          a minimal selfish subset of $[n]$ containing $n$ by the inverse
          procedure. Hence the number of minimal selfish subsets of $[n]$
          containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
          Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
          term of the Fibonacci sequence.






          share|cite|improve this answer




























            up vote
            0
            down vote













            Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.



            Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).






            share|cite|improve this answer





















              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',
              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%2f3030745%2fselfish-set-to-be-a-set-which-has-its-own-cardinality-number-of-elements-as%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








              up vote
              4
              down vote



              accepted










              Your argument is correct.



              Lets see if recursion helps.



              Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
              number of minimal selfish subsets of $[n]$. Then the number of
              minimal selfish subsets of $[n]$ not containing $n$ is equal to
              $f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
              containing $n$, by subtracting 1 from each element, and then taking
              away the element $n-1$ from the set, we obtain a minimal selfish
              subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
              set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
              a minimal selfish subset of $[n]$ containing $n$ by the inverse
              procedure. Hence the number of minimal selfish subsets of $[n]$
              containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
              Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
              term of the Fibonacci sequence.






              share|cite|improve this answer

























                up vote
                4
                down vote



                accepted










                Your argument is correct.



                Lets see if recursion helps.



                Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
                number of minimal selfish subsets of $[n]$. Then the number of
                minimal selfish subsets of $[n]$ not containing $n$ is equal to
                $f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
                containing $n$, by subtracting 1 from each element, and then taking
                away the element $n-1$ from the set, we obtain a minimal selfish
                subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
                set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
                a minimal selfish subset of $[n]$ containing $n$ by the inverse
                procedure. Hence the number of minimal selfish subsets of $[n]$
                containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
                Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
                term of the Fibonacci sequence.






                share|cite|improve this answer























                  up vote
                  4
                  down vote



                  accepted







                  up vote
                  4
                  down vote



                  accepted






                  Your argument is correct.



                  Lets see if recursion helps.



                  Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
                  number of minimal selfish subsets of $[n]$. Then the number of
                  minimal selfish subsets of $[n]$ not containing $n$ is equal to
                  $f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
                  containing $n$, by subtracting 1 from each element, and then taking
                  away the element $n-1$ from the set, we obtain a minimal selfish
                  subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
                  set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
                  a minimal selfish subset of $[n]$ containing $n$ by the inverse
                  procedure. Hence the number of minimal selfish subsets of $[n]$
                  containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
                  Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
                  term of the Fibonacci sequence.






                  share|cite|improve this answer












                  Your argument is correct.



                  Lets see if recursion helps.



                  Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
                  number of minimal selfish subsets of $[n]$. Then the number of
                  minimal selfish subsets of $[n]$ not containing $n$ is equal to
                  $f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
                  containing $n$, by subtracting 1 from each element, and then taking
                  away the element $n-1$ from the set, we obtain a minimal selfish
                  subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
                  set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
                  a minimal selfish subset of $[n]$ containing $n$ by the inverse
                  procedure. Hence the number of minimal selfish subsets of $[n]$
                  containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
                  Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
                  term of the Fibonacci sequence.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 1 hour ago









                  Rakesh Bhatt

                  825113




                  825113






















                      up vote
                      0
                      down vote













                      Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.



                      Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).






                      share|cite|improve this answer

























                        up vote
                        0
                        down vote













                        Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.



                        Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).






                        share|cite|improve this answer























                          up vote
                          0
                          down vote










                          up vote
                          0
                          down vote









                          Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.



                          Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).






                          share|cite|improve this answer












                          Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.



                          Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered 1 hour ago









                          platty

                          2,830318




                          2,830318






























                              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.





                              Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                              Please pay close attention to the following guidance:


                              • 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.


                              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%2f3030745%2fselfish-set-to-be-a-set-which-has-its-own-cardinality-number-of-elements-as%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

                              Costa Masnaga

                              Fotorealismo

                              Sidney Franklin