Galeria zdjęć interaktywnych

Polecenie 1

Zapoznaj się z przedstawioną poniżej galerią. Przeanalizuj zaprezentowane w niej rozwiązanie zadania dotyczącego wyznaczenia wszystkich permutacji zbioru $\{1, 2, 3, 4, 5, 6, 7\}$ , w których wyróżnione trzy elementy nie są zapisane obok siebie.

Rg2OloFSLmPc8

Ilustracja pierwsza. Liczba permutacji zadanie ze złożonymi warunkami. obliczmy ile jest wszystkich permutacji zbioru

\{1, 2, 3, 4, 5, 6, 7\}

w których żadne 2 spośród elementów 1 2 3 nie są zapisane obok siebie. Rozwiązanie. rozpatrujemy permutację

\{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}\}

zbioru,

\{1, 2, 3, 4, 5, 6, 7\}

która spełnia warunki zadania. Jeżeli permutacja

(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7})

spełnia warunki zadania, to liczby

1

2

3

muszą być w niej zapisane na miejscach, które nie sąsiadują ze sobą.

Rr2VpORvglMnY

ilustracja druga. Pierwszy sposób zauważmy że jeżeli już wyznaczymy liczby niesąsiadujących miejsc dla elementów 1 2 oraz 3 to w każdym z otrzymanych przypadków te 3 liczby umieścimy na przydzielonych miejscach na 3 silnia sposobów pozostałe 4 liczby rozmieścimy na pozostałych miejscach na 4 silnia sposobów. ustalmy zatem ile nie sąsiadujących ze sobą miejsc dla elementów 1 2 oraz 3. Rozmieszczamy wtedy elementy

1

2

3

na przyporządkowanych im trzech miejscach oraz elementy

4

5

6

7

na przyporządkowanych im pozostałych czterech miejscach.

R1Kom6kQOsZlu

Ilustracja trzecia. Jeżeli pierwszym od lewej z tych miejsc jest x indeks dolny jeden koniec jak indeksu to pozostałe 2 miejsca wybierzemy na 6 sposobów. Razem z

x_{1}

wybieramy miejsca:
,

x_{3}

oraz

x_{5}

,
,

x_{3}

oraz

x_{6}

,
,

x_{3}

oraz

x_{7}

,
,

x_{4}

oraz

x_{6}

,
,

x_{4}

oraz

x_{7}

,
,

x_{5}

oraz

x_{7}

.Jeśli pierwszym od lewej z tych miejsc jest x indeks dolny 2 koniec indeksu to tu pozostałe 2 miejsca wybierzemy na kolejne 3 sposoby. Razem z

x_{2}

wybieramy miejsca:
,

x_{4}

oraz

x_{6}

,
,

x_{4}

oraz

x_{7}

,
,

x_{5}

oraz

x_{7}

.Jeśli pierwszym od lewej z tych miejsc jest x indeks dolny 3 koniec indeksu to pozostałe 2 miejsca wybierzemy już tylko na jeden sposób . Razem z

x_{3}

wybieramy

x_{5}

oraz

x_{7}

. Poza wymienionymi nie ma innych możliwości wyboru miejsc dla elementów 1, 2, trzy.

R8uGMq3iSNUis

Ilustracja czwarta. Podsumowując stwierdzamy że jest 10 możliwości rozmieszczenia w rozpatrywanej permutacji elementów 1 2 oraz 3 na nie sąsiadujących miejscach. Pojawia się tabela 7 na dziesięć. W kolumnie pierwszej zaznaczono wiersze od 1 do 6, w kolumnie drugiej zaznaczono wiersze od 7 do dziewięć, w kolumnie trzeciej zaznaczono wiersze od 1 do trzech oraz dziesiąty. W kolumnie 4 zaznaczono wiersze 4,5,7 oraz osiem. W kolumnie piątej zaznaczono wiersze 1,6, 9 oraz dziesięć. W kolumnie szóstej zaznaczono wiersze 2,4 oraz siedem. W kolumnie siódmej zaznaczono wiersze 3,5,6 oraz 8,9, dziesięć. Wobec tego wszystkich permutacji spełniających warunki zadania jest

10 \cdot 3! \cdot 4! = 1440

. Korzystamy z reguły mnożenia:

10 \cdot 3! \cdot 4! = 10 \cdot 6 \cdot 24 = 1440

. odpowiedź jest 1440 permutacji zbioru w których żadne 2 spośród elementów jeden, 2,3 nie są zapisane obok siebie

R1N4hQZRSehGG

Ilustracja piąta. drugi sposób jeśli wyznaczymy liczbę ka wszystkich permutacji w których przynajmniej 2 spośród elementów jeden, 2,3 zapisane są na sąsiednich miejscach to na tej podstawie obliczymy że permutacji zbioru

\{1, 2, 3, 4, 5, 6, 7\}

w których żadne 2 spośród elementów jeden, 2,3 nie są zapisane obok siebie jest

7! - k

. Wszystkich permutacji siedmioelementowego zbioru

\{1, 2, 3, 4, 5, 6, 7\}

jest

7! = 5040

R1C1knTMYig5x

Ilustracja szósta. Aby obliczyć rozpatrzmy 2 rozłączne przypadki. przypadek pierwszy elementy jeden, 2,3 znajdują się na 3 sąsiednich miejscach w tym przypadku mamy

5 \cdot 3! \cdot 4! = 720

możliwości wyboru. Elementy

1

2

oraz

3

mogą być przypisane do miejsc:

x_{1}

x_{2}

x_{3}

lub

x_{2}

x_{3}

x_{4}

lub

x_{3}

x_{4}

x_{5}

lub

x_{4}

x_{5}

x_{6}

lub

x_{5}

x_{6}

x_{7}

.

Te trzy elementy rozmieścimy na przydzielonych im trzech miejscach na

3! = 6

sposobów, a pozostałe cztery elementy rozmieścimy na pozostałych czterech miejscach na

4! = 24

sposoby.

R1BWK15tFv3gd

Ilustracja siódma. Przypadek drugi. 2 spośród 3 elementów jeden, 2,3 znajdują się na dwóch sąsiednich miejscach a trzeci z tych elementów jest na miejscu nie sąsiadującym z nimi w tym przypadku najpierw ustalimy na ilu miejscach można rozmieścić ten jeden z trzech elementów spośród jeden, 2,3 który nie sąsiaduje z parą dwóch pozostałych elementów tej trójki zapisanych na sąsiednich miejscach. Jeśli już będziemy znali liczbę tych możliwości, to w każdym z otrzymanych przypadków ten jeden niesąsiadujący element wybierzemy z trzech dostępnych

1

2

3

na trzy sposoby, dwa pozostałe na przydzielonych im miejscach rozmieścimy na

2! = 2

sposoby, a pozostałe cztery miejsca uzupełnimy na

4! = 24

sposoby. Rozdzielamy tym przypadek na dwa.

RNt1u3xrrr1Xn

Ilustracja ósma. Dwa kropka jeden. Gdy dwa sąsiadujące elementy wybrane spośród 1,2,3 zajmują 2 skrajne miejsca w permutacji to znaczy miejsca x indeks dolny jeden koniec indeksu i x indeks dolny 2 koniec indeksu lub x indeks dolny 6 koniec indeksu i x indeks dolny 7 koniec indeksu wówczas mamy

4 \cdot 2 = 8

możliwości wyboru miejsc. Dla trzeciego z tych elementów mamy za każdym razem cztery miejsca do wyboru; w sumie jest więc

4 \cdot 2 = 8

możliwości wyboru miejsc.

RYvqzpbZI3Bj9

Ilustracja dziewiąta. Dwa kropka dwa. Gdy 2 sąsiadujące elementy wybrane spośród 1,23 zajmują miejsca x indeks dolny 2 koniec indeksu i x indeks dolny 3 koniec indeksu lub x indeks dolny 3 koniec indeksu i x indeks dolny 4 koniec indeksu lub x indeks dolny 4 koniec indeksu lub x indeks dolny 5 koniec indeksu lub x indeks dolny 5 koniec indeksu i x indeks dolny 6 koniec indeksu wtedy mamy

3 \cdot 4 = 12

możliwość wyboru miejsc. Dla trzeciego z nich mamy za każdym razem trzy miejsca do wyboru; w sumie jest więc

3 \cdot 4 = 12

możliwości wyboru miejsc. Zatem ogółem miejsc do wyboru jest

8 + 12 = 20

a więc w przypadku drugim wszystkich permutacji jest

20 \cdot 3 \cdot 2! \cdot 4! = 2880

(8 + 12) \cdot 3 \cdot 2! \cdot 4! = 20 \cdot 3 \cdot 2 \cdot 24 = 2880

RkFwgo3dpTF30

ilustracja dziesiąta. Oznacza to że

k = 720 + 2880 = 3600

}Sumujemy liczby wszystkich permutacji, które nie spełniają warunków zadania. Oznacza to że wszystkich permutacji które spełniają warunki zadania jest

5040 - 3600 = 1440

. Dla obliczonego

k = 3600

otrzymujemy

7! - k = 5040 - 3600 = 1440

. odpowiedź. Jest 1440 permutacji zbioru w których żadne 2 spośród elementów 1,2 i 3 nie są zapisane obok siebie

Polecenie 2

Rozumując podobnie, jak w rozwiązaniu zadania omówionego w powyższej animacji oblicz, ile jest wszystkich permutacji zbioru $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ , w których elementy $2$ , $4$ , $6$ , $8$ nie są zapisane obok siebie.

Zauważmy, że jeżeli wyznaczymy liczbę niesąsiadujących miejsc dla elementów $2$ , $4$ , $6$ oraz $8$ , to w każdym z otrzymanych przypadków te cztery liczby rozmieścimy na przydzielonych miejscach na $4! = 24$ sposoby, a pozostałe pięć liczb rozmieścimy na pozostałych miejscach na $5! = 120$ sposobów.

Wybierając niesąsiadujące miejsca dla czterech rozdzielanych elementów $2$ , $4$ , $6$ , $8$ , mamy następujące, rozłączne przypadki:

$(1.1)$ jeżeli dwa z nich zajmą w permutacji miejsca $1$ oraz $3$ , to:
- jeżeli trzeci zajmie miejsce numer $5$ , to dla czwartego pozostają do wyboru trzy miejsca: $7$ lub $8$ , lub $9$ ,
- jeżeli trzeci zajmie miejsce numer $6$ , to dla czwartego pozostają do wyboru dwa miejsca: $8$ lub $9$ ,
- jeżeli trzeci zajmie miejsce numer $7$ , to dla czwartego pozostaje tylko jedno miejsce, numer $9$ ;
  w tym przypadku mamy więc ogółem $6$ możliwości;
$(1.2)$ jeżeli dwa z nich zajmą w permutacji miejsca $1$ oraz $4$ , to:
- jeżeli trzeci zajmie miejsce numer $6$ , to dla czwartego pozostają do wyboru dwa miejsca: $8$ lub $9$ ,
- jeżeli trzeci zajmie miejsce numer $7$ , to dla czwartego pozostaje tylko jedno miejsce, numer $9$ ;
  w tym przypadku mamy więc ogółem $3$ możliwości;
$(1.3)$ jeżeli dwa z nich zajmą w permutacji miejsca $1$ oraz $5$ , to dla trzeciego pozostaje miejsce numer $7$ , a dla czwartego pozostaje miejsce numer $9$ ;
- w tym przypadku mamy więc tylko $1$ możliwość;
$(2.1)$ jeżeli dwa z nich zajmą w permutacji miejsca $2$ oraz $4$ , to:
- jeżeli trzeci zajmie miejsce numer $6$ , to dla czwartego pozostają do wyboru dwa miejsca: $8$ lub $9$ ,
- jeżeli trzeci zajmie miejsce numer $7$ , to dla czwartego pozostaje tylko jedno miejsce, numer $9$ ;
- w tym przypadku mamy więc ogółem $3$ możliwości;
$(2.2)$ jeżeli dwa z nich zajmą w permutacji miejsca $2$ oraz $5$ , to dla trzeciego pozostaje miejsce numer $7$ , a dla czwartego pozostaje miejsce numer $9$ ;
- w tym przypadku mamy więc tylko $1$ możliwość;
$(3.1)$ jeżeli dwa z nich zajmą w permutacji miejsca $3$ oraz $5$ , to dla trzeciego pozostaje miejsce numer $7$ , a dla czwartego pozostaje miejsce numer $9$ ;
- w tym przypadku mamy więc tylko $1$ możliwość.

Wobec tego wszystkich możliwości rozmieszczenia w rozpatrywanej permutacji elementów $2$ , $4$ , $6$ , $8$ na niesąsiadujących miejscach jest
$6 + 3 + 1 + 3 + 1 + 1 = 15$ .

Oznacza to, że wszystkich permutacji spełniających warunki zadania jest $15 \cdot 5! \cdot 4! = 15 \cdot 120 \cdot 24 = 43200$ .

$43200$

Przeczytaj

Sprawdź się