Mixing
Solving number of subsets that meet the “spread out” condition using recurrence relation
$begingroup$
I'm trying to follow the solution shown here from (lulu):
Number of subsets that meet the "spread out" condition
Lulu then says in one of the comments that this can be solved as a recurrence relation and that the correct recurrence relation is:
$A_n = A_{n-1} + A_{n-3}$
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?
S={1,2,3} = $varnothing,{1},{2},{3}$ $A_3 = 4$
S={1,2,3,4} = $varnothing,{1},{2},{3},{4}, {4,1}$ $A_4 = 6$
S={1,2,3,4,5} = $varnothing,{1},{2},{3},{4},{5},{4,1},{5,1}, {5,2}$ $A_5 = 9$
S={1,2,3,4,5,6} = $varnothing,{1},{2},{3},{4},{5},{6},{4,1},{5,1},{5,2},{6,1},{6,2},{6,3} $ $A_6 = 13$
S={1,2,3,4,5,6,7} = $varnothing,{1},{2},{3},{4},{5},{6},{7}{4,1},{5,1},{5,2},{6,1},{6,2},{6,3},{7,1},{7,2},{7,3},{7,4} $ $A_7 = 18$
For $A_6$ the recursion works $A_6= A_5 + A_3$
However $A_7$ does not. Accorsong to the furmuls it shouyld be 19 but I can only find 18 valid combinations? Have I gone wrong?
combinatorics recurrence-relations
asked Jan 28 at 15:27
BazmanBazman
406413
$endgroup$
add a comment |
$begingroup$
I'm trying to follow the solution shown here from (lulu):
Number of subsets that meet the "spread out" condition
Lulu then says in one of the comments that this can be solved as a recurrence relation and that the correct recurrence relation is:
$A_n = A_{n-1} + A_{n-3}$
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?
S={1,2,3} = $varnothing,{1},{2},{3}$ $A_3 = 4$
S={1,2,3,4} = $varnothing,{1},{2},{3},{4}, {4,1}$ $A_4 = 6$
S={1,2,3,4,5} = $varnothing,{1},{2},{3},{4},{5},{4,1},{5,1}, {5,2}$ $A_5 = 9$
S={1,2,3,4,5,6} = $varnothing,{1},{2},{3},{4},{5},{6},{4,1},{5,1},{5,2},{6,1},{6,2},{6,3} $ $A_6 = 13$
S={1,2,3,4,5,6,7} = $varnothing,{1},{2},{3},{4},{5},{6},{7}{4,1},{5,1},{5,2},{6,1},{6,2},{6,3},{7,1},{7,2},{7,3},{7,4} $ $A_7 = 18$
For $A_6$ the recursion works $A_6= A_5 + A_3$
However $A_7$ does not. Accorsong to the furmuls it shouyld be 19 but I can only find 18 valid combinations? Have I gone wrong?
combinatorics recurrence-relations
asked Jan 28 at 15:27
BazmanBazman
406413
$endgroup$
1
$begingroup$
In the original problem, the empty set and singleton sets counted. So $A_3=4$, because the four valid subsets are $varnothing,{1},{2},{3}$.
$endgroup$
– Mike Earnest
Jan 28 at 17:40
$begingroup$
I thought that you hand to find all subsets where the difference between each the subset elements is more than 2. However, none of $varnothing,{1},{2},{3}$ matches that condition, what is the correct condition?
$endgroup$
– Bazman
Jan 28 at 17:51
1
$begingroup$
Think of it this way; a subset is only illegal if it has two distinct elements whose difference is at most $2$. But ${1}$ has no two distinct elements whose difference is at most $2$, so it is counted. Also, the original problem statement specifically said "Empty set and sets with only one element is counted in."
$endgroup$
– Mike Earnest
Jan 28 at 17:59
$begingroup$
Please see edited version of the equation above
$endgroup$
– Bazman
Jan 28 at 18:28
1
$begingroup$
For $A_7$, you are missing a single subset (it has three elements).
$endgroup$
– Mike Earnest
Jan 28 at 18:29
add a comment |
$begingroup$
I'm trying to follow the solution shown here from (lulu):
Number of subsets that meet the "spread out" condition
Lulu then says in one of the comments that this can be solved as a recurrence relation and that the correct recurrence relation is:
$A_n = A_{n-1} + A_{n-3}$
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?
S={1,2,3} = $varnothing,{1},{2},{3}$ $A_3 = 4$
S={1,2,3,4} = $varnothing,{1},{2},{3},{4}, {4,1}$ $A_4 = 6$
S={1,2,3,4,5} = $varnothing,{1},{2},{3},{4},{5},{4,1},{5,1}, {5,2}$ $A_5 = 9$
S={1,2,3,4,5,6} = $varnothing,{1},{2},{3},{4},{5},{6},{4,1},{5,1},{5,2},{6,1},{6,2},{6,3} $ $A_6 = 13$
S={1,2,3,4,5,6,7} = $varnothing,{1},{2},{3},{4},{5},{6},{7}{4,1},{5,1},{5,2},{6,1},{6,2},{6,3},{7,1},{7,2},{7,3},{7,4} $ $A_7 = 18$
For $A_6$ the recursion works $A_6= A_5 + A_3$
However $A_7$ does not. Accorsong to the furmuls it shouyld be 19 but I can only find 18 valid combinations? Have I gone wrong?
combinatorics recurrence-relations
asked Jan 28 at 15:27
BazmanBazman
406413
$endgroup$
I'm trying to follow the solution shown here from (lulu):
Number of subsets that meet the "spread out" condition
Lulu then says in one of the comments that this can be solved as a recurrence relation and that the correct recurrence relation is:
$A_n = A_{n-1} + A_{n-3}$
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?
S={1,2,3} = $varnothing,{1},{2},{3}$ $A_3 = 4$
S={1,2,3,4} = $varnothing,{1},{2},{3},{4}, {4,1}$ $A_4 = 6$
S={1,2,3,4,5} = $varnothing,{1},{2},{3},{4},{5},{4,1},{5,1}, {5,2}$ $A_5 = 9$
S={1,2,3,4,5,6} = $varnothing,{1},{2},{3},{4},{5},{6},{4,1},{5,1},{5,2},{6,1},{6,2},{6,3} $ $A_6 = 13$
S={1,2,3,4,5,6,7} = $varnothing,{1},{2},{3},{4},{5},{6},{7}{4,1},{5,1},{5,2},{6,1},{6,2},{6,3},{7,1},{7,2},{7,3},{7,4} $ $A_7 = 18$
For $A_6$ the recursion works $A_6= A_5 + A_3$
However $A_7$ does not. Accorsong to the furmuls it shouyld be 19 but I can only find 18 valid combinations? Have I gone wrong?
combinatorics recurrence-relations
combinatorics recurrence-relations
asked Jan 28 at 15:27
BazmanBazman
406413
asked Jan 28 at 15:27
BazmanBazman
406413
edited Jan 28 at 18:27
Bazman
asked Jan 28 at 15:27
BazmanBazman
406413
asked Jan 28 at 15:27
BazmanBazman
406413
asked Jan 28 at 15:27
BazmanBazman
406413
406413
1
$begingroup$
In the original problem, the empty set and singleton sets counted. So $A_3=4$, because the four valid subsets are $varnothing,{1},{2},{3}$.
$endgroup$
– Mike Earnest
Jan 28 at 17:40
$begingroup$
I thought that you hand to find all subsets where the difference between each the subset elements is more than 2. However, none of $varnothing,{1},{2},{3}$ matches that condition, what is the correct condition?
$endgroup$
– Bazman
Jan 28 at 17:51
1
$begingroup$
Think of it this way; a subset is only illegal if it has two distinct elements whose difference is at most $2$. But ${1}$ has no two distinct elements whose difference is at most $2$, so it is counted. Also, the original problem statement specifically said "Empty set and sets with only one element is counted in."
$endgroup$
– Mike Earnest
Jan 28 at 17:59
$begingroup$
Please see edited version of the equation above
$endgroup$
– Bazman
Jan 28 at 18:28
1
$begingroup$
For $A_7$, you are missing a single subset (it has three elements).
$endgroup$
– Mike Earnest
Jan 28 at 18:29
add a comment |
1
$begingroup$
In the original problem, the empty set and singleton sets counted. So $A_3=4$, because the four valid subsets are $varnothing,{1},{2},{3}$.
$endgroup$
– Mike Earnest
Jan 28 at 17:40
$begingroup$
I thought that you hand to find all subsets where the difference between each the subset elements is more than 2. However, none of $varnothing,{1},{2},{3}$ matches that condition, what is the correct condition?
$endgroup$
– Bazman
Jan 28 at 17:51
1
$begingroup$
Think of it this way; a subset is only illegal if it has two distinct elements whose difference is at most $2$. But ${1}$ has no two distinct elements whose difference is at most $2$, so it is counted. Also, the original problem statement specifically said "Empty set and sets with only one element is counted in."
$endgroup$
– Mike Earnest
Jan 28 at 17:59
$begingroup$
Please see edited version of the equation above
$endgroup$
– Bazman
Jan 28 at 18:28
1
$begingroup$
For $A_7$, you are missing a single subset (it has three elements).
$endgroup$
– Mike Earnest
Jan 28 at 18:29
1
1
$begingroup$
In the original problem, the empty set and singleton sets counted. So $A_3=4$, because the four valid subsets are $varnothing,{1},{2},{3}$.
$endgroup$
– Mike Earnest
Jan 28 at 17:40
$begingroup$
In the original problem, the empty set and singleton sets counted. So $A_3=4$, because the four valid subsets are $varnothing,{1},{2},{3}$.
$endgroup$
– Mike Earnest
Jan 28 at 17:40
$begingroup$
I thought that you hand to find all subsets where the difference between each the subset elements is more than 2. However, none of $varnothing,{1},{2},{3}$ matches that condition, what is the correct condition?
$endgroup$
– Bazman
Jan 28 at 17:51
$begingroup$
I thought that you hand to find all subsets where the difference between each the subset elements is more than 2. However, none of $varnothing,{1},{2},{3}$ matches that condition, what is the correct condition?
$endgroup$
– Bazman
Jan 28 at 17:51
1
1
$begingroup$
Think of it this way; a subset is only illegal if it has two distinct elements whose difference is at most $2$. But ${1}$ has no two distinct elements whose difference is at most $2$, so it is counted. Also, the original problem statement specifically said "Empty set and sets with only one element is counted in."
$endgroup$
– Mike Earnest
Jan 28 at 17:59
$begingroup$
Think of it this way; a subset is only illegal if it has two distinct elements whose difference is at most $2$. But ${1}$ has no two distinct elements whose difference is at most $2$, so it is counted. Also, the original problem statement specifically said "Empty set and sets with only one element is counted in."
$endgroup$
– Mike Earnest
Jan 28 at 17:59
$begingroup$
Please see edited version of the equation above
$endgroup$
– Bazman
Jan 28 at 18:28
$begingroup$
Please see edited version of the equation above
$endgroup$
– Bazman
Jan 28 at 18:28
1
1
$begingroup$
For $A_7$, you are missing a single subset (it has three elements).
$endgroup$
– Mike Earnest
Jan 28 at 18:29
$begingroup$
For $A_7$, you are missing a single subset (it has three elements).
$endgroup$
– Mike Earnest
Jan 28 at 18:29
add a comment |
0
active
oldest
votes
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
});
}
});
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%2f3091002%2fsolving-number-of-subsets-that-meet-the-spread-out-condition-using-recurrence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
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%2f3091002%2fsolving-number-of-subsets-that-meet-the-spread-out-condition-using-recurrence%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
1
$begingroup$
In the original problem, the empty set and singleton sets counted. So $A_3=4$, because the four valid subsets are $varnothing,{1},{2},{3}$.
$endgroup$
– Mike Earnest
Jan 28 at 17:40
$begingroup$
I thought that you hand to find all subsets where the difference between each the subset elements is more than 2. However, none of $varnothing,{1},{2},{3}$ matches that condition, what is the correct condition?
$endgroup$
– Bazman
Jan 28 at 17:51
1
$begingroup$
Think of it this way; a subset is only illegal if it has two distinct elements whose difference is at most $2$. But ${1}$ has no two distinct elements whose difference is at most $2$, so it is counted. Also, the original problem statement specifically said "Empty set and sets with only one element is counted in."
$endgroup$
– Mike Earnest
Jan 28 at 17:59
$begingroup$
Please see edited version of the equation above
$endgroup$
– Bazman
Jan 28 at 18:28
1
$begingroup$
For $A_7$, you are missing a single subset (it has three elements).
$endgroup$
– Mike Earnest
Jan 28 at 18:29