# Non-isomorphic combinatorial classes with growth rate equal to the golden ratio?

In a couple of weeks, I'm giving a talk about the growth rates of some combinatorial classes.

In the introduction, I thought I'd present the class of tilings of a $n\!\times\!2$ strip with dominos, which is enumerated by the Fibonacci numbers and hence has growth rate equal to the golden ratio $\phi=\frac{1}{2}(\sqrt{5}+1)$. I thought it would be fun to show some other classes, preferably as distinct as possible, with the same growth rate but different enumeration sequences.

Clearly it's possible to come up with different tilings that also have growth rate $\phi$ but aren't enumerated by the Fibonacci numbers (e.g. of a $n\!\times\!1$ strip with $1\!\times\!1$, $3\!\times\!1$ and $4\!\times\!1$ tiles, or with two distinct $2\!\times\!1$ tiles and a $3\!\times\!1$ tile), but I wondered what other, more varied (interesting, natural) classes there are. So the question is:

What interesting combinatorial classes are there with growth rate equal to the golden ratio that are not enumerated by the Fibonacci numbers?

The answers should be easy to explain quickly to new postgraduates who may have no familiarity with combinatorics.

-
You know, since $F_n$ is the closest integer to $\phi^n$, it is (close to) impossible to find something integer that is related to $\phi^n$ but not to $F_n$. – yo' Nov 30 '12 at 13:10
@tohecz: Are you saying that David's examples of $n\times1$ strips are flawed? – joriki Nov 30 '12 at 13:12
No, but they are based on the same recurrence relation $x_n=x_{n-1}+x_{n-2}$, which means that their solution is a multiple of $F_n$ with some (eventually small) correction and with rounding. – yo' Nov 30 '12 at 13:15
@tohecz: That's a good point; the multipler may be polynomial. – David Bevan Nov 30 '12 at 15:08

A001629 has some possibilities which don't immediately reveal Fibonacci connections:

• Total number of elements in all subsets of $[n]$ with no consecutive integers.
• Number of binary sequences of length $n$ with exactly one pair of consecutive 1's.

A006490 is related.

-
The problem is that since the first one "deny" 11 in some sense, it is immediately connected to Fibonnaci sequence, since this sequence is the complexity of language of all binary words avoiding 11. – yo' Nov 30 '12 at 16:28

Anything enumerated by the Lucas numbers $L_n$, which satisfy the same recurrence as the Fibonacci numbers but with the initial conditions $L_1 = 1$, $L_2 = 3$. Wolfram MathWorld gives an example: the number of subsets of $[n] = \{1, 2, \ldots, n\}$ so that no two elements in in the set are "cyclically" consecutive, so that $1$ and $n$ are considered consecutive.

-
Of course these are connected to the Fibonacci numbers - there's the identity $L_n = F_{n-1} + F_{n+1}$. But I'd venture to guess just about any "natural" sequence with this growth rate would have some kind of connection to Fibonacci numbers. – Jair Taylor Nov 30 '12 at 19:05