subset calculation with intervals
- Thread starter sazack21
- Start date
blamocur
Elite Member
- Joined
- Oct 30, 2021
- Messages
- 2,627
READ BEFORE POSTING
Welcome to FreeMathHelp.com! Please take the time to read the following before you make your first post. It will help you to get your math questions answered promptly and in the most helpful manner. A summary is available here, but please read the complete guidelines below at your earliest...
www.freemathhelp.com
Did I post in the wrong category? If so can you please advise on the correct category to post to?
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,087
If you "read before posting", you would know that this is not how the site works. Rather, we want you to explain (partially) how you did not arrive at the answer, so we can tell where you need help.
I would approach this by first thinking carefully about what it means. I think it means that there can be one pair of two consecutive integers, but no more, so that {1, 3, 19} and {1, 2, 19} are included, but not {1, 2, 3, 19} or {1, 2, 18, 19}, for example. Is that how you interpret it?
Then, if I didn't see a good way to create all such subsets, I might try actually listing them for a smaller containing set, like {1, 2, 3, 4, 5}, in order to better understand how it works, and to be able to try out methods and see if they missed or double-counted anything.
But when you tell us what you have tried, and any special methods you've been learning, we may have more to suggest.
Right, I interpreted the problem the same way where (1, 2, 5) would be a proper subset and (1, 2, 3) would not be. my main issue at this point is figuring out a formula or process to incorporate this into solving the problem. Do you have any idea how to specifically go about solving the equation,, besides simply creating a smaller container set, as I would still not know the best way to go about solving the problem?
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,087
I think you are using "proper subset" not with its proper definition, but to mean "the kind of subset you are to count".
My point was that this sort of problem is not a routine problem with an obvious method; you have to think creatively. I haven't put much time into thinking about it yet, because that is your job (and I don't want to be tempted to tell you all about a great method I discover).
As I asked before, what methods have you learned? Telling us such things (and therefore pondering your inventory of "tools" so that you might think of something helpful) can be very useful.
One method could be to break down the set you are counting into cases. How many subsets are there with no consecutive pairs? How many with exactly one? See if those are solvable. Or, you could try a subtractive method: Count all subsets, and subtract from them those that have any pairs, perhaps using the inclusion-exclusion principle. (I don't expect that to be a good method here, but don't want to exclude it.)
unfortunately, I am new to subset problem solving and interpretation. this isn't something I was taught but rather a question my friend asked me and needs help with, which is why I wanted to rationalize a relatively clear cut solution to him to arrive at the answer and to be able to explain to him the process. If you really have discovered a great way to solve the problem then I would greatly appreciate it if you could show me that method and application.
D
Deleted member 4993
Guest
Please advise your friend to communicate with this forum directly and share "friendly" work on this problem......
He doesn't have any work to show on the problem, as subset intervals are new to him as well. He was asked by a teacher in class to come up with an answer and explanation. he was told he is allowed to acquire the answer and work from anybody as long as he is able to explain the process afterwards. I owe him a favor and said I would search for an answer and the overall process. I have been doing research myself on the subject in terms of how to calculate the total number of subsets and identifying elements. the total number of subsets for a set of 1 through 20 would be 1,048,576, but I don't know and can't find information on how to calculate the total number of subsets that would be excluded given the parameters; subsets including 3 or more sequential numbers. Is there any advise that you could please give?
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,087
Then pass on our requests to your friend, if he is unable to connect with us himself. We need his context, such as what he is studying, in order to know what sort of suggestions to make. Don't imagine that you, knowing nothing of the subject, could teach someone else just by having seen an answer. (I can too easily imagine someone, hopefully not you, saying what you do as an excuse to get us to give a complete solution for his own test problem.)
I made it clear that I had not done much work; my words "I don't want to be tempted to tell you all about a great method I discover" (not "have discovered) refer to the possible future, not the past or present!
But I'm working on it as I have time, and I want to reemphasize what I said about trying smaller problems, and about partitioning the problem into two cases. This was not a worthless suggestion, but a genuine method!
Working on the "no consecutive pairs" case, and making a list of values for S_n for small n, where S_n means the number of subsets of a set of n numbers with no consecutive pairs) reveals a nice pattern and a possible proof. This will be most useful to someone who knows about recursive sequences or inductive proof. I think the other case will require just a small modification.
That is all the hint I will give before seeing someone's attempt, either you or your (presumably real) friend.
pka
Elite Member
- Joined
- Jan 29, 2005
- Messages
- 11,971
If we take only the odd numbers in that set [imath]\mathcal{O}=\{1,3,5,\cdots,17,19\}[/imath] there [imath]2^{10}-1[/imath] non-empty subsets with no two consecutive integers. Likewise if we take only the even numbers in that set [imath]\mathcal{E}=\{2,4,6\cdots,18,20\}[/imath] there are [imath]2^{10}-1[/imath] non-empty subsets with no two consecutive integers.
But beyond that point it becomes tedious to count. EX. the set [imath]\{5,6,7\}[/imath] has [imath]7[/imath] non-empty subsets three of which contain consecutive integers.
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,087
Just for everyone's information, I have now solved it (I think!) using these ideas; the answer I got is related to the Fibonacci sequence, which suggests that something like my approach may be what's expected, not what you'd normally think of as combinatorics in the restricted sense. On the other hand, Fibonacci can be expressed in terms of combinations!
I very much want to know what course (or other source) the question comes from. It's quite nice.
Cubist
Senior Member
- Joined
- Oct 29, 2019
- Messages
- 1,666
A different thread concerning recursion reminded me of this problem. And since this thread is over a month old now then we can more openly discuss the answer.
For the "no consecutive pairs" case I found a Fibonacci like recursive formula f(n) that gives...
For the case of, "no more than 2 consecutive integers" in the original question it's possible to use a summation over all the possible consecutive pairs - using f(x) to determine the combinations both lower and higher. Add to this the result for no consecutive pairs f(n) and I obtain...
@Dr.Peterson was this the method that you used, or did you find a recursive relation for this too? (Perhaps you don't remember because it was a long time ago)
I haven't given my solution, nor the answer for n=20, just in case anyone else would like to look into this problem as a puzzle.
For the "no consecutive pairs" case I found a Fibonacci like recursive formula f(n) that gives...
Code:
n f(n)
--------
1 1
2 2
3 4
4 7
5 12
6 20
7 33
8 54
9 88
10 143For the case of, "no more than 2 consecutive integers" in the original question it's possible to use a summation over all the possible consecutive pairs - using f(x) to determine the combinations both lower and higher. Add to this the result for no consecutive pairs f(n) and I obtain...
Code:
1 1
2 3
3 6
4 12
5 22
6 40
7 71
8 125
9 218
10 378I haven't given my solution, nor the answer for n=20, just in case anyone else would like to look into this problem as a puzzle.
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,087
Are you not counting the empty set in your f(n)?
Unless I'm missing something as I look at it this time, I get something even more "Fibonacci-like" than yours.
I'll have to look through my notes and see if I have the answer for the second case, or reconstruct it. I think I recall it being a simple recursion.
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,087
For no consecutive integers, I get:
n=0, subsets of {}: {}, so [imath]S_0=1[/imath]
n=1, subsets of {1}: {}, {1} so [imath]S_1=2[/imath]
n=2, subsets of {1,2}: {}, {1}, {2} so [imath]S_2=3[/imath]
n=3, subsets of {1,2,3}: {}, {1}, {2}, {3}, {1,3} so [imath]S_3=5[/imath]
n=4, subsets of {1,2,3,4}: {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4} so [imath]S_4= 8[/imath]
For a given n, we can use any of the subsets in [imath]S_{n-1}[/imath], together with any of the subsets is [imath]S_{n-2}[/imath] together with n. For example, the subsets for n=4 are {}, {1}, {2}, {3}, {1,3} together with {4}, {1,4}, {2,4}. So the recursion is [imath]S_{n} = S_{n-1} + S_{n-2}[/imath], and is the Fibonacci sequence, offset.
If you don't count empty subsets, then your answer is correct (1 less than Fibonacci).
n=0, subsets of {}: {}, so [imath]S_0=1[/imath]
n=1, subsets of {1}: {}, {1} so [imath]S_1=2[/imath]
n=2, subsets of {1,2}: {}, {1}, {2} so [imath]S_2=3[/imath]
n=3, subsets of {1,2,3}: {}, {1}, {2}, {3}, {1,3} so [imath]S_3=5[/imath]
n=4, subsets of {1,2,3,4}: {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4} so [imath]S_4= 8[/imath]
For a given n, we can use any of the subsets in [imath]S_{n-1}[/imath], together with any of the subsets is [imath]S_{n-2}[/imath] together with n. For example, the subsets for n=4 are {}, {1}, {2}, {3}, {1,3} together with {4}, {1,4}, {2,4}. So the recursion is [imath]S_{n} = S_{n-1} + S_{n-2}[/imath], and is the Fibonacci sequence, offset.
If you don't count empty subsets, then your answer is correct (1 less than Fibonacci).
I haven't found notes from my original work, so I have to think about it again (I haven't had much time yet). I've got a candidate that doesn't involve a summation, but need to check and improve it.
Cubist
Senior Member
- Joined
- Oct 29, 2019
- Messages
- 1,666
Your "no consecutive integers" solution is much better than mine! Using this in the summation of post#17 gives...
[math]
F_{n+2} + \sum_{i=1}^{n-1}\left( \, F_i \times F_{n-i} \, \right)
[/math]Fn is the nth Fibonacci number. This looks much nicer. And results now count the empty set (giving one more than post#17's expression).
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,087
I finally worked it out again. One thing I've recalled is that I used a different representation. A subset of the set of numbers from 1 to n can be seen as a set of n check boxes, some of which we mark. For example, here is one set with no consecutive pairs, for n=5: _ x _ _ x.
Now, if we had a list of all no-pair subsets for a given n, we could use that to list subsets with exactly one pair of consecutive numbers: Just replace one x with xx, and you have a one-pair subset for n+1. Taking my example, we get (for n=6) _ x x _ _ x and _ x _ _ x x. Unfortunately, the number of one-pair subsets derived from a given no-pair subset depend on the number of elements in the latter, so this doesn't do what I hoped.
Any one-pair subset of the n-element set will end either in "_" (in which case there are [imath]T_{n-1}[/imath] ways to make the rest, which must include one pair); or in "_x" ([imath]T_{n-2}[/imath] ways); or in "xx" ([imath]S_{n-3}[/imath] ways, which must not include a pair). So [math]S_n=T_{n-1}+T_{n-2}+S_{n-3}[/math]
This produces the results you showed (when I add 1 for the empty set). Letting [imath]U_n=\S_n+T_n[/imath], I get
This can probably be improved, possibly to a single recursion for U.
Now, if we had a list of all no-pair subsets for a given n, we could use that to list subsets with exactly one pair of consecutive numbers: Just replace one x with xx, and you have a one-pair subset for n+1. Taking my example, we get (for n=6) _ x x _ _ x and _ x _ _ x x. Unfortunately, the number of one-pair subsets derived from a given no-pair subset depend on the number of elements in the latter, so this doesn't do what I hoped.
Any one-pair subset of the n-element set will end either in "_" (in which case there are [imath]T_{n-1}[/imath] ways to make the rest, which must include one pair); or in "_x" ([imath]T_{n-2}[/imath] ways); or in "xx" ([imath]S_{n-3}[/imath] ways, which must not include a pair). So [math]S_n=T_{n-1}+T_{n-2}+S_{n-3}[/math]
This produces the results you showed (when I add 1 for the empty set). Letting [imath]U_n=\S_n+T_n[/imath], I get
n | S | T | U |
0 | 1 | 0 | 1 |
1 | 2 | 0 | 2 |
2 | 3 | 1 | 4 |
3 | 5 | 2 | 7 |
4 | 8 | 5 | 13 |
5 | 13 | 10 | 23 |
6 | 21 | 20 | 41 |
7 | 34 | 38 | 72 |
8 | 55 | 71 | 126 |
9 | 89 | 130 | 219 |
10 | 144 | 235 | 379 |
This can probably be improved, possibly to a single recursion for U.