0

I already had a look at the following problem: For a given set $\{1, \dots, n\}$, how many sets are there so that there are no two consecutive numbers in them?

The answer could be found by using recurrence relations, namely: $$ M_n = M_{n-1} + M_{n-2} + 1 - 1$$ where $M_{i}$ indicates the number of sets with ${i}$ being in them or not; $M_0 = 1$ and $M_1 = 2$ (having a look at those cases). It just means that if we omit $n$, we have $M_{n-1}$ options to choose, or we have as many choices as with $M_{n-2}$ (they are compatible with adding ${n}$ to them). $+1$ because of the set ${n}$, and $-1$ because the empty set will be in both recurrence relations used. I was able to calculate an explicit formula for $M_n$ by solving the recurrence relation.

Now I am stuck with solving the problem for $\{1,\dots, n\}$ being a cyclic set, meaning that $1$ is the successor of $n$.

Can someone give me a hint for finding a suiting recurrence relation?

mdot
  • 947
  • do you consider pemutations ? – Abr001am Nov 08 '15 at 20:54
  • 1
    Your recurrence is correct, but the explanation could be better. $M_i$ is the total number of subsets, whether or not $i$ is in them. In forming $M_n$, if you don't add $n$ you have $M_{n-1}$ choices and if you do add $n$ you have $M_{n-2}$ choices of the subset – Ross Millikan Nov 08 '15 at 21:02
  • @Agawa001 I thought about them, but I was unable to find a way to use them for solving the second problem. – mdot Nov 08 '15 at 21:05

1 Answers1

1

Building on your result, you have $M_n=F_{n+2}$, the $n+2^{\text{nd}}$ Fibonacci number. To make a circle of $n$, you either include $n$, in which case you must have a linear subset of $\{2,3,4,\dots ,n-2\}$, or you do not include $n$, in which case you must have a linear subset of $\{1,2,3,4,\dots ,n-1\}$. Letting $C_n$ be the number of circular subsets out of $\{1,2,3,\dots n\}$, you have $C_n=M_{n-3}+M_{n-1}=F_{n-1}+F_{n+1}$

Ross Millikan
  • 374,822