WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 1 / 9
Techniki rozwiązywania problemów kombinatorycznych
zasada mnożenia
zasada równoliczności
zasada szufladkowa Dirichleta
zasada włączania-wyłączania
funkcje tworzące
Zasada mnożenia
Jeżeli rozważane są funkcje f : X
→
Y ,
dla których X = X
1
∪
X
2
i Y = Y
1
∪
Y
2
oraz spełnione są warunki
X
1
∩
X
2
=
∅
, f (
X
1
)
⊆
Y
1
i f (
X
2
)
⊆
Y
2
,
to
|
Fun(X, Y)
| = |
Fun(X
1
, Y
1
)
|
⋅
|
Fun(X
2
, Y
2
)
|
Jeżeli ponadto Y
1
∩
Y
2
=
∅
,
to
|
Inj(X, Y)
| = |
Inj(X
1
, Y
1
)
|
⋅
|
Inj(X
2
, Y
2
)
|
Przykład
Jaka jest maksymalna liczba tablic rejestracyjnych typu WI07049?
Tablica to zbiór 7 znaków X = {z
1
, z
2
, z
3
, z
4
, z
5
, z
6
, z
7
},
X
1
= {z
1
, z
2
}, X
2
= {z
3
, z
4
, z
5
, z
6
, z
7
}, Y
1
– zbiór liter, Y
2
– zbiór cyfr,
| X
1
| = 2, | X
2
| =5, | Y
1
| = 26, | Y
2
| = 10, |Fun(X, Y)| = 26
2
⋅⋅⋅⋅
10
5
Jaka jest maksymalna liczba tablic o różnych literach i różnych cyfrach?
| Inj(X, Y) | = 26
2
⋅⋅⋅⋅
10
5
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 2 / 9
Zasada równoliczności
Bij(X, Y)
≠
∅
⇒ |
X
| = |
Y
|
Przykład
Dlaczego podziałów liczby n na k składników jest tyle samo co
podziałów liczby n o największym składniku równym k ?
Bo możemy wzajemnie jednoznacznie przyporządkować podziałowi
liczby n na k składników jego podział sprzężony, który jest podziałem
liczby n o największym składniku równym k.
Zasada szufladkowa
Dla skończonych zbiorów X i Y , takich że | X | > r
⋅
| Y | dla r > 0 :
dla każdej funkcji f
∈
Fun(X, Y) warunek | f
−
1
({y}) | > r jest
spełniony dla co najmniej jednego y
∈
Y.
(jeśli wkładamy n przedmiotów do m pudełek i n > r
⋅
m , to w
przynajmniej jednym pudełku znajdzie się ponad r przedmiotów)
Przykład
Dlaczego na egzaminie dla 401 studentów, na którym każdy student
może dowolnie wybrać do rozwiązania 7 zadań z 9, będzie co
najmniej 12 studentów rozwiązujących ten sam zestaw zadań?
Bo wszystkich zestawów, które mogą powstać jest
7
9
= 36, a zatem
liczba studentów 401 > 11
⋅
36 = 396 i w twierdzeniu r = 11.
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 3 / 9
Zasada włączania-wyłączania
...
|
|
|
|
|
|
}
,...,
{
}
,
,
{
}
,...,
{
}
,
{
−
∩
∩
+
∩
−
=
∑
∑
∑
⊆
⊆
=
=
n
k
j
i
k
j
i
n
j
i
j
i
n
i
i
n
i
i
A
A
A
A
A
A
A
1
1
1
1
U
... + (
−
1)
n
−
1
| A
1
∩
...
∩
A
n
| =
=
∑
∑
⊆
=
−
∩
∩
∩
−
}
,...,
{
}
,...,
,
{
|
...
|
)
(
n
p
p
p
p
p
p
n
i
i
i
i
A
A
A
1
1
1
2
1
2
1
1
dla n = 3: | A
∪
B
∪
C | =
= | A | + | B | + | C |
−
| A
∩
B |
−
| A
∩
C |
−
| B
∩
C |
+
| A
∩
B
∩
C |
Zastosowanie zasady włączania-wyłączania do wyznaczenia liczby
podzbiorów k-elementowych zbioru z powtórzeniami
Rozważmy zbiór z powtórzeniami
X
=
<
5
∗
a, 2
∗
b, 3
∗
c
>
Ile jest 7-elementowych podzbiorów zbioru X ?
Wprowadźmy pomocniczy zbiór
Y
=
<
7
∗
a, 7
∗
b, 7
∗
c
>
Wśród 7-elementowych podzbiorów zbioru Y są takie, które są także
podzbiorami zbioru X i takie, które nimi nie są.
Oznaczmy przez P zbiór 7-elementowych podzbiorów zbioru Y :
| P | =
−
+
7
1
7
3
=
7
9
= 36
Podzbiorami zbioru X nie są te 7-elementowe podzbiory zbioru Y,
które zawierają ponad 5 powtórzeń elementu a lub ponad 2
powtórzenia elementu b, lub ponad 3 powtórzenia elementu c.
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 4 / 9
Rozważmy następujące zbiory:
P
a
– zbiór 7-elementowych podzbiorów zbioru Y, które zawierają
ponad 5 powtórzeń elementu a ,
P
b
– zbiór 7-elementowych podzbiorów zbioru Y, które zawierają
ponad 2 powtórzenia elementu b :
P
c
– zbiór 7-elementowych podzbiorów zbioru Y, które zawierają
ponad 3 powtórzenia elementu c :
Zbiór 7-elementowych podzbiorów zbioru Y, które nie są podzbiorami
zbioru X to
P
a
∪
P
b
∪
P
c
,
a zatem liczba 7-elementowych podzbiorów zbioru Y, które są
podzbiorami zbioru X wynosi | P |
−
| P
a
∪
P
b
∪
P
c
|
| P
a
∪
P
b
∪
P
c
| = | P
a
| + | P
b
| + | P
c
| +
−
| P
a
∩
P
b
|
−
| P
a
∩
P
c
|
−
| P
b
∩
P
c
|
+
| P
a
∩
P
b
∩
P
c
|
Każde A
∈
P
a
może być zapisane jako A =
<
6
∗
a, 0
∗
b, 0
∗
c
> ∪
A',
gdzie A' jest 1-elementowym podzbiorem zbioru
<
1
∗
a, 7
∗
b, 7
∗
c
> :
| P
a
| =
−
+
1
1
1
3
=
1
3
= 3
Każde B
∈
P
b
może być zapisane jako B =
<
0
∗
a, 3
∗
b, 0
∗
c
> ∪
B',
gdzie B' jest 4-elementowym podzbiorem zbioru
<
7
∗
a, 4
∗
b, 7
∗
c
> :
| P
b
| =
−
+
4
1
4
3
=
4
6
= 15
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 5 / 9
Każde C
∈
P
c
może być zapisane jako C =
<
0
∗
a, 0
∗
b, 4
∗
c
> ∪
C',
gdzie C' jest 3-elementowym podzbiorem zbioru
<
7
∗
a, 7
∗
b, 3
∗
c
> :
| P
c
| =
−
+
3
1
3
3
=
3
5
= 10
| P
a
∩
P
b
| = 0, bo podzbiór należący do P
a
∩
P
b
musiałby mieć co
najmniej 9 elementów
<
6
∗
a, 3
∗
b, ?
∗
c
>
.
| P
a
∩
P
c
| = 0, bo podzbiór należący do P
a
∩
P
c
musiałby mieć co
najmniej 10 elementów
<
6
∗
a, ?
∗
b, 4
∗
c
>
.
| P
b
∩
P
c
| = 1, bo podzbiór należący do P
b
∩
P
c
jest tylko jeden
<
0
∗
a, 3
∗
b, 4
∗
c
>
.
| P
a
∩
P
b
∩
P
c
| = 0, bo podzbiór należący do P
a
∩
P
b
∩
P
c
musiałby
mieć co najmniej 13 elementów
<
6
∗
a, 3
∗
b, 4
∗
c
>
.
Czyli
| P
a
∪
P
b
∪
P
c
| = 3 + 15 + 10 – 0 – 0 – 1 + 0 = 27,
27 podzbiorów 7-elementowych zbioru Y nie jest podzbiorami X.
Liczba 7-elementowych podzbiorów zbioru X wynosi zatem
| P |
−
| P
a
∪
P
b
∪
P
c
| = 36 – 27 = 9
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 6 / 9
Zastosowanie zasady włączania-wyłączania
do wyznaczenia liczby surjekcji
Dla | X | = n, | Y | = m ,
| Sur(X, Y) | =
⋅
=
m
n
m
s
m
n
!
,
,
ale spróbujmy ominąć odwołanie do liczb Stirlinga drugiego rodzaju.
Przyjmijmy, że Y = {y
1
, y
2
, ..., y
m
} i podzbiór F
i
⊆
Fun(X, Y) jest
zbiorem takich funkcji f , dla których y
i
∉
f (X).
Zatem zbiór F
1
∪
F
2
∪ ... ∪
F
m
jest zbiorem funkcji f
∈
Fun(X, Y) ,
które nie są surjekcjami:
m
n
s
,
= | Fun(X, Y) |
−
| F
1
∪
F
2
∪ ... ∪
F
m
|,
| Fun(X, Y) | = m
n
| F
1
∪
F
2
∪ ... ∪
F
m
| =
∑
∑
⊆
=
−
∩
∩
∩
−
}
,...,
{
}
,...,
,
{
|
...
|
)
(
m
p
p
p
p
p
p
m
i
i
i
i
F
F
F
1
1
1
2
1
2
1
1
Należy zatem wyznaczyć liczności zbiorów
i
p
p
p
F
F
F
∩
∩
∩
...
2
1
dla
i = 1, 2, ..., m i
{
} {
}
m
p
p
p
i
,...,
,...,
,
1
2
1
⊆
.
Zauważmy, że jeśli f
∈
i
p
p
p
F
F
F
∩
∩
∩
...
2
1
, to
i
p
p
p
y
y
y
,...,
,
2
1
∉
f (X).
Zatem
i
p
p
p
F
F
F
∩
∩
∩
...
2
1
= Fun(X, Y \ {
i
p
p
p
y
y
y
,...,
,
2
1
}) ;
|
i
p
p
p
F
F
F
∩
∩
∩
...
2
1
| = | Fun(X, Y \ {
i
p
p
p
y
y
y
,...,
,
2
1
}) | =
n
i
m
)
(
−
Podzbiór {
i
p
p
p
y
y
y
,...,
,
2
1
} można wybrać ze zbioru Y na
i
m
sposobów,
a zatem
n
m
p
p
p
p
p
p
i
m
i
m
F
F
F
i
i
)
(
|
...
|
}
,...,
{
}
,...,
,
{
−
=
∩
∩
∩
∑
⊆
1
2
1
2
1
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 7 / 9
i ostatecznie
| F
1
∪
F
2
∪ ... ∪
F
m
| =
∑
=
−
−
−
m
i
n
i
i
m
i
m
1
1
1
)
(
)
(
.
Liczba surjekcji
m
n
s
,
= | Fun(X, Y) |
−
| F
1
∪
F
2
∪ ... ∪
F
m
| =
=
n
m
−
∑
=
−
−
−
m
i
n
i
i
m
i
m
1
1
1
)
(
)
(
=
n
m +
∑
=
−
−
m
i
n
i
i
m
i
m
1
1
)
(
)
(
m
n
s
,
=
∑
−
=
−
−
1
0
1
m
i
n
i
i
m
i
m
)
(
)
(
Porównując
⋅
m
n
m!
=
∑
−
=
−
−
1
0
1
m
i
n
i
i
m
i
m
)
(
)
(
otrzymujemy wzór pozwalający bez
rekurencji wyznaczać liczby Stirlinga drugiego rodzaju:
∑
∑
−
=
−
=
⋅
−
−
−
=
−
−
=
1
0
1
0
1
1
1
m
i
n
i
m
i
n
i
i
i
m
i
m
i
m
i
m
m
m
n
!
)!
(
)
(
)
(
)
(
)
(
!
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 8 / 9
Zastosowanie zasady włączania-wyłączania
do wyznaczenia liczby nieporządków
S
n
−
zbiór wszystkich permutacji zbioru { 1, 2, ..., n }
Każdy element f
∈
S
n
możemy zapisać w postaci tablicy:
=
)
(
...
)
(
)
(
...
n
f
f
f
n
f
2
1
2
1
Nieporządkiem nazywamy taką permutację f
∈
S
n
,
dla której f (i)
≠
i dla każdego i
∈
{ 1, 2, ..., n }
D
n
−
zbiór wszystkich nieporządków w zbiorze { 1, 2, ..., n }
| D
n
| = ?
Przyjmijmy, że A
i
= { f
∈
S
n
: f (i) = i } dla i
∈
{ 1, 2, ..., n }.
W zbiorze A
1
∪
A
2
∪ ... ∪
A
n
są wszystkie permutacje f
∈
S
n
, które
nie są nieporządkami, a zatem | D
n
| = | S
n
|
−
| A
1
∪
A
2
∪ ... ∪
A
n
|.
| S
n
| = n! ,
| A
1
∪
A
2
∪ ... ∪
A
n
| =
∑
∑
⊆
=
−
∩
∩
∩
−
}
,...,
{
}
,...,
,
{
|
...
|
)
(
n
p
p
p
p
p
p
n
i
i
i
i
A
A
A
1
1
1
2
1
2
1
1
.
Należy zatem wyznaczyć liczności zbiorów
i
p
p
p
A
A
A
∩
∩
∩
...
2
1
dla
i = 1, 2, ..., n i
{
} {
}
m
p
p
p
i
,...,
,...,
,
1
2
1
⊆
.
i
p
p
p
A
A
A
∩
∩
∩
...
2
1
jest zbiorem wszystkich takich permutacji
f
∈
S
n
, dla których f (p
j
) = p
j
dla j = 1, 2, ..., i , a zatem
|
i
p
p
p
A
A
A
∩
∩
∩
...
2
1
| = (n – i)!
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
MATEMATYKA DYSKRETNA (8)
J.Sikorski
Strona 9 / 9
Podzbiór { p
1
, p
2
, ..., p
i
} można wybrać ze zbioru { 1, 2, ..., n } na
i
n
sposobów, a zatem
)!
(
|
...
|
}
,...,
{
}
,...,
,
{
i
n
i
n
A
A
A
n
p
p
p
p
p
p
i
i
−
=
∩
∩
∩
∑
⊆
1
2
1
2
1
i ostatecznie
| A
1
∪
A
2
∪ ... ∪
A
n
| =
∑
=
−
−
−
n
i
i
i
n
i
n
1
1
1
)!
(
)
(
.
Liczba nieporządków | D
n
| = | S
n
|
−
| A
1
∪
A
2
∪ ... ∪
A
n
| =
n!
−
∑
=
−
−
−
n
i
i
i
n
i
n
1
1
1
)!
(
)
(
= n!
+
∑
=
−
−
n
i
i
i
n
i
n
1
1
)!
(
)
(
=
∑
=
−
n
i
i
i
n
0
1
!
!
)
(
.
| D
n
| =
∑
=
−
n
i
i
i
n
0
1
!
)
(
!
Na przykład
Dla n = 5 liczba nieporządków
| D
n
| =
−
+
−
+
−
!
!
!
!
!
!
5
1
4
1
3
1
2
1
1
1
1
5
= 44
spośród wszystkich 5! = 120 permutacji, czyli ponad 36%
36787944
0
1
1
0
,
!
)
(
≈
→
−
=
∞
→
=
∑
e
i
S
D
n
n
i
i
n
n