Number of subsets that meet the “spread out†condition
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let $S = 1, 2,..., 12$, how many subsets of $S$ satisfy that the difference of any two number of the set is greater than $2$? Empty set and sets with only one element is counted in.
I am thinking of doing some partition and choosing numbers from each group. But it seems not to work. Any suggestion please? Thank you!
combinatorics
asked Aug 26 at 22:38
Edward Wang
661411
add a comment |Â
up vote
1
down vote
favorite
Let $S = 1, 2,..., 12$, how many subsets of $S$ satisfy that the difference of any two number of the set is greater than $2$? Empty set and sets with only one element is counted in.
I am thinking of doing some partition and choosing numbers from each group. But it seems not to work. Any suggestion please? Thank you!
combinatorics
asked Aug 26 at 22:38
Edward Wang
661411
How many such subsets are there (you can list and count them) for $S=1,2,3$? For $S=1,2,3,4$? And so on. Do you see a pattern in the answers? Does this suggest anything?
– Steve Kass
Aug 26 at 22:54
@SteveKass Oh I see! Thank you so much!
– Edward Wang
Aug 26 at 22:57
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let $S = 1, 2,..., 12$, how many subsets of $S$ satisfy that the difference of any two number of the set is greater than $2$? Empty set and sets with only one element is counted in.
I am thinking of doing some partition and choosing numbers from each group. But it seems not to work. Any suggestion please? Thank you!
combinatorics
asked Aug 26 at 22:38
Edward Wang
661411
Let $S = 1, 2,..., 12$, how many subsets of $S$ satisfy that the difference of any two number of the set is greater than $2$? Empty set and sets with only one element is counted in.
I am thinking of doing some partition and choosing numbers from each group. But it seems not to work. Any suggestion please? Thank you!
combinatorics
asked Aug 26 at 22:38
Edward Wang
661411
edited Aug 29 at 19:42
asked Aug 26 at 22:38
Edward Wang
661411
asked Aug 26 at 22:38
Edward Wang
661411
asked Aug 26 at 22:38
Edward Wang
661411
661411
How many such subsets are there (you can list and count them) for $S=1,2,3$? For $S=1,2,3,4$? And so on. Do you see a pattern in the answers? Does this suggest anything?
– Steve Kass
Aug 26 at 22:54
@SteveKass Oh I see! Thank you so much!
– Edward Wang
Aug 26 at 22:57
add a comment |Â
How many such subsets are there (you can list and count them) for $S=1,2,3$? For $S=1,2,3,4$? And so on. Do you see a pattern in the answers? Does this suggest anything?
– Steve Kass
Aug 26 at 22:54
@SteveKass Oh I see! Thank you so much!
– Edward Wang
Aug 26 at 22:57
How many such subsets are there (you can list and count them) for $S=1,2,3$? For $S=1,2,3,4$? And so on. Do you see a pattern in the answers? Does this suggest anything?
– Steve Kass
Aug 26 at 22:54
How many such subsets are there (you can list and count them) for $S=1,2,3$? For $S=1,2,3,4$? And so on. Do you see a pattern in the answers? Does this suggest anything?
– Steve Kass
Aug 26 at 22:54
@SteveKass Oh I see! Thank you so much!
– Edward Wang
Aug 26 at 22:57
@SteveKass Oh I see! Thank you so much!
– Edward Wang
Aug 26 at 22:57
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
The answer is in the form:
$$
1 + binom12-01 + binom12-22 + binom12-43+binom12-64
$$
Take $binom12-43$ as an example, we can think like this:
Assume we only have $8$ numbers, namely $1,2,3,4,5,6,7,8$, and we choose three numbers from them, such as $1,3,6$, we can always map it back to $1,3+2=5,6+2*2=10$, by adding the $2's$ back. This is one-to-one correspondence. Then we get the result in the end by adding them up.
answered Aug 26 at 23:45
Edward Wang
661411
4
This sort of problem lends itself to recursion. Let $A_n$ be the answer for the set $1,2,cdots, n$. (so you want $A_12$), We remark that either $n$ is in our subset or it isn't. If it is, then the rest of the subset must be an element of $A_n-3$. If it isn't then the subset must be an element of $A_n-1$. Thus $A_n=A_n-1+A_n-3$.
– lulu
Aug 27 at 0:05
@lulu Yeah thanks so much. Your approach is much simpler...
– Edward Wang
Aug 27 at 0:09
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
The answer is in the form:
$$
1 + binom12-01 + binom12-22 + binom12-43+binom12-64
$$
Take $binom12-43$ as an example, we can think like this:
Assume we only have $8$ numbers, namely $1,2,3,4,5,6,7,8$, and we choose three numbers from them, such as $1,3,6$, we can always map it back to $1,3+2=5,6+2*2=10$, by adding the $2's$ back. This is one-to-one correspondence. Then we get the result in the end by adding them up.
answered Aug 26 at 23:45
Edward Wang
661411
4
This sort of problem lends itself to recursion. Let $A_n$ be the answer for the set $1,2,cdots, n$. (so you want $A_12$), We remark that either $n$ is in our subset or it isn't. If it is, then the rest of the subset must be an element of $A_n-3$. If it isn't then the subset must be an element of $A_n-1$. Thus $A_n=A_n-1+A_n-3$.
– lulu
Aug 27 at 0:05
@lulu Yeah thanks so much. Your approach is much simpler...
– Edward Wang
Aug 27 at 0:09
add a comment |Â
up vote
1
down vote
accepted
The answer is in the form:
$$
1 + binom12-01 + binom12-22 + binom12-43+binom12-64
$$
Take $binom12-43$ as an example, we can think like this:
Assume we only have $8$ numbers, namely $1,2,3,4,5,6,7,8$, and we choose three numbers from them, such as $1,3,6$, we can always map it back to $1,3+2=5,6+2*2=10$, by adding the $2's$ back. This is one-to-one correspondence. Then we get the result in the end by adding them up.
answered Aug 26 at 23:45
Edward Wang
661411
4
This sort of problem lends itself to recursion. Let $A_n$ be the answer for the set $1,2,cdots, n$. (so you want $A_12$), We remark that either $n$ is in our subset or it isn't. If it is, then the rest of the subset must be an element of $A_n-3$. If it isn't then the subset must be an element of $A_n-1$. Thus $A_n=A_n-1+A_n-3$.
– lulu
Aug 27 at 0:05
@lulu Yeah thanks so much. Your approach is much simpler...
– Edward Wang
Aug 27 at 0:09
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
The answer is in the form:
$$
1 + binom12-01 + binom12-22 + binom12-43+binom12-64
$$
Take $binom12-43$ as an example, we can think like this:
Assume we only have $8$ numbers, namely $1,2,3,4,5,6,7,8$, and we choose three numbers from them, such as $1,3,6$, we can always map it back to $1,3+2=5,6+2*2=10$, by adding the $2's$ back. This is one-to-one correspondence. Then we get the result in the end by adding them up.
answered Aug 26 at 23:45
Edward Wang
661411
The answer is in the form:
$$
1 + binom12-01 + binom12-22 + binom12-43+binom12-64
$$
Take $binom12-43$ as an example, we can think like this:
Assume we only have $8$ numbers, namely $1,2,3,4,5,6,7,8$, and we choose three numbers from them, such as $1,3,6$, we can always map it back to $1,3+2=5,6+2*2=10$, by adding the $2's$ back. This is one-to-one correspondence. Then we get the result in the end by adding them up.
answered Aug 26 at 23:45
Edward Wang
661411
answered Aug 26 at 23:45
Edward Wang
661411
answered Aug 26 at 23:45
Edward Wang
661411
answered Aug 26 at 23:45
Edward Wang
661411
661411
4
This sort of problem lends itself to recursion. Let $A_n$ be the answer for the set $1,2,cdots, n$. (so you want $A_12$), We remark that either $n$ is in our subset or it isn't. If it is, then the rest of the subset must be an element of $A_n-3$. If it isn't then the subset must be an element of $A_n-1$. Thus $A_n=A_n-1+A_n-3$.
– lulu
Aug 27 at 0:05
@lulu Yeah thanks so much. Your approach is much simpler...
– Edward Wang
Aug 27 at 0:09
add a comment |Â
4
This sort of problem lends itself to recursion. Let $A_n$ be the answer for the set $1,2,cdots, n$. (so you want $A_12$), We remark that either $n$ is in our subset or it isn't. If it is, then the rest of the subset must be an element of $A_n-3$. If it isn't then the subset must be an element of $A_n-1$. Thus $A_n=A_n-1+A_n-3$.
– lulu
Aug 27 at 0:05
@lulu Yeah thanks so much. Your approach is much simpler...
– Edward Wang
Aug 27 at 0:09
4
4
This sort of problem lends itself to recursion. Let $A_n$ be the answer for the set $1,2,cdots, n$. (so you want $A_12$), We remark that either $n$ is in our subset or it isn't. If it is, then the rest of the subset must be an element of $A_n-3$. If it isn't then the subset must be an element of $A_n-1$. Thus $A_n=A_n-1+A_n-3$.
– lulu
Aug 27 at 0:05
This sort of problem lends itself to recursion. Let $A_n$ be the answer for the set $1,2,cdots, n$. (so you want $A_12$), We remark that either $n$ is in our subset or it isn't. If it is, then the rest of the subset must be an element of $A_n-3$. If it isn't then the subset must be an element of $A_n-1$. Thus $A_n=A_n-1+A_n-3$.
– lulu
Aug 27 at 0:05
@lulu Yeah thanks so much. Your approach is much simpler...
– Edward Wang
Aug 27 at 0:09
@lulu Yeah thanks so much. Your approach is much simpler...
– Edward Wang
Aug 27 at 0:09
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2895599%2fnumber-of-subsets-that-meet-the-spread-out-condition%23new-answer', 'question_page');
);
Post as a guest
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
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
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
How many such subsets are there (you can list and count them) for $S=1,2,3$? For $S=1,2,3,4$? And so on. Do you see a pattern in the answers? Does this suggest anything?
– Steve Kass
Aug 26 at 22:54
@SteveKass Oh I see! Thank you so much!
– Edward Wang
Aug 26 at 22:57