Question 62971: Richard Stanley writes in his book "Enumerative Combinatorics" that it is easily seen why  where f(n) is the number of subsets of [n] ({1,2,3,..,n}) that do not contain two consecutive integers.
Can someone actually explain why it is so, please?
Thanks!
Answer by joyofmath(189)   (Show Source):
You can put this solution on YOUR website! Richard Stanley writes in his book "Enumerative Combinatorics" that it is easily seen why where f(n) is the number of subsets of [n] ({1,2,3,..,n}) that do not contain two consecutive integers.
Can someone actually explain why it is so, please?
This is an interesting problem that took me a while to figure out. I can give you the gist of what's going on but you'd have to do a proof, either by induction or by contradiction to really prove the relationship.
Here's the idea:
Let's enumerate the subsets when n=3: {}{1}{2}{3}{13}
Let's enumerate the subsets when n=4: {}{1}{2}{3}{4}{13}{14}{24}
Now, let's say we want to construct the subsets when n=5. We can do this as follows, in two steps:
1. Take all the subsets we used for n=4. They're all still legal when n=5.
2. Take all the subsets we used for n=3. Add the number 5 to the end of each subset. That would give us {5}{15}{25}{35}{135}.
Combining the subsets from n=3 (with the 5 tacked onto the end of each subset) and n=4 gives us the subsets for n=5 which is the motivation behind .
Note that there's no duplication between the subsets in n=3 with the 5's tacked on and the subsets in n=4 because the subsets in n=4 can't have any 5's (because n=4). Note also that tacking 5 onto the subsets in n=3 is legal since the n=3 subsets all end in 3 or less and thus tacking on 5 doesn't violate the nonconsecutive number constraint.
Does this make sense?
Note, you'd have to do a real proof, in particular you'd need to prove that no subsets were missing when we construct f(n) from f(n-1) and f(n-2).
|
|
|
