Zliczanie podziałów zbioru
: 29 sie 2014, 19:02
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 ?
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 ?