Zliczanie podziałów zbioru

[tukan]

Witam,

Trzeba podzielić zbiór {1,...,n} na 3 bloki (niepuste), ale tak że w żadnym bloku nie ma sąsiednich liczb, tzn 1 i 2 nie sa w tym samym bloku. Czwórka nie może być z piątką i szóstką itd.

I trzeba zliczyć takie podziały:
Moja idea jest taka:
Przyjrzę się elementom 1,2,3:
{1}{2}{3}
lub
{1,3}{2}{jakiś dowolny element spośród {4,5,...n}}

I teraz dla każdego z pozostałych elementów podejmuję decyzję, do którego bloku go wsadzić. Dla każdego mogę podjąć decyzję na dwa sposoby, ostatecznie dostanę:
\(2^{n-3} + (n-3)2^{n-4}\)

Czy to jest wg Was ok ?

[Crazy Driver]

Nie rozumiem Twojego sposobu obliczenia. Nie rozumiem w jaki sposób wiążesz rozkład liczb \(1, 2, 3\) w blokach, z pozostałymi liczbami.

[tukan]

Patrz, musisz porozkładać \(n\) liczb.

Jedynka nie może być w zbiorze z dwójką. Dwójka nie może być ani z jedynką, ani z trójką. W ten sposób są dwa przypadki:
(1) jedynka razem z trójką, dwójka osobno.
(2)jedynka, trójka, dwójka osobno.

Jeśli pierwszy przypadek to jeden z bloków jest pusty. Muszę wpakować tam jedną liczbę - bo nie tolerujemy bloków pustych.
Wybieram taką liczbę na \(n-3\) sposoby, bo \((1,2,3)\) już porozkładałem.
Dalej zostało mi \(n-4\) liczb.
I teraz dla każdego z nich mogę wsadzić do jednego z dwóch bloków - jeden jest zablokowany - a to dlatego, że mamy ten warunek w zadaniu.

Czyli \((n-3) \cdot 2^{n-4}\)


(2) nie ma już pustego bloku, a więc mamy \(2^{n-3}\) sposoby.

[tukan]

Pomyliłem się, prawidłowy wynik to :

\(2^{n-2}-1\)

Otrzymałem go na dwa różne sposoby więc się zgadza.

[Panko]

Realizacje dla \(n=5\)
\(\left\{ 1,3,5\right\} , \left\{ 2\right\}, \left\{4\right\}\)
\(\left\{ 1,3\right\} , \left\{ 2,4\right\} , \left\{ 5\right\}\)
\(\left\{ 1,4\right\} , \left\{ 2,5\right\} , \left\{ 3\right\}\)
\(\left\{ 1,4\right\} , \left\{ 5,3\right\} , \left\{ 2\right\}\)
\(\left\{ 1,5\right\} , \left\{ 2,4\right\} , \left\{ 3\right\}\)
\(\left\{ 2,4\right\} , \left\{ 3,5\right\} , \left\{ 1\right\}\)
\(\left\{ 2,5\right\} , \left\{ 1,3\right\} , \left\{ 4\right\}\)
Fakt Bo tu jest ich siedem. ( ale tylko dla n=5 )