This is the seventeenth puzzle in Matt Parker's Matt Parker's Maths Puzzles puzzle series
As the owner of a pet hotel, you have ten kennels in a row that you can put either a cat, or a dog into each night. Cats, being as they are, are not happy when placed adjacent to other cats. Dogs do not mind who they are next to though.
How many different ways are there to put cats and dogs into the ten kennels,