" Recall that our combinatorial interpretation of the Fibonacci numbers $f_0 = f_1 = 1$ with $f_n = f_{n-1} + f_{n-2}$ for $n \geq 2$ was the number of ways to tile a board of length $n$ using squares (taking up 1 space) and dominos (taking up 2 spaces).

Invent a combinatorial interpretation for the ''Tribonacci numbers'', given by $t_0 = t_1 = 1$, $t_2 = 2$, and $t_n = t_{n-1} + t_{n-2} + t_{n-3}$ for $n \geq 3$."

EDIT: Thanks everyone! From what I gathered here I was able to understand everything.

  • 2
    $\begingroup$ Hint: try finding a combinatorial interpretation of tiling a board of length $n$ using some set of tiles. $\endgroup$ – Peter Shor Jun 6 '13 at 4:06
  • $\begingroup$ What is the pattern for the 2xn board? I'm familiar with what Peter is getting at (1xn), but your suggestion is new to me :) More to the point for answering your question, can you mimic the proof of the Fibonacci interpretation (referenced in the problem) is valid? $\endgroup$ – Eric Stucky Jun 6 '13 at 5:54

For a fairly long list that you can select ideas from, please see this from OEIS (Online Encyclopedia of Integer Sequences).

Added: Think of the number $b(n)$ of ways to express $n$ as an ordered sum of numbers chosen from $\{1,2,3\}$. (You can give a more visual version in terms of "dominos").

The case $n=0$ is tricky, there is $1$ way to do it, use no numbers.

Obviously $b_1=1$.

For $2$, we have the representations $2$ and $1+1$, so $b_2=2$.

For $3$ we have the representations $3$, $2+1$, $1+2$, and $1+1+1$, so $b_3=4$.

For $4$ we have $3+1$, $2+2$, $2+1+1$, $1+3$, $1+2+1$, $1+1+2$, and $1+1+1+1$, so $b_4=7$.

Now try to argue why the recurrence holds.

  • $\begingroup$ Sorry Andre, but that link is guiding me anywhere. Like I said to Mr.Shor, I've tried drawing a 2xn board to find a pattern like I did for the Fibonacci numbers, but I haven't found anything. $\endgroup$ – Ozera Jun 6 '13 at 4:57
  • 1
    $\begingroup$ The number of compositions of $n-2$ with no part greater than $3$ (mentioned in my link) is dominoes of length $1$, $2$, or $3$, where we are making a pattern of length $n-2$. That's very close in spirit to the Fibonacci example you mentioned in your post. $\endgroup$ – André Nicolas Jun 6 '13 at 5:07
  • $\begingroup$ Calculate very carefully how many ways there are to make a $1\times k$ board using $1\times 1$'s and/or $2\times 1$'s and/or $3\times 1$'s. You will find your numbers coming up. $\endgroup$ – André Nicolas Jun 6 '13 at 5:27
  • $\begingroup$ I added sme stuff, including explicit listing for the first few numbers. $\endgroup$ – André Nicolas Jun 6 '13 at 5:48
  • $\begingroup$ Look at the added material in the post, it is I think correct. $\endgroup$ – André Nicolas Jun 6 '13 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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