1

MATEMATYKA DYSKRETNA - Elektronika

Lista 7 - Wzór włączeń i wyłączeń

1. Każdy z uczniów uczy sie dokładnie dwóch, sposród trzech jezyków: angielskiego,
francuskiego i niemieckiego. Angielskiego uczy sie 80%, francuskiego 50%. Jaki procent
uczniów uczy sie niemieckiego?

2. Badania wykazały, że w pewnej grupie złożonej z 20 osób 15 zna angielski, 13 niemiecki,
a 9–włoski. Ponadto, że 10 osób zna angielski i niemiecki, 5 angielski i włoski, 3 niemiecki
i włoski, a 2 osoby wszystkie trzy języki. Wykaż, że te dane są sfałszowane.

3. Załóżmy, że |A ∪ B ∪ C| = 16, |A| = 9, |B| = 8, |C| = 7, a ponadto |B ∩ C| =
|A ∩ B ∩ C| + 2. Ile wynosi |A ∩ C|?

4. Ile liczb naturalnych z przedziału [1, 1000]:
a) dzieli się przez 2 lub przez 3 lub przez 5; b) nie dzieli się ani przez 2, ani przez 3, ani
przez 5; c) dzieli się przez 4 lub 5 lub 6?

5. Na ile sposobów można z 6 małżeństw utworzyć 6 par tanecznych tak, aby nikt nie
tańczył ze swym małżonkiem?

6. Na ile sposobów można pokolorować ściany pokoju i sufit trzema kolorami tak, aby
każdy kolor został wykorzystany?

7. Rozważmy wszystkie funkcje ze zbioru {1, 2, 3, 4, 5} w zbiór {1, 2, 3}. Ile spośród
tych funkcji to: a) funkcje różnowartościowe; b) funkcje rosnące: c) funkcje ”na”?

8. Rozważmy wszystkie funkcje ze zbioru {1, 2, 3, 4} w zbiór {1, 2, 3, 4, 5, 6}. Ile
spośród tych funkcji to: a) funkcje różnowartościowe; b) funkcje rosnące: c) funkcje ”na”;
d) funkcje niemalejące?

9. Ile permutacji zbioru sześcioelementowego ma dokładnie jeden punkt stały?

10. Ile sposobami można ustawić na szachownicy 8 wież tak, aby żadne dwie się nie
atakowały, a żadna z wież nie stała na wybranej przekątnej?

11.* Wykaż, że dla nieporządków zachodzą równości

d

n+1

= (n + 1)d

n

+ (−1)

n+1

,

d

n+1

= n(d

n

+ d

n−1

).