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.