'selfish' set to be a set which has its own cardinality (number of elements) as an element
up vote
4
down vote
favorite
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
add a comment |
up vote
4
down vote
favorite
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
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
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
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
combinatorics discrete-mathematics
edited 55 mins ago
Kemono Chen
1,762332
1,762332
asked 1 hour ago
Suraj
898
898
add a comment |
add a comment |
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.
add a comment |
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).
add a comment |
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.
add a comment |
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.
add a comment |
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.
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.
answered 1 hour ago
Rakesh Bhatt
825113
825113
add a comment |
add a comment |
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).
add a comment |
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).
add a comment |
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).
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).
answered 1 hour ago
platty
2,830318
2,830318
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.
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.
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%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
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