Matematyka dyskretna 1/Test 3: Zliczanie zbiorów i funkcji

From Studia Informatyczne

Niech \displaystyle X będzie dowolnym zbiorem skończonym. Wtedy:

liczba injekcji, liczba surjekcji i liczba bijekcji z \displaystyle X w \displaystyle X jest taka sama

injekcji i bijekcji z \displaystyle X w \displaystyle X jest tyle samo, natomiast surjekcji może być mniej

injekcji i surjekcji z \displaystyle X w \displaystyle X jest tyle samo, natomiast bijekcji może być mniej

liczba injekcji jest niewiększa od liczby surjekcji, która jest niewiększa od liczby bijekcji (wszystkie funkcje z \displaystyle X w \displaystyle X)

Niech \displaystyle A będzie zbiorem dodatnich liczb nieparzystych. Wtedy:

\displaystyle A jest przeliczalny

istnieje injekcja z \displaystyle A w \displaystyle \mathbb{N}

istnieje surjekcja z \displaystyle A w \displaystyle \mathbb{N}

istnieje bijekcja z \displaystyle A w pewien właściwy podzbiór \displaystyle A

Maksymalna liczba punktów które można wybrać w trójkącie równobocznym o boku \displaystyle 1 (wraz z obrzeżami) tak, by dowolne dwa były odległe o co najmniej \displaystyle \frac{1}{2} to:

\displaystyle 3

\displaystyle 4

\displaystyle 5

\displaystyle 6

Dla skończonych zbiorów \displaystyle A,B,C,D takich, że \displaystyle A\cap B=\emptyset i \displaystyle C\cap D=\emptyset, moc zbioru \displaystyle A\cup B\cup C\cup D wynosi:

\displaystyle \left\vert A \right\vert+\left\vert B \right\vert+\left\vert C \right\vert+\left\vert D \right\vert-\left\vert A\cap C \right\vert-\left\vert A\cap D \right\vert-\left\vert B\cap C \right\vert-\left\vert B\cap D \right\vert

\displaystyle \displaystyle{\left\vert A \right\vert+\left\vert B \right\vert+\left\vert C \right\vert+\left\vert D \right\vert-\sum_{I,J\in\left\lbrace A,B,C,D \right\rbrace, I\neq J}\left\vert I\cap J \right\vert+\sum_{I,J,K\in\left\lbrace A,B,C,D \right\rbrace, I\neq J\neq K \neq I}\left\vert I\cap J\cap K \right\vert}

\displaystyle \left\vert A\cup B \right\vert+\left\vert C\cup D \right\vert

\displaystyle \left\vert A\cup C \right\vert+\left\vert B\cup D \right\vert

Gdy \displaystyle X jest zbiorem skończonym, to par \displaystyle (A,B) takich, że \displaystyle A\subseteq B\subseteq X jest:

\displaystyle 2^{\left\vert X \right\vert}+2^{\left\vert X \right\vert}

\displaystyle 2^{\left\vert X \right\vert}\cdot 2^{\left\vert X \right\vert}

\displaystyle 2^{\left\vert X \right\vert^2}

\displaystyle 3^{\left\vert X \right\vert}

Bartek, Paweł i Piotrek wybrali się na wesele znajomych. W pewnym momencie na parkiecie tańczyło \displaystyle 7 samotnych dziewcząt. Cała trójka postanowiła spróbować szczęścia. Najpierw jednak ustalili, że każdy poprosi do tańca inną panią. Na ile sposobów mogli oni dokonać wyboru?

\displaystyle 7^3

\displaystyle 3^7

\displaystyle 7!\cdot 3!

\displaystyle \frac{7!}{4!}

Dowolna permutacja zbioru skończonego:

jest odwracalna

jest rozkładalna na cykle

jest rozkładalna na rozłączne cykle

jest jednoznacznie rozkładalna (z dokładnością do porządku cykli) na rozłączne cykle

W dowolnym dwu-kolorowaniu (białym i czarnym kolorem) punktów płaszczyzny \displaystyle \mathbb{R}^2:

dla nieskończenie wielu \displaystyle r>0 istnieją dwa czarne punkty oddalone o \displaystyle r

dla dowolnego \displaystyle r>0 istnieją dwa czarne punkty oddalone o \displaystyle r

dla nieskończenie wielu \displaystyle r>0 istnieją dwa jednobarwne punkty oddalone o \displaystyle r

dla dowolnego \displaystyle r>0 istnieją dwa jednobarwne punkty oddalone o \displaystyle r

Masz zestaw składający się z trzech typów klocków: \displaystyle 6 dużych, \displaystyle 7 średnich i \displaystyle 3 małych. Piramidę złożoną z \displaystyle 3 klocków (na dole największy, później średni i na górze mały) można zbudować na:

\displaystyle 6\cdot7\cdot3 sposobów

\displaystyle \frac{6\cdot7\cdot3}{2} sposobów

\displaystyle \frac{6\cdot 7\cdot 3}{3!} sposobów

\displaystyle 6!7!3! sposobów

Ile liczb rzeczywistych wystarcza by mieć pewność, że wśród nich co najmniej dwie mają rozwinięcia dziesiętne pokrywające się w nieskończonej liczbie miejsc po przecinku (jeśli liczba ma skończone rozwinięcie, to uzupełniamy je zerami).

\displaystyle 2

\displaystyle 10

\displaystyle 11

nieskończenie wiele