1
$\begingroup$

It is likely a duplicate, but I couldn't find an original question, so creating a new one.

Given a set $A=\{1,2,...,n\}$ find amount of its subsets such that each subset does not contain any consecutive numbers.

For example, $\{1,3\}, \varnothing, \{1,3,5\}$ are OK, but $\{1,2\}, A, \{1,3,n-1,n\}$ are not OK.

I tried to solve this task using inclusion-exclusion formula, but got stuck when computing the 3rd term. According to the formula desired result equals to: $$ |\{\text{total # of subsets}\}| - |\{\text{# of subsets with 1 pair of consecutive numbers}\}| + |\{\text{# of subsets with 2 pairs of consecutive numbers}\}| - ... $$ First term is easy, it equals to $2^n$.

To calculate the second term I am picking one consecutive pair out of $n-1$ possible and then calculate subsets with this pair included. So it equals $(n-1) \cdot 2^{n-2}$.

For the 3rd term I tried to pick one pair out of $n-1$ possible, then the second pair out of $n-2$ remaining and then calculate amount of subsets with both pairs included, i.e. it would equal something like $(n-1)(n-2)\cdot 2^{n-4}$. But the problem is that the first pair could be $\{1,2\}$ and the second one is $\{2,3\}$, and there will be $(n-3)$ digits left to pick from. To account for this we'll have to split the variants into these two cases. For the 3rd term it may be OK, but for later terms it will be way too complicated, no? Is there a nicer solution?

$\endgroup$
2
  • 5
    $\begingroup$ Try a recursion. Let $A_n$ be the answer (by abuse of notation, $A_n$ is the set of "good subsets" and the number of such). If your subset doesn't contain $n$ then it must be an element of $A_{n-1}$. If it does contain $n$ it must be an element of $A_{n-2}\cup \{n\}$. $\endgroup$
    – lulu
    Commented May 9, 2018 at 11:39
  • 3
    $\begingroup$ General note: for problems like this it is an excellent idea to work out the answer for small $n$, see if you can spot a familiar pattern. $\endgroup$
    – lulu
    Commented May 9, 2018 at 11:40

2 Answers 2

1
$\begingroup$

Let $A_n = \{1,2,3,\dots,n\}$. Let $G_n$ be the number of "good" subsets of $A_n$. Here I will consider the empty set to be a "good" subset of each $A_n$.

For each subset, $S$ of $A_n$ there is a function $f_{n,S}:A_n \to \{0,1\}$ define by $f_{n,S}(x)= \begin{cases} 0 & \text{If $x \not \in S$} \\ 1 & \text{If $x \in S$} \\ \end{cases}$


\begin{array}{c} & f \\ \text{subset} & 1 & \text{good?} \\ \hline & 0 &\checkmark \\ 1 & 1 &\checkmark \\ \hline \end{array}

So $A_1=2$.


\begin{array}{c} & f \\ \text{subset} & 12 & \text{good?} \\ \hline & 00 &\checkmark \\ 1 & 10 &\checkmark \\ 2 & 01 &\checkmark \\ 12 & 11 \\ \hline \end{array}

So $A_2=3$.


\begin{array}{c} & f \\ \text{subset} & 123 & \text{good?} \\ \hline & 000 &\checkmark &\text{Compare to $A_2$}\\ 1 & 100 &\checkmark \\ 2 & 010 &\checkmark \\ 12 & 110 \\ \hline 3 & 001 &\checkmark &\text{Compare to $A_1$}\\ 13 & 101 &\checkmark \\ 23 & 011 & \\ 123 & 111 \\ \hline \end{array}

So $A_3=A_1+A_2=5$.


\begin{array}{c} & f \\ \text{subset} & 1234 & \text{good?} \\ \hline & 0000 &\checkmark &\text{Compare to $A_3$}\\ 1 & 1000 &\checkmark \\ 2 & 0100 &\checkmark \\ 12 & 1100 \\ 3 & 0010 &\checkmark \\ 13 & 1010 &\checkmark \\ 23 & 0110 & \\ 123 & 1110 \\ \hline 4 & 0001 &\checkmark &\text{Compare to $A_2$}\\ 14 & 1001 &\checkmark \\ 24 & 0101 &\checkmark \\ 124 & 1101 \\ 34 & 0011 & \\ 134 & 1011 & \\ 234 & 0111 & \\ 1234 & 1111 \\ \hline \end{array}

So $A_4=A_2+A_3=8$.


So it seems that $A_1=2, \quad A_2=3, \quad$ and $A_{n+2}=A_n + A_{n+1}$ Thus $A_n = F_{n+2}$, the $(n+2)^{th}$ fibonacci number.

$\endgroup$
0
$\begingroup$

Supposing the subset is not the empty set we first choose the smallest value:

$$\frac{z}{1-z}.$$

Then we add in at least two several times to get the remaining values:

$$\frac{z}{1-z} \sum_{m\ge 0} \left(\frac{z^2}{1-z}\right)^m = \frac{z}{1-z} \frac{1}{1-z^2/(1-z)} = \frac{z}{1-z-z^2}.$$

Finally we collect the contributions that sum to at most $n$ and add one to account for the empty set:

$$1+ [z^n] \frac{1}{1-z} \frac{z}{1-z-z^2} \\ = [z^n] \frac{1}{1-z} + [z^n] \frac{1}{1-z} \frac{z}{1-z-z^2} \\ = [z^n] \frac{1}{1-z} \frac{1-z^2}{1-z-z^2} \\ = [z^n] \frac{1+z}{1-z-z^2}.$$

Calling the OGF $G(z)$ we have

$$G(z) (1-z-z^2) = 1 + z$$

so that for $[z^0]$ we get

$$[z^0] G(z) (1-z-z^2) = 1$$

or $g_0 = 1.$ We also get

$$[z^1] G(z) (1-z-z^2) = 1$$

or $g_1-g_0 = 1$ or $g_1=2.$ We have at the end for $n\ge 2$

$$g_n-g_{n-1}-g_{n-2} = 0,$$

which is the Fibonacci number recurrence. With these two initial values we obtain

$$\bbox[5px,border:2px solid #00A000]{ F_{n+2}.}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .