Suppose that we are putting animals in a barn. There are three types of animals: horses, cows, and goats. The barn has a fixed number of stalls (partitions). These stalls are arranged in a single row, and are consecutive. Horses and cows are big, and each need 2 stalls. A goat is small, and only needs 1 stall. Stalls are not allowed to be empty. Assume that all horses are equivalent, all cows are equivalent, and all goats are equivalent. For example, in a barn with only 1 stall, you can only place 1 goat (G). In a barn with 2 stalls, you could have one horse (H), or one cow (C), or two goats (GG). In a barn with 3 stalls, there are 5 possible sequences: GGG, GH, GC, HG, CG. Find a recurrence relation that describes how many ways are there to arrange the animals into a barn with n stalls. Hint: think about the last animal in the row of stalls.