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
re: a manual count solution
