5. Suppose that we are putting animals in a barn. There are three types of anima

Question

5. 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.

Explanation / Answer

For finding the reccurence relation lets analyze the pattern :

for 1 stall : 1 way

for 2 stalls : 3 ways (H,C,GG)

for 3 stalls : 5 ways (GGG, GH, GC, HG, CG.)

for 4 stallls : 9 ways (GGGG,HH,CC,GGC,GGH,CGG,HGG,GCG,GHG)

hence, we can see the relation is of type 20+1, 21+1, 22+1.........

so we can deduce the relation as an = 2n-1+1

Bingo!!!

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.