2
$\begingroup$

I need help primarily with the finding a solution, I already came up with an answer.

We define an Eden sequence to be a subset of the set $\{1,2,3,4,\ldots ,N\}$. The Eden sequence has three conditions.

  1. each of its terms is an element of the set of consecutive integers $\{1,2,3,4,\ldots ,N\}$,
  2. the sequence is increasing, and
  3. the terms in odd numbered positions are odd and the terms in even numbered positions are even.

We then define a function $e(N)$ such that $e(N)$ denotes the number of Eden sequences of the set $\{1,2,3,4,\ldots ,N\}$. If we are given that $e(17)=4180$ and $q(20)=17710$, how would we find $e(18)$ and $e(19)$ using a mathematical approach?

I am pretty sure the answers are that $e(18) = 6764$ and $e(19) = 10945$.

Thanks for your help in advance!

3 Answers 3

5

Ok, either you or I are off by one, but here goes.

The fact that the sequence is increasing but the parity stays the same means that the missing numbers go in consecutive blocks of two. So the number of Eden sequences is the same as the number of ways of tiling the numbers from 1-n with dominoes of one size one or two. These are well known to be the Fibonacci numbers. It appears that the sequence itself is not counted as the numbers you quote are one greater than the corresponding Fibonacci number.

As will has observed, this does not count the sequences where an odd number of numbers are left out of the tail of the Eden sequence. These are eqivalent to the tilings that have a 2-domino extending one unit past the end. There are $F(n-1)$ of these (the sequences of length $n-1$ with a 2 domino slapped on the end). So there are $F(n)+F(n-1)=F(n+1)$ possible sequences, and it appears that the empty sequence is the missing one.

  • 0
    @WillOrrick You are correct. I was forgetting the case where the length two dominoes extend off the end of the sequence. When I get a chance, I will update my answer. Thanks.2012-04-15
3

Denote $\{1,2,\ldots,N\}$ by $[N]$.

Let $e(N)$ and $o(N)$ be the numbers of Eden sequences from $[N]$ of even length and of odd length. So $q(N)=e(N)+o(N)$. If $N$ is even, then $e(N)=e(N-1)+o(N-1)$ since an even-length sequence from $[N-1]$ is also an even-length sequence from $[N]$, while one may add $N$ to an odd-length sequence from $[N-1]$ to get an even-length sequence from $[N]$. Furthermore, $o(N)=o(N-1)$ since an odd-length sequence from $[N]$ cannot have $N$ as its last element.

The $N$ odd case can be handled similarly.

Using these recurrences, one may express $e(N)$ and $o(N)$, and hence $q(N)$, for $N>17$, in terms of $e(17)$ and $o(17)$. Since $q(17)=e(17)+o(17)$, one may use the known values of $q(17)$ and $q(20)$ to solve for $e(17)$ and $o(17)$. One may then compute $q(18)$ and $q(19)$. I find the same value of $q(19)$ that you found, but a different value of $q(18)$.

Edit: The analysis above assumes that the empty sequence counts as one of the even sequences. This is not the assumption that was made in the original poster's question since $q(17)=4180$ and $q(20)=17710$ are the correct numbers when the empty sequence is omitted. We can modify the analysis above to account for this by leaving the definitions of $e(N)$ and $o(N)$ as is (that is, $e(N)$ includes the empty sequence), but redefining $q(N)$ as $q(N)=e(N)-1+o(N)$ (so that $q(N)$ does not include the empty sequence). With this modification our numbers are in perfect agreement.

2

The answers for q(18) and q(19) are correct. The formula that can be established is that q(N)=q(n-1) + q(N-2) + 1, N>2. I found that examining q(N) separately for N odd and for N even helped. Also, for each N up to 6 I looked separately at the sequences that ended in an even number and those that ended in an odd number; this led me to the above equation. Using the formula along with the given values for q(17) and q(20) it was relatively easy to calculate q(18) and then q(19). I could go into more detail but if I can establish the above formula using this approach I'm sure you'll have no problem.

  • 0
    I think the discrepancy between our answers comes down to whether the empty sequence is allowed or not. I did not check, although I should have, whether the original poster's numbers for $q(17)$ and $q(20)$ included the empty sequence. Since in fact they do not, your recurrences are the correct ones. I will add a note about this to my answer.2012-04-15