# Number of subsets from an ordered set where adjacent elements may or may not be tied together

Assume we have an ordered set $S$ with a finite number of elements $S=\{1,2,3,\ldots,N\}$. I need to know the number of subsets where adjacent elements from the original set may either be tied together as one "unit" shown with a "-" between them or separate elements shown as "," as normally in a subset.

For instance, with 2 elements, if $S=\{1,2\}$ this number is 5 where the 5 subsets are: $\{\},\{1\},\{2\},\{1,2\}$ and $\{1-2\}$.

And with 3 elements, if $S=\{1,2,3\}$ there are 13 subsets of this kind: $\{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1-2\}, \{1,3\}, \{2,3\}, \{2-3\}, \{1,2,3\}, \{1-2,3\}, \{1,2-3\}$ and $\{1-2-3\}$.

With 4 elements I have counted this number to be 34. What is this number in the general case of $N$ elements, where $S=\{1,2,3,\ldots,N\}$ and can a formula be given?

• $\{0\}$ is not a subset of either of your $S$s. – Henning Makholm Apr 10 '16 at 11:48
• @HenningMakholm It appears that all $\{0\}$ should be replaced with $\{\}$. – Hagen von Eitzen Apr 10 '16 at 11:51

Let $a_n$ be the count of these listings for given $n$. Then $a_n$ is obtained as sum of those listings not ending in $n$ (there are $a_{n-1}$ of these), those ending in "$,n$" (there are $a_{n-1}$ of these), and those anding in "${-}n$" (there are $a_{n-1}-a_{n-2}$ of these). Hence we have the recursion $$a_n=3a_{n-1}-a_{n-2}.$$ The general solution to this is $$a_n=\alpha_1 \lambda_1^n+\alpha_2\lambda_2^n$$ where $\lambda_{1,2}$ are the roots of $x^2-3x+1=0$. So $\lambda_{1,2}=\frac{3\pm\sqrt{5}}{2}$. We determine $\alpha_{1,2}$ so that the result matches $a_0=1$, $a_1=2$. This leads to $\alpha_{1,2}=\frac{5\pm\sqrt 5}{10}$ so that $$a_n=\frac{5+\sqrt 5}{10}\cdot\left(\frac{3+\sqrt{5}}{2}\right)^n+\frac{5-\sqrt 5}{10}\cdot\left(\frac{3-\sqrt{5}}{2}\right)^n.$$ As the second summand is always between $0$ and $1$, we might as well say $$a_n=\left\lceil\frac{5+\sqrt 5}{10}\cdot\left(\frac{3+\sqrt{5}}{2}\right)^n\right\rceil.$$

Remark. In particular, the formualas above lead to $a_4=34$, not $30$. Indeed, here's the list: $$\begin{matrix}\{\}& \{1\}& \{2\}& \{1,2\}& \{1-2\}\\ \{3\}& \{1,3\}& \{2,3\}& \{2-3\}& \{1,2,3\}\\ \{1-2,3\}& \{1,2-3\}& \{1-2-3\}& \{4\}& \{1,4\}\\ \{2,4\}& \{1,2,4\}& \{1-2,4\}& \{3,4\}& \{3-4\}\\ \{1,3,4\}& \{1,3-4\}& \{2,3,4\}& \{2-3,4\}& \{2,3-4\}\\ \{2-3-4\}& \{1,2,3,4\}& \{1-2,3,4\}& \{1,2-3,4\}& \{1-2-3,4\}\\ \{1,2,3-4\}& \{1-2,3-4\}& \{1,2-3-4\}& \{1-2-3-4\}& \end{matrix}$$

Here is a solution using very basic generating functions. We will compute the generating function of these subsets with adjacencies marked and include most of the arithmetic.

First choose the first element:

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

Next choose the differences between subsequent elements taking care to mark adjacent elements with a difference of value one:

$$\sum_{q\ge 0} \left(uz + \frac{z^2}{1-z}\right)^q.$$

Finally observe that all subsets with final element less than or equal to $n$ contribute to the count for $n$, yielding a factor of

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

This produces the generating function

$$G(z, u) = \frac{1}{1-z} \frac{z}{1-z} \frac{1}{1-(uz(1-z)+z^2)/(1-z)} \\ = \frac{z}{1-z} \frac{1}{1-z-(uz-uz^2+z^2)} \\ = \frac{z}{1-z} \frac{1}{1-(1+u)z-(1-u)z^2}.$$

As a sanity check we have

$$G(z, 1) = \frac{z}{1-z} \frac{1}{1-2z} = -\frac{1}{1-z} + \frac{1}{1-2z}$$

so we get

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

subsets without markings, which is the correct answer since we have not included the empty set in the construction.

Now for the potentially tied sets we have that a symbol between adjacent values may be a comma or a dash so we set $u=2$, getting

$$G(z, 2) = \frac{z}{1-z}\frac{1}{1-3z+z^2}.$$

With $$\rho_{1,2} = \frac{3}{2}\pm \frac{\sqrt{5}}{2}$$

this becomes

$$-\frac{z}{z-1}\frac{1}{(z-\rho_1)(z-\rho_2)}.$$

Using partial fractions by residues we get

$$\frac{1}{z-1} - \frac{1}{z-\rho_1} \frac{\rho_1}{(\rho_1-1)(\rho_1-\rho_2)} - \frac{1}{z-\rho_2} \frac{\rho_2}{(\rho_2-1)(\rho_2-\rho_1)} \\ = -\frac{1}{1-z} + \frac{1}{1-z/\rho_1} \frac{1}{(\rho_1-1)(\rho_1-\rho_2)} + \frac{1}{1-z/\rho_2} \frac{1}{(\rho_2-1)(\rho_2-\rho_1)}$$

Extracting coefficients from this we obtain

$$[z^n] G(z, 2) = -1 + \rho_1^{-n} \frac{1}{(\rho_1-1)\sqrt{5}} - \rho_2^{-n} \frac{1}{(\rho_2-1)\sqrt{5}}.$$

We may add one here as this represents the empty set. Further simplification yields ($\rho_1\rho_2 = 1$)

$$\rho_2^n \frac{1}{(\rho_1-1)\sqrt{5}} - \rho_1^n \frac{1}{(\rho_2-1)\sqrt{5}}.$$

Finally $$\frac{1}{(\rho_{1,2}-1)\sqrt{5}} = \frac{1}{(1/2\pm \sqrt{5}/2)\sqrt{5}} = \frac{1}{\sqrt{5}/2\pm 5/2} \\ = \frac{\sqrt{5}/2\mp 5/2}{5/4-25/4} = \frac{\pm 5/2 - \sqrt{5}/2}{20/4} = \pm \frac{1}{2} - \frac{\sqrt{5}}{10}.$$

We thus obtain

$$\rho_2^n \left(\frac{1}{2} - \frac{\sqrt{5}}{10} \right) + \rho_1^n \left(\frac{1}{2} + \frac{\sqrt{5}}{10} \right) \\ = \left(\frac{1}{2} + \frac{\sqrt{5}}{10} \right) \left(\frac{3}{2} + \frac{\sqrt{5}}{2}\right)^n + \left(\frac{1}{2} - \frac{\sqrt{5}}{10} \right) \left(\frac{3}{2} - \frac{\sqrt{5}}{2}\right)^n.$$

This yields the sequence (starting at index one)

$$1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, \ldots$$

which incidentally is OEIS A001519.

Here’s a slightly different way to approach the problem.

Let $\mathscr{A}$ be the family of such ‘subsets’ of $[n]$ (where $$ is understood to be empty), and let $a_n=|\mathscr{A}_n|$. Clearly $a_0=1$ and $a_1=2$. Suppose that $n\ge 2$; $\mathscr{A}_n$ has $a_{n-1}$ members that do not contain $n$, so we’d like to know how many members of $\mathscr{A}_n$ do contain $n$. This suggests letting $\mathscr{B}_n$ be the set members of $\mathscr{A}_n$ that contain $n$ and letting $b_n=|\mathscr{B}_n|$; clearly $b_0=0$ and $b_1=1$, and $a_n=a_{n-1}+b_n$ for $n\ge 2$.

Each member of $\mathscr{B}_n$ in which $n$ is tied to $n-1$ can be obtained uniquely by appending a tied $n$ to a member of $\mathscr{B}_{n-1}$. Every remaining member of $\mathscr{B}_n$ can be obtained uniquely by appending an untied $n$ to a member of $\mathscr{A}_{n-1}$. Thus, $b_n=b_{n-1}+a_{n-1}$.

Calculate a few values of $a_n$ and $b_n$:

$$\begin{array}{rcc} n:&0&1&2&3&4&5\\ \hline b_n:&0&1&3&8&21&55\\ a_n:&1&2&5&13&34&89 \end{array}$$

These numbers are instantly recognizable as the Fibonacci numbers. Moreover, if we arrange them in the order in which they are naturally calculated from the recurrences

\left\{\begin{align*} b_n&=b_{n-1}+a_{n-1}\\ a_n&=a_{n-1}+b_n\;, \end{align*}\right.

we get the ordinary Fibonacci sequence:

$$\begin{array}{ccc} b_0&a_0&b_1&a_1&b_2&a_2&b_3&a_3&b_4&a_4&b_5&a_5\\ 0&1&1&2&3&5&8&13&21&34&55&89\\ F_0&F_1&F_2&F_3&F_4&F_5&F_6&F_7&F_8&F_9&F_{10}&F_{11} \end{array}$$

The obvious conjecture at this point is that in general $b_n=F_{2n}$ and $a_n=F_{2n+1}$. This is easily verified: the recurrences become

\left\{\begin{align*} F_{2n}&=F_{2n-2}+F_{2n-1}\\ F_{2n+1}&=F_{2n-1}+F_{2n}\;, \end{align*}\right.

which reduce to the single familiar Fibonacci recurrence $F_n=F_{n-1}+F_{n-2}$, and the initial values $F_0=b_0$ and $F_1=a_0$ are correct.

The problem is now reduced to standard results about the Fibonacci sequence. In particular, if $\varphi=\frac12\left(1+\sqrt5\right)$, it’s well known that $F_n$ is the integer nearest $\frac{\varphi^n}{\sqrt5}$, so $a_n$ is the integer nearest $\frac{\varphi^{2n+1}}{\sqrt5}$. Equivalently,

$$a_n=\left\lfloor\frac{\varphi^{2n+1}}{\sqrt5}+\frac12\right\rfloor\;.$$

Hagen von Eitzen’s closed form is easily derived from this and the observation that

$$\varphi^2=\frac{3+\sqrt5}2\;.$$