Find the total number of ways to select a non-empty subset of these people, such that no two adjacent people are selected.

Question

There are N people are sitting around a circular table. Let’s call them P1, P2, . . . , PN , in order. P1 is sitting between P2 and PN . P2 is sitting between P1 and P3. P3 is sitting between P2 and P4, and so on.

You need to select a non-empty subset of these people, such that no two adjacent people are selected. Find the total number of ways in which you can do so.
For example, suppose N = 3, then we have P1, P2 and P3. If we select P1, then neither P2 nor P3 can be selected. So, the only valid selections are {P1}, {P2}, {P3}.

So there are three possible ways, and hence the answer would be 3. Suppose N = 4, then we have P1, P2, P3 and P4. The possible subsets are {P1}, {P2}, {P3}, {P4}, {P1, P3}, {P2, P4}. So the answer would be 6.

Find the answer for the following values of N:
(a) N = 11
(b) N = 13
(c) N = 15
source:- Q.3 https://www.iarcs.org.in/inoi/2019/zio2019/zio2019-question-paper.pdf
ANS:- (a)198
(b) 520 (c) 1363
This question was from pen & paper test

My failed attempt:-

(a) For N = 11,
the possible subsets are {P1},{P2},....{P11} = 11 +
since P11,P2 are adjacent to P1, the next possible subsets are:- {P1,P3},{P1,P4},...,{P1,P10}
= 8 +
Similarly, P1,P3 are adjacent to P2, the next subsets are:- 
{P2,P4},{P2,P5}.....,{P2,11} = 8 +
DOING SAME FOR P3,P4,P5,P6,P7,P8,P9,P10,P10, (each of the individual has 7 subsets)
total subsets of them are :- 7 x 9 + 8 + 8 + 11 = 90.
MY ANS:-90

Answer 1

Two comments:

First, your count for subsets of $2$ is off. When you choose $P_4$, you have already counted pairing that up with $P_1$ and $P_2$, and so you only have $6$ more options, rather than $7$. So, you get $8+8+7+6+5+4+3+2+1=44$ options.

However, an easier way to count this is to say that for *each * person we can pick $8$ others, giving $11\cdot 8 = 88$ options. Of course, now you need to rule out double-counting: first picking $P_1$ and then picking $P_6$ gives you the same subset as first picking $P_6$ and then picking $P_1$. So, you need to divide by $2$. In other words, there are $\frac{88}{2}=44$ possible subsets of size $2$

Second: what about subsets of size $3$? For example, you can pick $P_1$, $P_4$, and $P_8$. You didn't count that subset, or any subset of size $3$. And you also didn't consider subsets of size $4$ or $5$. Now, any subset of size $6$ or larger will be impossible (do you see why?), but you will have to count the subsets of size $3$, $4$, and $5$.

OK, how many subsets of size $3$ are there?

You can again start with $P_1$, pick $P_3$ as a second person, and then have a choice of $6$ ($P_5$ through $P_{10}$) as a third. So, that's $6$ options. Then, still staying with $P_1$, you can pick $P_4$ as your second person, but now you have only $5$ persons left ($P_6$ through $P_{10}$) for the third one. So, that's another $5$ options. Choosing $P_5$ as the second gives $4$ options ... and continuing this, you get $6+5+4+3+2+1=21$ options with $P_1$ as the first person. This, of course, repeats for all $11$ people, so you get $11\cdot 21=231$ options. But again, you are over-counting, because for any subset of $3$, you could have picked any of those $4$ as your 'first' person. As such, every triple got counted $3$ times, and so you have $\frac{231}{3}=77$ possible subsets of size $3$

For subsets of $4$:

Again, start with $P_1$, add $P_3$, then $P_5$, and now you have $4$ options left ($P_7$ though $P_{10}$). Now we can make the third person $P_6$, and that gives you $3+2+1=6$ options. Likewise, you get $2+1=3$ and $1$ one more while having $P_1$ as the second person. So, there are $10+6+3+1=20$ subsets with $P_1$ as the first person. Again, multiply by $11$ ... and divide by $4$, since each subset gets counted $4$ times, since we could have started going around with each of the $4$ people in each subset. So: $\frac{11 \cdot 20}{4}=55$

Subsets of $5$:

With $P_1$, $P_3$, $P_5$, and $P_7$ you have $2$ options left. You can also make $P_8$ the fourth person, and now there is $1$ option left. You can make the third $P_6$, and that also leads to $1$ options, and finally you can pick $P_4$ as the second, for a final option. Total: $5$ subsets with $P_1$. Again, multiply by $11$, and divide by size of subsets: $\frac{11 \cdot 5}{5}=11$ possibilities.

Total:

$11+44+77+55+11=198$ subsets

Answer 2

Let $C_n$ be the number of ways to choose a group of people from a circle of $n$ people such that no two adjacent people are chosen, and let $L_n$ be the number of ways to choose a group of people from a line of $n$ people such that no two adjacent people are chosen. For now, we will include the possibility that no one in the group is chosen -- remind me to rule that out at the end, okay?

Step 1: $C_n=L_{n-1}+L_{n-3}$
Proof: Let $n$ people numbered $p_1$ through $p_n$ be in a circle. Either $p_n$ is in the group or not. If $p_n$ is not in the group, then the remaining people could be selected for a group in $L_{n-1}$ ways. If $p_n$ is in the group, then we know for certain that $p_{n-1}$ and $p_1$ cannot be in the group, so the remaining members of the group can be chosen in $L_{n-3}$ ways.

Step 2: $L_n=F_{n+2}$, where $F_n$ is the n'th Fibonacci number (i.e. $L_1=2$,$L_2=3$)
Proof: By inspection, $L_1=2$ and $L_2=3$, since we are still counting the possibility that no one is chosen. Let $n>2$ be given, and let $p_1$ through $p_n$ be our $n$ people in a line. Again, either $p_n$ is in the group or not. If not, then the remaining members of the group can be chosen in $L_{n-1}$ ways. If so, then $p_{n-1}$ must not be in the group and the remaining members can be chosen in $L_{n-2}$ ways. Therefore, $L_n=L_{n-1}+L_{n-2}$ and the sequence is a tail of the Fibonacci sequence starting at $2$.

Hmmm? Oh, right, thank you. Since there is 1 way to have nobody in the group and we're not supposed to count that, our final answer is $C_n-1=F_{n+1}+F_{n-1}-1$.