KOMBINATORYKA
KOMBINATORYKA
Dział matematyki zajmujący się badaniem różnych możliwych zestawień i
ugrupowań, jakie można tworzyć z dowolnego zbioru skończonego.
Zbiory skończone, najczęściej wraz z pewną relacją
obiekty kombinatoryczne
TRZY TYPY ZAGADNIEC
:
TRZY TYPY ZAGADNIEC
:
(1) Czy istnieje obiekt o zadanych własnościach?
(2) Ile jest obiektów o zadanych własnościach?
(3) Czy można znalez
ć obiekt optymalny według zadanych kryteriów?
Odpowiedz
na pytanie (1)   tak lub  nie , a w ogólności twierdzenie
charakteryzujące kryterium.
Odpowiedz
na pytanie (2)  liczba, a w ogólności wzór lub metoda
obliczeniowa.
Odpowiedz
na pytanie (3)  podanie struktury optymalizującej, a w
ogólności algorytmu znajdującego taką strukturę.
Problem przydziału prac
Problem przydziału prac
Do obsadzenia sześć stanowisk pracy:
(m) - murarza (d) - dekarza
(s) - stolarza (c) - cieśli
(b) - betoniarza (i) - instalatora
Pięciu kandydatów: A, B, C, D, E
A - uprawnienia ( s, i )
B - uprawnienia ( s, d )
C - uprawnienia ( s, d )
D - uprawnienia ( m, s, c, i )
E - uprawnienia ( b, i )
PYTANIE 1: Czy można tak dopasować kandydatów do stanowisk pracy,
aby każdy otrzymał pracę zgodnie ze swoimi uprawnieniami?
TAK A - i, B - s, C - d, D - m, E - b
stanowisko cieśli nie jest obsadzone
Uwaga: przy zmianie uprawnień D (d,i) - odpowiedz
NIE
Matematyka Dyskretna
Barbara Głut 1
PYTANIE 2: Na ile sposobów można dopasować kandydatów do
stanowisk pracy?
4 sposoby (trzy inne - B i C mogą się zamienić, D może być cieślą)
Dodatkowo ustalono przydatność kandydatów do stanowisk (skala 1-6),
0 - brak kwalifikacji
m s b d c i
A 0 4 0 0 0 3
B 0 1 0 3 0 0
C 0 5 0 6 0 0
D 3 5 0 0 4 4
E 0 0 2 0 0 5
PYTANIE 3: Który z dopuszczalnych przydziałów pracy jest
najkorzystniejszy (daje największą liczbę punktów) ?
Przydział A - i (3), B - d (3), C - s (5), D - c (4), E - b (2)
suma - 17 punktów
Przedmioty w pudełkach
Przedmioty w pudełkach
Na ile sposobów można rozmieścić trzy przedmioty w dwóch pudełkach?
Przypadek 1: pudełka i przedmioty (a, b, c) rozróżnialne
abc |  ab | c ac | b bc | a
 | abc c | ab b | ac a | bc
Przypadek 2: przedmioty rozróżnialne, pudełka nie
tylko 4 rozmieszczenia
odrzucamy 4 z drugiego wiersza, bo to samo
Przypadek 3: pudełka rozróżnialne, przedmioty nie
o o o |  o o | o o | o o  | o o o
Przypadek 4: pudełka nierozróżnialne, przedmioty też
dwie możliwości: o o o |  o | o o
Matematyka Dyskretna
Barbara Głut 2
USTAWIENIA
USTAWIENIA
Ile słów można utworzyć z liter A K R używając każdej z nich tylko jeden
raz?
AKR ARK KAR KRA RAK RKA
3 �2 �1 = 6 słów
Gdybyśmy mieli do dyspozycji 4 litery? 4 � 3 �2 �1 = 24 słowa
Dla n różnych liter?
n �(n - 1) �(n - 2) �... �2 �1 sposobów ustawienia n silnia
Definicja: n! = 1 � 2 �3 �... � (n - 1) �n 0! = 1
Definicja:
Też definicja rekurencyjna: 1! = 1 n! = (n - 1)! �n
definicja rekurencyjna:
Określa liczbę wszystkich ustawień albo uporządkowań, albo
PERMUTACJI n przedmiotów.
Definicja:
Definicja:
Permutacją bez powtórzeń n elementów
nazywamy ciąg składający się z n elementów
uporządkowanych i różnych.
Liczba możliwych permutacji zbioru n-elementowego:
Pn = n!
Matematyka Dyskretna
Barbara Głut 3
Ile jest ustawień k przedmiotów wybranych spośród n różnych
Ile jest ustawień k przedmiotów wybranych spośród n różnych
przedmiotów?
przedmiotów?
Np.: Ile można utworzyć  słów dwuliterowych ze zbioru liter A, B, C, D
tak, aby litery nie powtarzały się w słowie?
AB BA CA DA
AC BC CB DB 12 ustawień
AD BD CD DC
1 element na 4 sposoby, 2 element na 3 sposoby 4�3 = 12
Ogólnie, gdy ustawiamy k-elementowy ciąg:
1 element n sposobów
2 element n  1
3 element n  2
...
k element n  k + 1
n!
n �(n-1) �(n-2) �... �(n k+1) =
(n - k)!
Definicja:
Definicja:
Wariacją bez powtórzeń k-elementową
ze zbioru n-elementowego
nazywamy ciąg k elementów wybranych z n elementów,
przy czym elementy te są różne między sobą.
Ciąg ważna jest kolejność elementów
Liczba wariacji bez powtórzeń
n!
Vnk =
(n - k)!
Matematyka Dyskretna
Barbara Głut 4
Ile jest ustawień k przedmiotów wybranych spośród n przedmiotów?
Ile jest ustawień k przedmiotów wybranych spośród n przedmiotów?
Np.: Ile można utworzyć liczb dwucyfrowych z cyfr 1, 2, 3?
tworzymy ciągi dwucyfrowe ze zbioru trójelementowego
kolejność odgrywa rolę
cyfry mogą się powtarzać
N 1 N 1 N 1
1L 2 2 L 2 3 L 2
32
O 3 O 3 O 3
Ile można utworzyć liczb pięciocyfrowych z cyfr 1, 2, 3 ?
11111 11112 11121 ...
21111 21112 21121 ... 35
31111 31112 31121 ...
Rzut kostkami
Rzut kostkami
Rzucamy dwoma rozróżnialnymi kostkami do gry.
(Jedna zielona, druga czerwona)
Ile jest możliwych wyników tego  doświadczenia ?
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6)
(2,1) (2,2) (2,3) (2,4) (2,5) (2,6)
(3,1) (3,2) (3,3) (3,4) (3,5) (3,6)
(4,1) (4,2) (4,3) (4,4) (4,5) (4,6)
(5,1) (5,2) (5,3) (5,4) (5,5) (5,6)
(6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
62
A gdyby rzucać trzema kostkami? 62 �6 = 63
A gdyby kostek było k ? 6k
Matematyka Dyskretna
Barbara Głut 5
Ustawiamy k elementów wybranych spośród n elementów
Pierwszy element ciągu możemy wybrać na n sposobów, drugi też, trzeci ...
. . .
n � n � n � . . . � n = nk
Definicja:
Definicja:
Wariacją z powtórzeniami k-elementową
ze zbioru n elementów
nazywamy ciąg k elementów wybranych spośród n
elementów.
Elementy ciągu mogą być różne lub mogą nie różnić się między sobą.
Liczba wariacji z powtórzeniami
k
V = nk
n
Permutacje z wyróżnioną parą
Permutacje z wyróżnioną parą
Na ile sposobów można zapisać w jednym rzędzie cyfry 0, 1, ... , 9 tak, by
cyfry 1 i 2 stały obok siebie?
Traktujemy 1 i 2 jak pojedynczy element 9 elementów
Permutujemy je na 9! sposobów.
Ale: dla cyfr 1 i 2 musimy wybrać kolejność, w jakiej stoją obok
siebie 2 możliwości
Czyli wszystkich sposobów jest: 2 � 9!
A gdy będzie n elementów, a wśród nich są dwa wyróżnione, które
powinny znalez
ć się obok siebie?
2 � (n 1)!
Matematyka Dyskretna
Barbara Głut 6
Permutacje koralikowe
Permutacje koralikowe
Szczególny wariant permutacji, gdzie nie jest wyróżniony początek ani
koniec
np.  elementy rozstawione na okręgu
n krzeseł wokół okrągłego stołu
Ważne, kto siedzi obok kogo, a nie, gdzie kto siedzi
Liczba ustawień:
n!
= (n - 1)!
n
Permutacje z powtórzeniami
Permutacje z powtórzeniami
Definicja:
Definicja:
Permutacją z powtórzeniami
nazywamy ciąg składający się z n elementów,
wśród których pewne elementy powtarzają się odpowiednio
n1, n2, ... , nk razy.
Np. Wypisać wszystkie 3-elementowe permutacje elementów a i b, w
których element a powtarza się dwa razy.
aab aba baa
Matematyka Dyskretna
Barbara Głut 7
Pytanie:
Ile można utworzyć 4-elementowych permutacji z elementów a i b, w
których element a powtarza się trzy razy?
aaab aaba abaa baaa
Istnieje 24 (bo 4!) permutacji z 4 elementów a1a2 a3a4.
A liczba 4-elementowych permutacji o powtarzającym się trzykrotnie elemencie a
jest 3!=6 razy mniejsza od liczby 4-elementowych permutacji bez powtórzeń.
Ogólnie:
Liczba permutacji n-elementowych o powtarzających się
elementach odpowiednio n1, n2, ... , nk razy
n!
1
Pnn ,n2 ,...,nk =
n1!n2!...nk!
LICZBY WYBORÓW
LICZBY WYBORÓW
Gdy chcemy określić tylko liczbę możliwych wyborów lub kombinacji
k przedmiotów, nie interesuje nas k silnia różnych sposobów ich
ustawienia.
Zatem, liczbę wyborów otrzymujemy przez podzielenie liczby
ustawień przez k!
Np. 3-elementowy zbiór { a, b, c }. Z niego wybieramy 2-elementowe
wariacje bez powtórzeń. Liczba ustawień jest równa:
3!
= 6
( a , b) ( a , c ) ( b , a ) ( c, a ) ( b , c ) ( c , b )
1!
Gdy interesuje nas jedynie liczba możliwych wyborów zbiorów
2-elementowych z trzech elementów:
3!
{ a, b } { a , c } { b , c }
= 3
1!�"2!
Matematyka Dyskretna
Barbara Głut 8
Definicja:
Definicja:
Kombinacją bez powtórzeń k-elementową
ze zbioru n elementów
nazywamy zbiór składający się z k różnych elementów
wybranych spośród n różnych elementów.
Obojętne jest, w jakim porządku elementy tego zbioru są rozmieszczone.
Liczba k-elementowych kombinacji bez powtórzeń
Liczba k-elementowych kombinacji bez powtórzeń
ze zbioru n elementów:
ze zbioru n elementów:
n
�# ś# n!
k
Cn = ś# ź# =
ś# ź#
k k!(n - k)!
�# #
n
�# ś#
ś# ź#
ś# ź#
k
symbol Newtona: �# #
Znów rzucamy dwoma kostkami, ale kostki są nierozróżnialne!
Wynik doświadczenia: nieuporządkowana para { i , j }, i, j =1, 2, ... , 6
Ile możliwych różnych wyników?
{1,1} {1,2} {1,3} {1,4} {1,5} {1,6}
{2,2} {2,3} {2,4} {2,5} {2,6}
{3,3} {3,4} {3,5} {3,6}
{4,4} {4,5} {4,6}
{5,5} {5,6}
{6,6}
Na ile sposobów można pomalować k jednakowych kul, mając do
dyspozycji n kolorów?
n = k = 3 kolory: czerwony (c), niebieski (n), zielony (z)
{ z z z } { z z c } { z c c } { c c c } { z z n }
{ z n n } { n n n } { n n c } { n c c } { c n z }
Matematyka Dyskretna
Barbara Głut 9
Wyniki  doświadczeń  zbiory (kolejność elementów nieistotna)
Ale: elementy mogą występować kilka razy, czyli mogą się powtarzać.
Definicja:
Definicja:
Kombinacją z powtórzeniami k-elementową
ze zbioru n-elementowego
nazywamy zbiór składający się z k elementów różnych lub
nie różniących się między sobą, wybranych spośród n
różnych elementów.
Obojętne jest, w jakim porządku elementy tego zbioru są rozmieszczone
Liczba kombinacji z powtórzeniami:
n + k
�# - 1 n + k - 1
ś# �# ś#
k
Cn = ś# ź# = ś# ź#
ś# ź# ś# ź#
k n - 1
�# # �# #
SCHEMATY LOSOWANIA
SCHEMATY LOSOWANIA
k elementów z n-elementowego zbioru
Przed przystąpieniem do losowania należy odpowiedzieć na 2 pytania?
I Czy istotna jest kolejność wylosowanych elementów?
II Czy wylosowane elementy mogą się powtarzać?
I TAK II TAK Wariacje z powtórzeniami
I TAK II NIE Wariacje bez powtórzeń
I NIE II NIE Kombinacje bez powtórzeń
I NIE II TAK Kombinacje z powtórzeniami
Matematyka Dyskretna
Barbara Głut 10
Zasada włączeń i wyłączeń
Zasada włączeń i wyłączeń
PRAWO SUMY:
B
A
A i B zbiory skończone
(1) jeśli A )" B = " (zbiory rozłączne),
to |A *" B| = |A| + |B|
A)"B
(2) ogólnie: |A *" B| = |A| + |B|  |A )" B|
Dla trzech zbiorów:
A
B
| A *" B *" C | = |A| + |B| + |C| +
 |A )" B|  |A )" C|  |B )" C|
C
+ | A )" B )" C |
Przykład
Spośród 100 studentów - 50 uczy się angielskiego, 40 -
francuskiego, w tym 20 obu języków. Ilu studentów nie
uczy się ani angielskiego, ani francuskiego?
A - angielski, F - francuski
100  ( |A| + |F|  |A )" F|) =
= 100  (50 + 40  20) = 30
Matematyka Dyskretna
Barbara Głut 11
Przykład
30 - osobowa grupa: A - 20 uczy się angielskiego,
B - 14 uczy się francuskiego,
C - 10 uczy się niemieckiego.
Jeśli żadna osoba nie uczy się wszystkich trzech języków, a 8 osób nie
uczy się żadnego, to ilu uczy się francuskiego i niemieckiego?
30  8 = 22 osoby uczą się wymienionych języków
| A *" B *" C | = 22 | A )" B )" C | = 0
22 = 20 + 14 + 10  |A )" B|  |A )" C|  |B )" C| + 0
|A )" B| + |A )" C| + |B )" C| = 22
co pokrywa zbiór osób uczących się języków
Każda osoba uczy się dwóch języków, jeśli uczy się języka
|A| = |A )" B| + |A )" C| = 20
|B )" C| = 2
Zasada włączeń i wyłączeń:
Zasada włączeń i wyłączeń:
Aby określić liczbę elementów zbioru A1 *" A2 *" ... *" An należy znalez
ć
liczby elementów wszystkich możliwych przecięć zbiorów spośród
{A1, A2, ... , An }, dodać do siebie wyniki uzyskane dla przecięć
nieparzystej liczby zbiorów, a następnie odjąć wyniki uzyskane dla
przecięć parzystej liczby zbiorów.
Należy  włączyć , czyli dodać do siebie liczebności poszczególnych
zbiorów, następnie  wyłączyć - czyli odjąć liczności wszystkich
przecięć po dwa zbiory, potem znów  włączyć liczności przecięć po
trzy zbiory itd.
Zasada nadaje się do sytuacji, w których:
" chcemy jedynie znać wielkość zbioru A1 *" A2 *" ... *" An,
" liczby wielokrotnych przecięć daje się łatwo obliczyć.
Matematyka Dyskretna
Barbara Głut 12