Ciąg zerojedynkowy

[karpadros]

Na ile sposobów mogę zbudować siedmioelementowy ciąg zerojedynkowy, taki że nie występują w nim trzy jedynki/trzy zera stojące obok siebie?

[Chromosom]

Zastosuj zasadę włączeń i wyłączeń.

[karpadros]

Hmm, no to siedmiowyrazowych ciągów zerojedynkowych mógłbym ułożyć na \(\displaystyle{ V_{2}^{7} = 2 ^{7} = 128}\) sposobów. Teraz muszę odjąć od tego wszystkie możliwe kombinacje z potrójnymi zerami i jedynkami, tak? No i w sumie z poczwórnymi zerami i jedynkami też, to samo dla piątek, szóstek i siódemek (dla których są tylko 2 możliwości, 0000000 i 1111111). To będą wariacje bez powtórzeń czy kombinacje? Nigdy nie potrafiłem tego odróżnić i zrozumieć.

[Chromosom]

Ciągi, w których występuje więcej niż 3 zera lub jedynki stojące obok siebie, można uwzględnić obliczając liczbę ciągów z trzema wystąpieniami takich samych liczb koło siebie. Należy obliczyć liczbę ciągów z trzema zerami oraz jedynkami obok siebie (liczba ta jest taka sama) i odjąć od ich sumy liczbę ciągów zawierających trzy zera i trzy jedynki obok siebie.

[karpadros]

Należy obliczyć liczbę ciągów z trzema zerami oraz jedynkami obok siebie (liczba ta jest taka sama)

Czyli liczba ciągów z trzema jedynkami/zerami (z reguły mnożenia) wynosi \(\displaystyle{ 1 ^{3} \cdot 2 ^{4} = 16}\), tak?

i odjąć od ich sumy liczbę ciągów zawierających trzy zera i trzy jedynki obok siebie.

Czyli \(\displaystyle{ 2 \cdot 16 - 8 = 32 - 8 = 24}\)? Bo mamy 8 takich ciągów w których trzy zera i trzy jedynki są obok siebie (111000X, 000111X, X000111, X111000, każdy z nich dwa razy). Ale czy to nie za mało?