WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

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)| = 262 ⋅ 105

Jaka jest maksymalna liczba tablic o różnych literach i różnych cyfrach?

| Inj( X, Y) | = 262 ⋅ 105

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 1 / 9

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

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ń?

 9

Bo wszystkich zestawów, które mogą powstać jest  = 36, a zatem

 7

liczba studentów 401 > 11 ⋅ 36 = 396 i w twierdzeniu r = 11.

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 2 / 9

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

Zasada włączania-wyłączania

n

n

U i

A = ∑| A |

i −

∑| iA ∩ A |

j

+

∑| iA ∩ Aj ∩ A |

k

− ...

i=1

i=1

{ i, j} {

⊆ ,

1 ..., n}

{ i, j, k } {

⊆ ,

1 ..., n}

... + (−1) n−1| A 1 ∩ ... ∩ An | =

n

i−

= ∑(− ) 1

1

∑| Ap ∩ Ap ∩... ∩ A |

p

1

2

i

i=1

{ p , p ,..., p

1

2

i ⊆

} { ,

1 ..., n}

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 :

3 + 7 −1 9

| P | = 

 =  = 36



7

  7

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.

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 3 / 9

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

Rozważmy następujące zbiory:

Pa – zbiór 7-elementowych podzbiorów zbioru Y, które zawierają ponad 5 powtórzeń elementu a ,

Pb – zbiór 7-elementowych podzbiorów zbioru Y, które zawierają ponad 2 powtórzenia elementu b :

Pc – 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

Pa ∪ Pb ∪ Pc ,

a zatem liczba 7-elementowych podzbiorów zbioru Y, które są

podzbiorami zbioru X wynosi | P | − | Pa ∪ Pb ∪ Pc |

| Pa ∪ Pb ∪ Pc | = | Pa | + | Pb | + | Pc | +

− | Pa ∩ Pb | − | Pa ∩ Pc | − | Pb ∩ Pc | + | Pa ∩ Pb ∩ Pc |

Każde A ∈ Pa 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 > :

3 +1−1 3

| Pa | = 

 =  = 3



1



1

Każde B ∈ Pb 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 > :

3 + 4 − 

1

 6

| Pb | = 

 =  = 15



4



 4

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 4 / 9

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

Każde C ∈ Pc 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 > :

3 + 3 − 

1

5

| Pc | = 

 =   = 10



3



3

| Pa ∩ Pb | = 0, bo podzbiór należący do Pa ∩ Pb musiałby mieć co najmniej 9 elementów < 6∗ a, 3∗ b, ?∗ c >.

| Pa ∩ Pc | = 0, bo podzbiór należący do Pa ∩ Pc musiałby mieć co najmniej 10 elementów < 6∗ a, ?∗ b, 4∗ c >.

| Pb ∩ Pc | = 1, bo podzbiór należący do Pb ∩ Pc jest tylko jeden

< 0∗ a, 3∗ b, 4∗ c >.

| Pa ∩ Pb ∩ Pc | = 0, bo podzbiór należący do Pa ∩ Pb ∩ Pc musiałby mieć co najmniej 13 elementów < 6∗ a, 3∗ b, 4∗ c >.

Czyli

| Pa ∪ Pb ∪ Pc | = 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 | − | Pa ∪ Pb ∪ Pc | = 36 – 27 = 9

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 5 / 9

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

Zastosowanie zasady włączania-wyłączania

do wyznaczenia liczby surjekcji

 n 

Dla | X | = n, | Y | = m ,

| Sur( X, Y) | = sn, m = m ⋅

!   ,

 m

ale spróbujmy ominąć odwołanie do liczb Stirlinga drugiego rodzaju.

Przyjmijmy, że Y = { y1, y2, ..., ym} i podzbiór Fi ⊆ Fun( X, Y) jest zbiorem takich funkcji f , dla których yi ∉ f ( X).

Zatem zbiór F1 ∪ F2 ∪ . . ∪ Fm jest zbiorem funkcji f ∈ Fun( X, Y) , które nie są surjekcjami:

sn, m = | Fun( X, Y) | − | F1 ∪ F2 ∪ . . ∪ Fm |,

| Fun( X, Y) | = mn

m

i−

| F

∑(− ) 1

1

| Fp ∩ Fp ∩ ... ∩

1 ∪ F2 ∪ . . ∪ Fm | =

∑

F

|

p

1

2

i

i=1

{ p , p ,..., p

1

2

i ⊆

} { ,

1 ..., m}

Należy zatem wyznaczyć liczności zbiorów F

∩

∩ ... ∩

p

Fp

F dla

1

2

i

p

i = 1, 2, ..., m i { p , p ,..., p ⊆

1

2

i }

{ , 1..., m}.

Zauważmy, że jeśli f ∈ F ∩

∩ ... ∩

p

Fp

F , to y , y

,..., y ∉ f ( X).

1

2

i

p

p

p

1

2

i

p

Zatem

F

∩

∩ ... ∩

p

Fp

F = Fun( X, Y \ { y , y

,..., y }) ;

1

2

i

p

p

p

1

2

i

p

| F

∩

∩ ... ∩

−

p

Fp

F | = | Fun( X, Y \ { y , y

,..., y }) | =

n

( m i)

1

2

i

p

p

p

1

2

i

p

 m

Podzbiór { y p , y p ,..., y } można wybrać ze zbioru Y na   sposobów, 1

2

i

p

 i 

 m

a zatem

n

∑| F ∩

∩ ∩

=   −

p

Fp

...

Fp |

( m i)

1

2

i

 i

{ p , p ,..., p } {

1

2

⊆ ,

1 ..., m



i

}

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 6 / 9

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

m

i−  m 

i ostatecznie

| F

(−

1

n

1)

 ( m −

1 ∪ F2 ∪ . . ∪ Fm | = ∑

i) .

i

i=

 

1

Liczba surjekcji sn, m = | Fun( X, Y) | − | F1 ∪ F2 ∪ . . ∪ Fm | =

m

m

 m

i−  m 

= n

m − ∑(−

1

n

1)

i

n

 ( m − i) = n

m + ∑(−1)  ( m − i) i

i

i=

 

1

i=

 

1

m−1

 m

s

(−1 i

n

)  ( m −

n, m = ∑

i)

i

i=

 

0

Porównując

 n  m−1

 m

m! ⋅  = ∑(−1 i

n

)  ( m − i) otrzymujemy wzór pozwalający bez

 m

i

i=

 

0

rekurencji wyznaczać liczby Stirlinga drugiego rodzaju:

m−1

−

 n 

1

1

m

n

m

( m i)

  =

∑

 

(−1 i

n

i

)  ( m − i) = ∑

−

(−1)

 m

m!

i

( m i)! i!

i=

 

0

i=

− ⋅

0

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 7 / 9

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

Zastosowanie zasady włączania-wyłączania

do wyznaczenia liczby nieporządków

Sn − zbiór wszystkich permutacji zbioru { 1, 2, ..., n }

Każdy element f ∈ Sn możemy zapisać w postaci tablicy:

 1

2

...

n 

f = 



 f ( )

1

f (2)

...

f ( n)

Nieporządkiem nazywamy taką permutację f ∈ Sn , dla której f ( i) ≠ i dla każdego i ∈ { 1, 2, ..., n }

Dn − zbiór wszystkich nieporządków w zbiorze { 1, 2, ..., n }

| Dn | = ?

Przyjmijmy, że Ai = { f ∈ Sn : f ( i) = i } dla i ∈ { 1, 2, ..., n }.

W zbiorze A1 ∪ A2 ∪ . . ∪ An są wszystkie permutacje f ∈ Sn , które nie są nieporządkami, a zatem | Dn | = | Sn | − | A1 ∪ A2 ∪ . . ∪ An |.

| Sn | = n! ,

n

i−

| A

∑(− ) 1

1

| Ap ∩ Ap ∩ ... ∩

1 ∪ A2 ∪ . . ∪ An | =

∑

A

|

p

.

1

2

i

i=1

{ p , p ,..., p

1

2

i ⊆

} { ,

1 ..., n}

Należy zatem wyznaczyć liczności zbiorów A

∩

∩ ... ∩

p

Ap

A dla

1

2

i

p

i = 1, 2, ..., n i { p , p ,..., p ⊆

1

2

i }

{ , 1..., m}.

A

∩

∩ ... ∩

p

Ap

A jest zbiorem wszystkich takich permutacji

1

2

i

p

f ∈ Sn , dla których f ( pj) = pj dla j = 1, 2, ..., i , a zatem

| A

∩

∩ ... ∩

p

Ap

A | = ( n – i)!

1

2

i

p

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 8 / 9

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

 n

Podzbiór { p1, p2, ..., pi } można wybrać ze zbioru { 1, 2, ..., n } na  

 i 

 n

sposobów, a zatem

∑| A ∩ A ∩ ... ∩ A | =

( n

 

− i)!

p

p

p

1

2

i

 i

{ p , p ,..., p } {

1

2

⊆ ,

1 ..., n}



i

n

i−  n 

i ostatecznie

| A

(−

1

1)

 ( n −

1 ∪ A2 ∪ . . ∪ An | = ∑

i)! .

i

i=

 

1

Liczba nieporządków | Dn | = | Sn | − | A1 ∪ A2 ∪ . . ∪ An | =

n

n

 n

n

i−  n 

n!

n! − ∑(−

1

1)

i

i

 ( n − i)! = n! + ∑(−1)  ( n − i)! = ∑(−1)

.

i

i

i!

i=

 

1

i=

 

1

i=0

n (− i

1)

| Dn | = n! ∑

i!

i=0

Na przykład

Dla n = 5 liczba nieporządków



1

1

1

1

1 

| D

!

5 1 −

+ − + −

n | =

 = 44



!

1

!

2

!

3

!

4

!

5 

spośród wszystkich 5! = 120 permutacji, czyli ponad 36%

D

n

n

( 1

− ) i

1

= ∑

 

 → ≈ 0 3

, 6787944

S

!

n→∞

n

i=

i

e

0

MATEMATYKA DYSKRETNA (8)

J.Sikorski

Strona 9 / 9