N-wyrazowy ciąg bez trzech jedynek

[acmilan]

Ile jest możliwych ustawień zer i jedynek w n-wyrazowy ciąg tak, żeby nigdy trzy jedynki nie stały koło siebie?

[frej]

Można z metody włączeń i wyłączeń. Wtedy przyjąć własność \(\displaystyle{ A_i = \{ \text{na miejscach } i, i+1, i+2 \text{ stoją jedynki } \}}\). Trzeba zatem policzyć \(\displaystyle{ 2^n - \left| A_1 \cup A_2 \cup \ldots \cup A_{n-2}\right|}\)

[acmilan]

Super, tylko że w ten sposób \(\displaystyle{ A_i \cap A_j \neq 0}\) i nie wiadomo jak policzyć moc tej sumy zbiorów.