# Invent a combinatorial interpretation for the ''Tribonacci numbers''

" 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.

• Hint: try finding a combinatorial interpretation of tiling a board of length $n$ using some set of tiles. – Peter Shor Jun 6 '13 at 4:06
• 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? – 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.

• 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. – Ozera Jun 6 '13 at 4:57
• 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. – André Nicolas Jun 6 '13 at 5:07
• 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. – André Nicolas Jun 6 '13 at 5:27
• I added sme stuff, including explicit listing for the first few numbers. – André Nicolas Jun 6 '13 at 5:48
• Look at the added material in the post, it is I think correct. – André Nicolas Jun 6 '13 at 6:35