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