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.

  • 0
    @tohecz: That's a good point; the multipler may be polynomial.2012-11-30

2 Answers 2

1

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.

  • 0
    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`.2012-11-30
0

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.

  • 0
    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.2012-11-30