Matematyka dyskretna

© Andrzej Łachwa, UJ, 2013

[e-mail]

9/15

Zadanie *

Przyjmujemy, że dwa numery rejestracyjne są podobne, gdy reprezen-
tujące je zbiory znaków są takie same. Ile różnych niepodobnych
numerów rejestracyjnych można utworzyć, jeśli pierwszą literą jest K,
pozostałe dwie należą do zbioru {R, W, T, A}, a potem występuje pięć
cyfr?

Część literową można utworzyć wybierając jedną literę, np. KRR, i można
to zrobić na 4 sposoby. Można też wybrać dwie litery ze zbioru 4-
elementowego. Uwaga: wybór liter R, A pozwala na utworzenie numerów
podobnych KRA i KAR. Mamy zatem 4+6 możliwych wyborów. Część
numeryczną rozwiążemy jako osobne „pod-zadanie”.

Pod-zadanie **

Tworzymy 5-cyfrowe hasła (z cyfr 0, 1, … 9). Hasła uważamy za podobne,
gdy zbiory cyfr, z których się składają są takie same. Np. hasło 27311 jest
podobne do hasła 77312, bo ich zbiory cyfr to {1,2,3,7}.

Ile jest niepodobnych haseł?

Rozwiązanie pierwsze

Klasy haseł o 5 różnych cyfrach można utworzyć na













5

10

sposobów.

Zbiór haseł o 4 takich samych cyfrach składa się z haseł, w których jedna
cyfra powtarza się dwukrotnie. Każdą taką klasę haseł można utworzyć
przez wybór cyfry powtarzającej się i wybór trzech innych cyfr, czyli na

840

3

9

10

=













⋅

sposobów.

Każda klasa haseł o 3 cyfrach składa się z haseł, w których albo dwie cyfry
występują dwukrotnie, albo jedna cyfra występuje trzykrotnie. Klasę
pierwszego rodzaju można wybrać na

720

8

9

10

=

⋅

⋅

sposobów, bo

najpierw wybieramy cyfrę pojedynczą, potem inną cyfrę podwójną i

znowu jeszcze inną cyfrę podwójną. Klasę drugiego rodzaju na













⋅

2

9

10

sposobów, bo ...

To rozwiązanie nie jest poprawne!

Permutacje

Permutacja zbioru skończonego X to bijekcja z X w X. Zbiór permutacji
zbioru

oznaczamy przez , a permutacje małymi literami greckimi.

Np. rozważ funkcję

zadaną przez poniższą tabelę:

Funkcja jest bijekcją z

w

, zatem jest permutacją i

.

Dla dowolnych permutacji

skończonego zbioru X złożenia

są

permutacjami X, oraz

jest permutacją X taką, że jej złożenie z α daje

funkcję identycznościową.

Zbiór n-elementowy ma dokładnie n! permutacji, czyli

.

Niech

α

będzie permutacją n-elementowego zbioru X.

Cykl zbioru n-elementowego X to taka permutacja zbioru X, dla której

, przy dowolnym

.

Łatwo zauważyć, że jeśli dla pewnego

zachodzi powyższa

równość, to jest tak dla wszystkich

, czyli

α

jest cyklem na X.

Weźmy bowiem {

α

(x),

α

2

(x), …

α

n

-1

(x),

α

n

(x)}. Ten zbiór jest równy X, bo

jest to

α

(X). Zatem

α

n

(x)=x.

Cykl

α

zbioru X zapisujemy jako

dla dowolnie

wybranego

.

Niech

α

będzie permutacją n-elementowego zbioru X. Permutację

α

nazywamy cyklem k-elementowym (k

≤

n

) jeżeli dla pewnego

k

-elementowego podzbioru I={i

1

, i

2

, … i

k

} zbioru X zachodzi

α

( i

1

)= i

2

,

α

( i

2

)= i

3

, …

α

( i

k-

1

)= i

k

,

α

( i

k

)= i

1

oraz

α

(i)= i dla wszystkich i

∉

I.

Piszemy wtedy

α

=(i

1

, i

2

, … i

k

), ale również

α

=( i

2

, i

3

, … i

k

, i

1

) …

Permutacja tożsamościowa to cykl 1-elementowy!

Dwa cykle nazwiemy rozłącznymi jeżeli ich zbiory wskaźników nie mają
wspólnych elementów.

Rozważmy

daną przez

Sekwencja ,

,

,

,

,

pokrywa

całe

, zatem

jest cyklem.

ROZKŁAD PERMUTACJI NA ROZŁĄCZNE CYKLE

Dowolną permutację

α

zbioru X można rozłożyć na rozłączne cykle

w sposób następujący:

wybierz dowolny element

, który nie jest jeszcze w żadnym

cyklu,

iteruj permutację

α

otrzymując kolejno:

aż do

uzyskania

,

dodaj do rozkładu cykl

,

jeśli w zbiorze X pozostały jeszcze elementy niepokryte przez żaden

cykl, to wróć do pierwszego punktu.

Jeśli permutacja

α

złożona jest z k rozłącznych cykli, to zapisujemy

, gdzie w kolejnych nawiasach są

elementy kolejnych cykli startujące od odpowiednio:

.

Przykład: Rozważmy jeszcze raz permutację

:

Rozkład

α

na cykle:

,

,

,

,

,

,

,

,

,

.

ZADANIE

Ile jest tras wycieczkowych odwiedzających kolejno 3 miejscowości?

Odp: 3!=6

ZADANIE

Na ile sposobów można rozstawić 8 wież na ponumerowanych polach
szachownicy 8x8 w taki sposób, by żadne dwie nie znajdowały się w polu
wzajemnego rażenia?

Rozważamy rozłożenia ośmiu wież, w taki sposób aby w każdej linii i w
każdej kolumnie znajdowała się dokładnie jedna wieża. Każde takie
rozłożenie jednoznacznie wyznacza bijekcję ze zbioru wierszy
w zbiór kolumn

. Jest ich zatem

.

ZADANIE

Ile jest par postaci

, gdzie

, gdy

?

Dla pary

rozważ funkcję

zdefiniowaną jako:

i wywnioskuj, że

.

k=1…n

OSZACOWANIE GAUSSA

(n!)

2

=

∏

k(n+1–k), przy czym najmniejszy z tych czynników ma wartość n

a największy dla k =

(n+1)/2 ma wartość (n+1)

2

/4

zatem n

n

≤

(n!)

2

≤

((n+1)

2

/4)

n

i stąd oszacowanie

n

n

n

n

n













+

≤

≤

2

1

!

2

.

Np. 11

5,5

≤ 11! ≤ 6

11

czyli 534 146 ≤ 39 916 800 ≤ 362 797 056

Pod-zadanie ** – cd

Zbiór cyfr 5-cyfrowego hasła może mieć od 5 do 1 elementów. Każdy taki
zbiór reprezentuje klasę haseł podobnych. Trzeba więc dodać do siebie
liczby podzbiorów pięcio, cztero, trzy, dwu i jednoelementowych:

252

5

10

=













,

210

4

10

=













,

120

3

10

=













,

45

2

10

=













,

10

1

10

=













Szukanych klas jest 252+210+120+45+10 = 637.

Rozwiązanie * w całości

Część literową można utworzyć wybierając jedną literę, np. KRR, i można
to zrobić na 4 sposoby. Można też wybrać dwie litery ze zbioru 4-
elementowego. Uwaga: wybór liter R, A pozwala na utworzenie numerów
podobnych KRA i KAR. Mamy zatem 4+6 możliwych wyborów.

Część numeryczną reprezentuje co najwyżej 5-elementowy podzbiór
zbioru 10-elementowego.

Mamy zatem

(4+













2

4

)(













5

10

+













4

10

+













3

10

+













2

10

+













1

10

) = 10

⋅⋅⋅⋅

(252+210+120+45+10) = 6370

W rozwiązaniu pierwszym – wadliwym: wybór grupy haseł 4-cyfrowych
polegał na wyborze cyfry powtarzającej się, a następnie 3 cyfr z
pozostałych dziewięciu. Wybór taki można dla konkretnego przypadku
oznaczyć jako {8, {7, 6, 5}}, a różnych grup jest 840.

W rozwiązaniu poprawnym odpowiedni wybór możemy oznaczyć jako
{8, 7, 6, 5}, a różnych grup jest 210. Dlaczego jest ich 4 razy mniej?

Bo grupa {8, 7, 6, 5} składa się z haseł podobnych należących do 4
podgrup postaci:

{8, {7,6,5}}
{7, {8,6,5}}
{6, {8,7,5}}
{5, {8,7,6}} .

A gdyby to były hasła 3-cyfrowe?

Wtedy dodajemy

120

3

10

=













,

45

2

10

=













,

10

1

10

=













, czyli 120+45+10=175.

Dla takich 3-cyfrowych haseł policzmy ile jest elementów w każdej
grupie haseł podobnych?

Na przykład niech „345” oznacza grupę haseł złożonych z tych trzech cyfr.
Można je uporządkować na 3! sposobów, więc w każdej takiej grupie jest
6 haseł podobnych. Niech „34” oznacza grupę haseł złożonych tylko z
dwóch takich cyfr. Należą do niej 334, 343, 433, 443, 434, 344, czyli 6
haseł. Niech „3” oznacza grupę haseł zbudowanych z cyfry 3. Należy do
niej tylko jedno hasło.

Sprawdzamy: 120 grup po 6 haseł i 45 grup po 6 haseł i 10 grup po 1 haśle
daje łącznie 720+270+10=1000. I to się zgadza, bo 3-cyfrowych liczb
dziesiętnych jest 10

3

.

Przeprowadźmy podobne rozumowanie dla haseł 4-cyfrowych.

Mamy

210

4

10

=













,

120

3

10

=













,

45

2

10

=













,

10

1

10

=













grup cztero, trzy, dwu i

jednoelementowych, łącznie 210+120+45+10 = 385 grup.

W każdej grupie typu „2345” mamy 4! różnych haseł. W grupie typu
„234” – 36 haseł, bo na 3 sposoby wybieramy cyfrę, która wystąpi
dwukrotnie (np. będzie to cyfra 4), pozostałe dwie cyfry mogą wystąpić w
różnej kolejności (2 przypadki: 23 i 32), a wybraną cyfrę można wstawić
do każdej pary cyfr na 6 sposobów (4423, 4243, 4234, 2443, 2434, 2344).
W grupie typu „56” będzie 14 haseł, bo 8 haseł z potrojoną cyfrą (5556,
5565, 5655, 6555, 6665, 6656, 6566, 5666) i 6 haseł z podwojonymi
cyframi (5566, 5656, 5665, 6655, 6565, 6556). I na koniec w grupie typu
„5” będzie jedno hasło postaci 5555.

Sprawdzamy: 210

⋅

24+120

⋅

36+45

⋅

14+10=5040+4320+630+10=10000.

I dla haseł 5-cyfrowych.

W każdej grupie typu „34567” mamy 5! różnych haseł, a grup takich jest

252

5

10

=













, łącznie mamy tu 252

⋅

120=30240.

Grup typu „3456” jest

210

4

10

=













, a w każdej z nich jest 240 haseł, mamy

bowiem 4!=24 permutacje i dla każdej z nich 10 haseł (np. dla permutacji
6543 mamy hasła 66543, 65643, 65463, 65436, 65543, 65453, 65435,
65443, 65434, 65433). Łącznie jest tu 210

⋅

24

⋅

10=50400.

Grup typu „345” jest

120

3

10

=













. Każdą taką grupę podzielimy na podgrupę

z potrojoną cyfrą i podgrupę z dwoma podwojonymi cyframi. W pierwszej
z nich najpierw wybieramy potrojoną cyfrę (3 sposoby wyboru), następnie
ustalamy kolejność dwóch pozostałych (2 sposoby) i wstawiamy cyfrę
potrojoną na 10 sposobów. Razem jest w takiej podgrupie 60 haseł.

Przykład: potrojona niech będzie cyfra 5, a wybrana kolejność
pozostałych, to 34. Wtedy mamy hasła: 55534, 55354, 55345, 53554,
53545, 53455, 35554, 35545, 35455, 34555.

W drugiej podgrupie mamy 90 haseł. Bierze się to stąd, że najpierw
wybieramy cyfrę niepodwojoną (3 sposoby). Dalej, cyfry podwojone mogą
utworzyć ciągi 3355, 3535, 3553, 5335, 5353, 5533. Do każdego z tych
ciągów można wstawić cyfrę niepodwojoną na 5 sposobów, np. do ciągu
3355 wstawiamy cyfrę 4: 43355, 34355, 33455, 33545, 33554.

Każda grupa typu „345” ma ostatecznie 150 haseł. Razy 120 grup daje
nam 18000 haseł.

Grup typu „34” jest

45

2

10

=













, a w każdej z nich jest 30 haseł. Jest tak

dlatego, że 5-elementowych łańcuchów z dwóch znaków można
zbudować 2

5

czyli 32, ale dwa z nich nas nie interesują (33333, 44444).

Wreszcie grup typu „3” jest 10.

Sprawdzamy: 30240+210

⋅⋅⋅⋅

240+120

⋅⋅⋅⋅

(60+90)+45

⋅⋅⋅⋅

30+10=30240+50400+18000+1350+10 = 100 000.

GENEROWANIE PERMUTACJI

Algorytm 1: Aby wygenerować n! permutacji wygeneruj wszystkie (n-1)!
permutacji zaczynających się od 1, potem od 2, … i na koniec od n.

1

234

2

134

3

124

1

243

2

143

3

142

1

324

2

314

…

1

342

2

341

1

423

2

413

1

432

2

431

Algorytm 2: Aby wygenerować n! permutacji wygeneruj wszystkie (n-1)!
permutacji zbioru {2, … n} i umieść 1 na pierwszej pozycji każdej z nich.
Powtórz to umieszczając 1 na drugiej pozycji, itd. aż do n-tej pozycji.

1

234

2

1

34

23

1

4

1

243

2

1

43

24

1

3

1

324

3

1

24

…

1

342

4

1

23

1

423

3

1

42

1

432

4

1

32

Algorytm 3: Aby wygenerować n! permutacji wygeneruj wszystkie (n-1)!
permutacji zbioru {2, … n}. Dla każdej z tych permutacji umieść 1 na
kolejnych n możliwych pozycjach.

1

234

1

324

1

342

2

1

34

3

1

24

3

1

42

23

1

4

32

1

4

…

234

1

324

1

i = 0 … n-1

Generowanie podzbiorów

Weźmy n-elementowy zbiór X={x

1

, x

2

… x

n

}. Każdemu podzbiorowi Y

⊂

X

przyporządkujemy ciąg binarny b

0

b

1

… b

n-1

określony następująco:







∈

∉

=

+

+

Y

x

Y

x

b

i

i

i

1

1

:

1

:

0

Otrzymujemy wtedy wzajemnie jednoznaczną odpowiedniość pomiędzy
elementami P(X) a ciągami binarnymi długości n, czyli liczbami binarnymi

z przedziału [0, 2

n

–1] postaci

∑

b

i

2

i

oznaczanymi dalej przez [b

n

-1

… b

0

].

Ciąg binarny stanowi wygodną reprezentację maszynową podzbioru X,
a kolejne liczby binarne określą wszystkie podzbiory zbioru X.

W wielu sytuacjach zależy nam, by kolejny generowany podzbiór niewiele
różnił się od poprzedniego. W tym celu zamiast kolejnych liczb binarnych
generuje się kolejne liczby tzw. kodu Greya.

Kod ten powstaje w wyniku zastosowania następującej obserwacji:

Jeżeli ciąg C

1

, C

2

, … C

m

zawiera wszystkie 2

k

ciągi binarne długości k, przy

czym C

i

różni się od C

i

+1

na dokładnie jednej pozycji (i=1, 2 … m-1), to ciąg

postaci C

1

0, C

2

0, … C

m

0, C

m

1, C

m

-1

1, … C

1

1 zawiera wszystkie ciągi binarne

długości k+1 oraz każde dwa sąsiednie ciągi binarne różnią się na
dokładnie jednej pozycji.

Przykład dla k=4

0000, 1000, 1100, 0100, 0110, 1110, 1010, 0010,

0011, 1011, 1111, 0111, 0101, 1101, 1001, 0001.

ZBIÓR Z POWTÓRZENIAMI

A

=B wtw gdy mają te same elementy w tych samych krotnościach.

A

⊂

B

wtw jeśli każdy element z A występuje w B (krotność każdego

elementu w A jest nie większa od krotności tego elementu w B).

Niech X zawiera elementy x

1

, x

2

, … x

n

, odpowiednio o krotnościach

k

1

, k

2

, … k

n

. Licznością zbioru X nazwiemy sumę krotności, czyli

|X| = k

1

+ k

2

+ … + k

n

.

Każdemu podzbiorowi A

⊂

X

odpowiada jednoznacznie ciąg (m

1

, … m

n

),

gdzie 0

≤

m

1

≤

k

1

, … 0

≤

m

n

≤

k

n

.

Wniosek: wszystkich podzbiorów torby X jest (k

1

+1)∙(k

2

+1)∙ … ∙(k

n

+1).

Generowanie podzbiorów można przeprowadzić w sposób podobny do
tego opartego na kodzie Greya.

Zliczanie relacji

Ile jest różnych relacji binarnych określonych na skończonym zbiorze X?

Każda taka relacja jest podzbiorem X

×

X

. Jest więc tych relacji tyle, co

różnych podzbiorów X

2

, czyli 2

nn

.

Każdą relację na X można przedstawić w postaci kwadratowej tablicy,
a liczba relacji to liczba możliwych układów jedynek w takiej tablicy.

A jeśli chcielibyśmy policzyć tylko relacje zwrotne?

Każda relacja zwrotna ma jedynki na przekątnej, w pozostałych miejscach
mogą być zera lub jedynki. Tych pozostałych miejsc jest n

2

–n, więc relacji

zwrotnych jest 2

n

(n-1)

.

Ile jest różnych relacji symetrycznych?

Relacja symetryczna ma dowolnie wypełnione pole na przekątnej i pod
przekątną. Nad przekątną musi się znaleźć lustrzane odbicie układu pod
przekątną. Relację symetryczną możemy więc określić wpisując jedynki do

n

(n+1)/2 pól, relacji takich jest więc 2

n

(n+1)/2

.

Ile jest relacji równoważności?

Każda taka relacja to podział na bloki (klasy abstrakcji). Liczba podziału
zbioru n-elementowego na k bloki to tzw. liczba Stirlinga drugiego
rodzaju.

Liczba wszystkich podziałów zbioru n-elementowego (liczba wszystkich
relacji równoważności) to tzw. liczba Bella. Jest to suma n-tego wiersza
trójkąta Stirlinga dla podziałów.