Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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