# Counting the number of Eden sequences in $\{1,2,\ldots,N\}$

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

-

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.

-
Hi thanks for the response! my calculation was based on trial and error it has no legit proof behind it. I tested it for small numbers and say this: q(1)=1, q(2)=q(1)+1=2,q(3)=q(2)+2=4,q(4)=q(3)+3=7,q(5)=q(4)+5=12,q(6)=q(5)+8=20. So obviously there is some relation to fibonacci numbers, but if you go along in this pattern my answer comes up and so does the conditions given in the problem. How can we show that q(n)=q(n-1)+F_n . Where F_n is the nth fibonacci number. Once again thanks for the help! – ahuang Apr 15 '12 at 3:53
Also can you please explain why the missing numbers go in consecutive blocks of two, and the domino idea. Thanks! – ahuang Apr 15 '12 at 3:59
@alan If you have an odd number followed by a larger even number there are an even number of integers skipped, Likewise for an even number followed by an odd number. – deinst Apr 15 '12 at 4:21
I believe the quoted numbers are one less than the corresponding Fibonacci numbers, most likely because the empty sequence is not counted. (More about this in my answer.) Nice observation about the dominoes, by the way. – Will Orrick Apr 15 '12 at 15:51
An observation related to domino tilings: use "." and "=" to represent dominoes of lengths 1 and 2. The tilings we get for the first few $N$ are {.} ($N=1$), {.., =} ($N=2$), {...,=.,.=} ($N=3$), {....,=..,.=.,..=,==} ($N=4$). These correspond to the Eden sequences {{1}}, ($N=1$), {{1,2},{}} ($N=2$), {{1,2,3},{3},{1}} ($N=3$), {{1,2,3,4},{3,4},{1,4},{1,2},{}} ($N=4$). Observe that (1) for $N$ even, only even-length Eden sequences correspond to domino tilings, while for $N$ odd, only odd-length Eden sequences correspond to domino tilings; – Will Orrick Apr 15 '12 at 16:33

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.

-

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.

-
I tried to do just as you said but I still am not able to come up with the formula I dont know what it is that im doing wrong. Can you please go in a little bit more detail. Once again thank you very much! – ahuang Apr 15 '12 at 4:22
I was thinking similarly to the above answer using o(N) and e(N) but I did get q(18) = 6764 so I'll quickly outline my approach. Starting with N odd, we have q(N) = o(N) + e(N). Now for q(N+1), we can add (N+1) to the end of each odd sequence to form o(N) more sequences giving us q(N+1) = 2*o(N) + e(N). For q(N+2), with (N+2) being odd we can add it to the end of the e(N) sequences and the o(N) sequences we just made even, plus have (N+2) as a single digit sequence, giving us q(N+2) = 3*o(N) + 2 *e(N) + 1 = q(N+1) + q(N) + 1, which can be rewritten as q(N) = q(N-1) + q(N-2) + 1. – Brian Apr 15 '12 at 5:51
The same thing can be done starting with N even, yielding the same formula. I hope my approach isn't too muddled for you. – Brian Apr 15 '12 at 5:55
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. – Will Orrick Apr 15 '12 at 15:38