3
$\begingroup$

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.

  • 2
    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$.2012-11-30
  • 0
    @tohecz: Are you saying that David's examples of $n\times1$ strips are flawed?2012-11-30
  • 0
    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.2012-11-30
  • 0
    @tohecz: That's a good point; the multipler may be polynomial.2012-11-30

2 Answers 2