3
$\begingroup$

I am looking at the following problem. There are three types of toys: a small, a medium, and a large. The medium is twice as long as the small and the large is thrice as long as the small. I have a shelf that can accommodate exactly 10 small toys lengthwise. How many different ways can this shelf be filled using different combinations of the toys (where order matters)?

It is easy to solve for shorter shelves; for instance, for shelf length $3$, there are $4$ ways: small ($3x$); small, medium; medium, small; large. For shelf length $4$, there are $7$ ways: small ($4x$); small ($2x$), medium; small, medium, small; medium, small ($2x$); medium ($2x$); small, large; large small. It is more tedious to enumerate for shelves larger than 4 units; I am looking for a more elegant and systematic method to enumerate the different ways to fill the $10$-unit shelf, ideally one that can be easily adapted to a larger shelf size.

$\endgroup$
1
  • $\begingroup$ This may be helpful (see first comment). $\endgroup$ Sep 29 '16 at 23:24
0
$\begingroup$

Let $a_k$ be the number of ways of filling a shelf of length $k$.

Observe that $a_1 = 1$ since the only way to fill a shelf of length $1$ is to use a small toy; $a_2 = 2$ since the only ways to fill a shelf of length $2$ are to use a medium toy or two small toys; and $a_3 = 4$ since the only ways to fill a shelf of length $3$ are to use a large toy, use a medium toy followed by a small toy, use a small toy followed by a medium toy, or use three small toys.

To complete a shelf of length $k \geq 4$ by adding a single toy, we have three options:

  • add a small toy to a sequence of toys of length $k - 1$
  • add a medium toy to a sequence of toys of length $k - 2$
  • add a large toy to a sequence of toys of length $k - 3$

Hence, we have the recursion relation \begin{align} a_1 & = 1\\ a_2 & = 2\\ a_3 & = 4\\ a_k & = a_{k - 1} + a_{k - 2} + a_{k - 3},~\text{if}~k \geq 4 \end{align}

The Tribonacci numbers are defined by the recurrence relation \begin{align*} T_0 & = 0\\ T_1 & = 0\\ T_2 & = 1\\ T_n & = T_{n - 1} + T_{n - 2} + T_{n - 3}~\text{if}~n \geq 3 \end{align*} so $a_k = T_{k + 2}$.

$\endgroup$

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.