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 ?
Zliczanie podziałów zbioru
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Fachowiec
- Posty: 1070
- Rejestracja: 07 maja 2010, 12:48
- Podziękowania: 2 razy
- Otrzymane podziękowania: 357 razy
-
- Fachowiec
- Posty: 985
- Rejestracja: 18 paź 2010, 20:45
- Podziękowania: 509 razy
- Otrzymane podziękowania: 4 razy
- Płeć:
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.
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.
-
- Fachowiec
- Posty: 2946
- Rejestracja: 20 gru 2013, 21:41
- Lokalizacja: Radom
- Otrzymane podziękowania: 1556 razy
- Płeć:
Re: Zliczanie podziałów zbioru
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 )
\(\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 )