Question

A carpenter produces two types of furniture: chairs and tables. Each chair takes one full day
to produce, and each table takes three days. The craftsman wants to schedule her tasks for
the next n days; how many different schedules are possible? (Assume that the carpenter will
work on each of the n days, and will not leave any tasks unfinished at the end of the nth
day.) For example, if n = 5, then there are four possibilities: the carpenter could produce five
chairs (one on each of the five days), she could produce two chairs followed by a table, she
could produce one chair followed by a table followed by another chair, or she could produce
a table followed by two chairs.
(a) Let sn denote the number of possible n-day schedules. Find a recurrence relation for sn.
(b) Let tn denote the number of schedules provided that the carpenter will not build chairs for
two or more days in a row. Find a recurrence relation for tn.

Answer 1

The distinct permutation of objects each of the same kind is

.

Using the above general formula, when , where .

tables and chairs can be sheduled in ways. We can have at most tables.

The number of possible shedules is

a)

1) On the day we can shedule a chair

2) On the day can include a table.

These two cases are mutually exclusive.

Also if , days can include tables.

So the recursion is

b) The carpenter will not build chairs for two or more days in a row.

1) The day can be a chair preceded by a table.

2) The day can include a table.

These two cases are mutually exclusive. So if denote the number of schedules (in days) provided that the carpenter will not build chairs for two or more days in a row, then the recursion can be written as