zasada wlaczen i wylaczen

[kriegor]

1. oblicz ile jest liczb \(\displaystyle{ 8}\)-cyfrowych nie zawierajacych cyfry \(\displaystyle{ 0}\) ani ciągu kolejnych cyfr \(\displaystyle{ …121….}\)

2. znajdz liczbe permutacji zbioru \(\displaystyle{ \{1,…,7\}}\) nie zawierajacych czterech kolejnych elementow w porządku rosnacym

nie idzie mi to pomoze ktoss ??

[Kartezjusz]

Liczb ośmiocyfrowych bez zera jest \(\displaystyle{ 9^{8}}\) Teraz usuńmy te,które nie mają 121.
Policzmy te,które mają jedynka z sekwencji może być na miejscach od 1 do 6 i jeśli wybierzemy
pozycję jedynki jako i ,to 2 będzie i+1,a druga jedynka i+2. Reszta cyfr bez przeszkód
\(\displaystyle{ 9^{8}-7 \cdot 9^{5}}\)

Wybierzmy na ile różnych rosnących ciągów czterocyfrowych można otrzymać . permutacji można otrzymać 7!.
pierwsza cyfra dowolnie, oprócz 5,6,7 bo braknie cyfr (4 sposoby)
druga cyfra (rozpatrujemy 4 przypadki w zależności co wylosowalismy pierwszego)
(Może być 4,3,2,1) w zależności od tego jaka była pierwsza cyfra(odpowiednio 1,2,3,4)
trzecia cyfra -zależy od drugiej też od( 3,6)-4 kolejne przypadki
i czwarta w zależnosci od trzeciej analogicznie.
Ten ciąg rosnący możemy wsadzić na jedno z 4 miejsc ( tak ,aby się zmieściła)
Rozrysuj drzewko i będziesz widzieć:)

[kriegor]

tak na dobra sprawe to ja do dzis nie potrafie tych zadan zrobic

sposob na zadanie pierwsze jest w sposob oczywisty zly bo liczymy kilka razy niektore ciagi
w drugim sie gubie i sadze ze i tak zaprowadzi mnie to do zlego wyniku

naprawde nie da sie tego jakos ladnie podstawic pod zasade wlaczen i wylaczen? chyba najwieksza w niej trudnosc to sensowne zdefiniowanie wlasnosci potem juz troche z gorki ale ja nawet tego nie potrafie zrbic co mnie troche irytuje bo pewnie jeszcze pare razy ta zasada bedzie mi potrzebna w zyciu

[TMac]

Nie jestem pewny tej metody, ale policzyłem nią zadanie pierwsze i wyszła duża, a co najważniejsze dodatnia liczba, co daje pewne nadzieje na jej poprawność

Zatem niech \(\displaystyle{ A _{i}}\) oznacza zbiór tych liczb ośmiocyfrowych bez zer, gdzie na pozycji \(\displaystyle{ i-1}\)-szej występuje jedynka, na \(\displaystyle{ i}\)-tej dwójka, a na \(\displaystyle{ i+1}\)-szej znów jedynka. Oczywiście \(\displaystyle{ i \in \left\{ 2,3,4,5,6,7\right\}}\), przyjmując, że zaczniemy numerowanie kolejnych cyfr od 1 (np. nie ma \(\displaystyle{ A_{8}}\), bo gdyby było to oznaczałoby, że na \(\displaystyle{ i+1 = 8+1 = 9}\) miejscu jest jedynka, a przecież nie ma 9. miejsca).
Teraz już można zastosować zasadę włączeń-wyłączeń, tylko trzeba zwrócić uwagę na jeszcze jedną rzecz - ile pozostaje miejsc do "wolnego" wyboru. Np. \(\displaystyle{ \left| A_{2} \right| = 9^{5}}\), bo mamy pierwsze 3 miejsca ustalone wg definicji zbioru, a na pozostałych ustawiamy co chcemy (oprócz zer), \(\displaystyle{ \left| A_{2} \cap A _{7} \right| = 9^{2}}\), bo ustalone są miejsca 1.,2.,3. oraz 6.,7.,8., więc pozostają do obsadzenia 4. i 5., ale już \(\displaystyle{ \left| A_{2} \cap A _{4} \right| = 9^{3}}\), bo mamy ustalone tylko 1.,2.,3.,4. i 5. miejsce w liczbie (czyli \(\displaystyle{ 12121...}\)), a 6.,7.,8. dobieramy.


Co do drugiego, to zależy jak interpretować treść. Czy np. konfiguracja \(\displaystyle{ \left(7,6,1,3,4,5,2\right)}\) jest dopuszczalna? Mamy tu cztery kolejne elementy w porządku rosnącym, ale nie są to cztery kolejne elementy zbioru (ja bym stawiał na to, że nie, no ale w sumie nie moje zadanie ). Jeśli dopuszczamy powyższe ustawienie to \(\displaystyle{ A_{i}}\) może być zbiorem, w którym od \(\displaystyle{ i}\)-tego miejsca są cztery elementy w porządku rosnącym, a jeśli nie to jest zbiorem, w którym elementy zbioru \(\displaystyle{ i,i+1,i+2,i+3}\) są w porządku rosnącym (ale wtedy już niekoniecznie tuż po sobie w permutacji (np. dopuszczamy \(\displaystyle{ \left( 6,5,1,2,3,7,4\right)}\), bo 1,2,3,4 są w porządku rosnącym i są kolejnymi elementami, według 1. definicji byśmy nie dopuścili, bo nie są tuż po sobie).

[kriegor]

w pierwszym chyba wlasnie o to chodzi tak cos czuje ale jakos nie bardzo tego wciaz czuje
strasznie duzo liczenia duzo tych przeciez zbiorow wychodzi w wyniku

w drugim liczymy permutacje ktore maja spojny podciag czteroelementowy (conajmniej w takim razie) rosnacy

\(\displaystyle{ \left(7,6,1,3,4,5,2\right)}\) oraz \(\displaystyle{ \left( 6,5,1,2,3,7,4\right)}\) sa liczone poniewaz da sie w nich znalezc kolejne cztery elementy w porzadku rosnacym i sa to kolejno: \(\displaystyle{ 1,3,4,5}\) oraz \(\displaystyle{ 1,2,3,7}\)-- 7 sie 2012, o 10:34 --strasznie ciezko to policzyc w drugim

[norwimaj]

strasznie ciezko to policzyc w drugim

To prawda.

\(\displaystyle{ 7!-4\cdot\binom74\cdot3!+3\cdot\binom75\cdot2!+2\cdot\binom76\cdot1!+1-7-1-1-7+1=4326.}\)

[kriegor]

dzieki moglem sprawdzic czy mam dobrze faktycznie teraz widze co mialem zle i kazdy czynnik sie zgadza wiec chyba zrozumialem choc jeszcze troche magii w tym jest

prosze sie nie smiac ale chyba nie polubie tej zasady bo jakos za duzo z nia roboty na szczescie w liceum nia nie katuja