5
$\begingroup$

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?

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

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}$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

Let $\mathscr{A}$ be the family of such ‘subsets’ of $[n]$ (where $[0]$ 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\;.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.