Zliczanie podziałów zbioru

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Zliczanie podziałów zbioru

Post autor: 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
Fachowiec
Fachowiec
Posty: 1070
Rejestracja: 07 maja 2010, 12:48
Podziękowania: 2 razy
Otrzymane podziękowania: 357 razy

Post autor: 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.
Korki z matmy, rozwiązywanie zadań
info na priv
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Post autor: 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
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Post autor: 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
Fachowiec
Fachowiec
Posty: 2946
Rejestracja: 20 gru 2013, 21:41
Lokalizacja: Radom
Otrzymane podziękowania: 1556 razy
Płeć:

Re: Zliczanie podziałów zbioru

Post autor: 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 )
ODPOWIEDZ