Art, the mail carrier delivers mail to the 19 houses on the east side of a street.

Art notices that:

(i) No two adjacent houses ever get mail on the same day, and:

(ii) There are never more than two houses in a row that get no mail on the same day.

How many distinct patterns of mail delivery are possible?

(In reply to

a manual count solution by Ady TZIDON)

Well, I wasn't going to post my solution, but I love disagreeing with Ady, so here it is. Ady has correctly identified the 151 distribution patterns that end with a 1. There are also 114 that end with a single 0 and 86 that end in 00. 151 + 114 + 86 = **351**, which is my answer.

I got my solution iteratively, using Excel.

Let f(n) be the number of strings of length n that end with a 1.

Let g(n) be the number of strings of length n that end with a single 0.

Let h(n) be the number of strings of length n that end with a double 0.

Then f(n+1) = g(n) + h(n)

g(n+1) = f(n)

h(n+1) = g(n)

My Excel table looked as follows:

n f(n) g(n) h(n) Total

1 1 1 0 2

2 1 1 1 3

3 2 1 1 4

4 2 2 1 5

5 3 2 2 7

6 4 3 2 9

7 5 4 3 12

8 7 5 4 16

9 9 7 5 21

10 12 9 7 28

11 16 12 9 37

12 21 16 12 49

13 28 21 16 65

14 37 28 21 86

15 49 37 28 114

16 65 49 37 151

17 86 65 49 200

18 114 86 65 265

19 **151** 114 86 **351**