Matematyka dyskretna

AGH

DZIAŁ ZLICZANIE – cz. II

wszystkie zadania warte są 1 punkt

Zad 1.
Funkcja g nazywa się funkcją odwrotną do funkcji f, jeśli domena (dziedzina) g jest zbiorem
wartości f, jeśli g (f (x)) = x dla każdego x w domenie (dziedzinie) f,
oraz jeśli f (g (y)) = y dla każdego y w zbiorze wartości f.

a. Wyjaśnij, dlaczego funkcja jest bijekcją wtedy i tylko wtedy, gdy posiada funkcję

odwrotną.

b. Wytłumacz dlaczego jeżeli funkcja posiada funkcję odwrotną to posiada tylko jedną taką

funkcję.

Zad 2.
Proszę wypisać wszystkie funkcje ze zbioru {1,2,3} na zbiór {a, b}. Proszę wskazać funkcje
iniekcje oraz suriekcje.

Zad 3.
Wypisz zbiór wszystkich 3 elementowych permutacji zbioru {1, 2, 3, 4}, który jest
równoważny do (relacją równoważności jest permutacja)

a. 243
b. 123
c. 142
d. 134

Czy któreś z tych zbiorów mają takie same permutacje?

Zad 4.
Zadania należy wykonać korzystając z odpowiednich wzorów na permutacje, kombinacje, itd.
tłumacząc za każdym razem możliwość ich użycia.

a. Na ile sposobów k różnych tabliczek czekolady można rozdzielić pomiędzy n osób

(każda z osób może otrzymać więcej niż jedną tabliczkę)?

b. Na ile sposobów k różnych tabliczek czekolady można rozdzielić pomiędzy n osób

(każda z osób może otrzymać najwyżej jedną tabliczkę)?

c. Na ile sposobów k identycznych tabliczek czekolady można rozdzielić pomiędzy n

osób (każda z osób może otrzymać więcej niż jedną tabliczkę)?

d. Na ile sposobów k różnych tabliczek czekolady można rozdzielić pomiędzy n osób

(każda z osób może otrzymać najwyżej jedną tabliczkę)?

e. Jaka jest ilość funkcji różnowartościowych f z {1, 2, . . . ,k} do {1, 2, . . . ,n}?
f. Jaka jest ilość funkcji f z {1, 2, . . . ,k} do {1, 2, . . . ,n}?
g. Na ile sposobów można wybrać k-elementowy podzbiór ze zbioru n-elementowego?
h. Na ile sposobów k-elementowy wielozbiór może być utworzony z n-elementowego

zbioru? Nie ma takiej odpowiedzi w podanych: (2k-1 po k)

i. Na ile sposobów k-najwyższych rangą urzędników w Polsce może zostać wybranych z

pośród n-osób? (Ma to być uporządkowana lista, a nie zbiór.)

j. Na ile sposobów k cukierków (niekoniecznie tego samego rodzaju) może zostać

wybranych z pośród n rodzajów?

k. Na ile sposobów k dzieci może wybrać jeden cukierek (każdy o innym smaku) z

pośród n różnych smaków cukierków?

Zad 5.

a. Na ile sposobów można ustawić litery a, b, c, d, e, f w takiej kolejności, by litery a i b

sąsiadowały z sobą?

b. Na ile sposobów można ustawić litery a, b, c, d, e, f w takiej kolejności, by litery a i b

nie sąsiadowały z sobą?

c. Na ile sposobów można ustawić litery a, b, c, d, e, f w takiej kolejności, by litery a i b

sąsiadowały z sobą, ale litery a i c nie?

Zad 6.

a. Na ile sposobów można rozmieścić 14 przedmiotów (jednego rodzaju) w 3 pudełkach

tak, by w jednym z pudełek znalazło się co najmniej 8 przedmiotów?

b. Na ile sposobów można rozmieścić 14 przedmiotów w 3 pudełkach tak, by w żadnym

z pudełek nie znalazło się więcej niż 7 przedmiotów?

c. Ile jest liczb między 0 a 999, których suma cyfr jest równa 20? Wskazówka: każda z

cyfr musi być równa co najmniej 2; można zastosować część (b).