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 air range the animals into a barn with n stalls