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

Question

I have asked this question before Here
The first guy solved it in a way, but i would like to know is there any efficient way
to do so, because i did the same for N = 13 and N = 15 which took long time.

This problem is from a pen and paper test, ZIO-2018 Can i solve it with an efficient algorithm, well i am pretty beginner in algos, so if there is one kindly descibe it how can i do so?

Thank you

Answer 1

I will quote Matthew Daly's answer and try to provide additional explanation. I will also make a small change.

Let $C_n$ be the number of ways to choose a [nonempty] 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 [possibly empty] 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?

The number $C_n$ is the number you are looking for. We'll see soon why we also want to consider $L_n$, which is defined similarly but for people standing in a line rather than a circle (i.e., there are two people at the ends of the line, and those people are not considered adjacent to one another). Note that $C_n$ does not count the empty group, but $L_n$ does.

Step 1: $C_n=(L_{n−1} -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.

We are breaking down all of the choices that make up $C_n$ into two categories: those that do not include the person $p_n$ and those that do. Suppose we know that $p_n$ is not selected. Then if we remove $p_n$ from the circle, we are left with a line of $n-1$ people: $p_1,p_2,\dots,p_{n-1}$. It is a line rather than a circle since the two people on either side of $p_n$ (i.e., $p_1 $ and $p_{n-1}$) are not adjacent to each other ($p_n$ was between them). So the number of ways to choose a (possibly empty) group of people not including $p_n$ and such that no two people are adjacent is $L_{n-1}$, the number of ways to choose a (possibly empty) group of people from the line of $n-1$ people such that no two are adjacent. However, this counts the choice of the empty group from the circle, so we subtract one to get $(L_{n-1}-1)$ as the number of nonempty groups which do not include $p_n$.

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.

Now we are counting how many groups do contain $p_n$. Since their neighbors ($p_1$ and $p_{n-1}$) cannot be in the group, we remove them along with $p_n$ and get the line of $n-3$ people: $p_2,p_3,\dots,p_{n-2}$. We need to choose the remainder of the group from this line such that no two people are adjacent to each other. The number of such choices is $L_{n-3}$. This time we allow the empty group to be chosen from the line, since the group chosen from the circle contains $p_n$ and thus is not empty. So there are $L_{n-3}$ ways to choose a group containing $p_n$ from the circle such that no two people are adjacent.

Combining these two counts, we now have $C_n$ written in terms of $L_{n-1}$ and $L_{n-3}$, which might not seem like an improvement. But we can try to work out what the $L_n$'s are.

Step 2: $L_n=F_{n+2}$, where $F_n$ is the $n$'th Fibonacci number (i.e. $L_1=2$,$L_2=3$)

The Fibonacci numbers are defined by $F_1 = 1, F_2=1$ and for all $n >2$, $F_n=F_{n-1}+F_{n-2}$. (So $F_3=F_1+F_2=1+1=2$, $F_4=F_2+F_3=1+2=3$, $F_5=F_3+F_4=2+3=5$, and so on). So to prove the claim in Step 2, it suffices to show that $L_1=F_3$, $L_2=F_4$, and for all $n >2$, $L_n=L_{n-1}+L_{n-2}$.

Proof: By inspection, $L_1=2$ and $L_2=3$, since we are still counting the possibility that no one is chosen.

To be explicit, the choices when the line is just $p_1$ are $\emptyset$ and $\{p_1\}$. The choices when the line consists of $p_1,p_2$ are $\emptyset$, $\{p_1\}$, and $\{p_2\}$. Now we show $L_n=L_{n-1}+L_{n-2}$ for $n >2$:

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.

Again we break down $L_n$ depending on whether $p_n$ is chosen or not. If $p_n$ is not chosen, then removing $p_n$ from the line leaves $p_1,\dots,p_{n-1}$ which is a line of $n-1$ people. So the number of ways to choose a group from this line such that no two people are adjacent is $L_{n-1}$.

If so, then $p_{n−1}$ must not be in the group and the remaining members can be chosen in $L_{n−2}$ ways.

If $p_n$ is chosen, then we know their neighbors $p_{n-1}$ cannot be chosen. Removing these two individuals leaves the line $p_1,\dots,p_{n-2}$ which is a line of $n-2$ people. So there are $L_{n-2}$ ways to choose a group from this line such that no two people are adjacent.

Therefore, $L_n=L_{n−1}+L_{n−2}$ and the sequence is a tail of the Fibonacci sequence starting at $2$.

This is just combining the two counts depending on whether $p_n$ is chosen or not. This ends the proof of Step 2.

The purpose of Step 2 was to get an explicit expression for the $L_n$'s so that we can plug those in to the expression in Step 1. Doing this, we get $$C_n=(L_{n-1}-1)+L_{n-3} = (F_{n+1}-1) + F_{n-1}.$$

To work this out by hand for, say, $n=15$, you need to compute $F_{14}$ and $F_{16}$. This can be done by repeated addition starting with what I began calculating above:

\begin{align*} F_1&=1\\ F_2&=1\\ F_3&=2\\ F_4&=3 \\ F_5&=5\\ F_6&=3+5=8\\ F_7&=5+8=13\\ F_8&=8+13=21\\ F_9&=13+21=34\\ F_{10}&=21+34=55\\ F_{11}&=34+55=89\\ F_{12}&=55+89=144\\ F_{13}&=89+144=233\\ F_{14}&=144+233=377\\ F_{15}&=233+377=610\\ F_{16}&=377+610=987. \end{align*}

So $C_{15}=(F_{16}-1)+F_{14} = (987-1)+377=1363$.

Answer 2

The general formula for counting the number of qualifying subsets of size $m$ is $\frac{n}{n-m}\binom{n-m}{m}$, so you need the sum for all $m$ up to $\lfloor\frac{n}{2}\rfloor$