Number of subsets that meet the “spread out” condition

Multi tool use
Multi tool use

The name of the pictureThe name of the pictureThe name of the pictureClash 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




share|cite|improve this question






















  • 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














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




share|cite|improve this question






















  • 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












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




share|cite|improve this question














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





share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Aug 29 at 19:42

























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
















  • 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










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.






share|cite|improve this answer
















  • 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










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: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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%2f2895599%2fnumber-of-subsets-that-meet-the-spread-out-condition%23new-answer', 'question_page');

);

Post as a guest

















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.






share|cite|improve this answer
















  • 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














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.






share|cite|improve this answer
















  • 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












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.






share|cite|improve this answer












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.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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












  • 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

















 

draft saved


draft discarded















































 


draft saved


draft discarded














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
































































VzSoRj5uJ,D iS0ORG2cVNJvwSs,giH
-
dkHJ9iylQgI6Yea74Ar S,5rr,oLeE7JJAEgv j H,meqKET7,sYraFUTlc5S7VU8yrp,JZk

這個網誌中的熱門文章

How to combine Bézier curves to a surface?

圖片
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now. To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface? I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach? In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input. The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier cur...
閱讀完整內容

Propositional logic and tautologies

圖片
Clash Royale CLAN TAG #URR8PPP up vote 0 down vote favorite Taken from P. Suppes "Introduction to logic" pp16 Starting from the sentence "If $P$ tautologically implies $Q$, then.." Question: Is it true that, at least within propositional logic, we are able to prove only tautologies or do I mis-understand something? If yes, is propositional logic special in some way? Is the notion of tautology meaningful only in propositional logic? logic propositional-calculus share | cite | improve this question edited Nov 29 '17 at 18:53 Mauro ALLEGRANZA 60.8k 4 46 105 asked Nov 29 '17 at 16:32 Alvin Lepik 2,448 9 20 add a comment  |  up vote 0 down vote favorite Taken from P. Suppes "Introduction to logic" pp16 Starting from the sentence "If $P$ tautologically implies $Q$, then.." Question: Is it true that, at least within propositional logic, we are able to prove only tautologi...
閱讀完整內容

Distribution of Stopped Wiener Process with Stochastic Volatility

圖片
Clash Royale CLAN TAG #URR8PPP up vote 0 down vote favorite Let $(W_s)_s geq 0$ be a Wiener process and $tau$ be a random variable with an exponential distribution with parameter $lambda$. Suppose that $W$ and $tau$ are independent. In this question, we see that the distribution of the stopped Wiener process $W_tau$ corresponds to a Laplace distribution with scale parameter $fracsigmasqrt2lambda$ where $sigma$ is the instantaneous variance of the Wiener process. Suppose now, that the variance $sigma^2$ also follows a stochastic process such that we have: $$dS = sigma SdW_s \ dsigma^2 = alphasigma^2dt + xisigma^2dW_sigma$$ where $alpha$ and $xi$ are independent of $S$ and $dW_s$ and $dW_sigma$ are independent Wiener processes. My aim is to derive the distribution of $log S_tau$. First, if $barV_T$ denotes the mean variance over some time interval $[0,T]$ defined by $$barV_T = frac1T intlimits_0^Tsigma^2(t)dt,$$ it is easy to show (Lemma of Îto) that $$...
閱讀完整內容