Mohutnost množin

Řešení příkladu:

Množina \(A\) obsahuje všechna sudá přirozená čísla od 1 do 20. Sudá čísla jsou ta, která jsou dělitelná 2 bez zbytku.

První sudé číslo v rozsahu je 2, poslední je 20. Čísla tvoří aritmetickou posloupnost s diferencí 2:

\(2, 4, 6, 8, 10, 12, 14, 16, 18, 20\).

Počet těchto čísel spočítáme jako:

\(\frac{20 – 2}{2} + 1 = \frac{18}{2} + 1 = 9 + 1 = 10\).

Tedy mohutnost množiny \(A\) je \( |A| = 10 \).

Řešení příkladu:

Kartézský součin \(B \times C\) je množina všech uspořádaných dvojic \((b, c)\), kde \(b \in B\) a \(c \in C\).

Mohutnost kartézského součinu je součin mohutností jednotlivých množin:

\(|B \times C| = |B| \times |C|.\)

Z množin máme \(|B| = 5\) a \(|C| = 3\).

Proto \(|B \times C| = 5 \times 3 = 15\).

Řešení příkladu:

Počet podmnožin množiny o velikosti \( k \) z množiny velikosti \( n \) je dán vzorcem pro kombinace:

\( \text{C}(n, k) = \frac{n!}{k! \times (n-k)!} \).

Pro \( n = 6 \) a \( k = 3 \) tedy:

\( \text{C}(6, 3) = \frac{6!}{3! \times 3!} = \frac{720}{6 \times 6} = \frac{720}{36} = 20 \).

Tedy existuje \( 20 \) podmnožin o velikosti \( 3 \) v množině \( D \).

Řešení příkladu:

Trojciferné číslo má první číslici od \(1\) do \(9\) \((0\) nemůže být na prvním místě\()\), druhá a třetí číslice od \(1\) do \(9\), ale všechny číslice musí být různé.

Postup výpočtu:

– První číslice: \(9\) možností \((1–9)\).

– Druhá číslice: \(10\) možností minus ta jedna již použitá = \(9\) možností.

– Třetí číslice: \(10\) možností minus \(2\) již použitých = \(8\) možností.

Celkem tedy:

\(9 \times 9 \times 8 = 648\).

Tedy mohutnost množiny je \(648\).

Řešení příkladu:

Nejprve spočítáme mohutnosti jednotlivých množin.

Množina \(E\): sudá čísla menší než \(30\) jsou \(2,4,6,\ldots,28\).

Počet těchto čísel:

\(\frac{28}{2} = 14\), tedy \(|E| = 14\).

Množina \(F\): lichá čísla menší než \(20\) jsou \(1,3,5,\ldots,19\).

Počet těchto čísel:

\(\frac{19+1}{2} = 10\), tedy \(|F| = 10\).

Protože \(E\) a \(F\) jsou disjunktní (žádné číslo není sudé i liché zároveň), platí:

\(|E \cup F| = |E| + |F| = 14 + 10 = 24\).

Řešení příkladu:

Počet všech podmnožin množiny o velikosti \(n\) je \(2^n\).

Protože \(|G|=4\), pak:

\(|\mathcal{P}(G)| = 2^4 = 16\).

Tedy množina všech podmnožin množiny \(G\) má mohutnost \(16\).

Řešení příkladu:

Celkový počet podmnožin množiny o 5 prvcích je \(2^5 = 32\).

Počet podmnožin, které neobsahují žádný prvek, je právě jedna – prázdná množina.

Tedy počet podmnožin obsahujících alespoň jeden prvek je:

\(32 – 1 = 31\).

Řešení příkladu:

Mohutnost kartézského součinu množin \(\{1,2,3\} \times \{4,5\}\) je součin jejich mohutností.

První množina má \(3\) prvky, druhá \(2\) prvky.

Proto:

\(|\{1,2,3\} \times \{4,5\}| = 3 \times 2 = 6\).

Řešení příkladu:

Průnik množin \(J\) a \(K\) jsou prvky, které jsou zároveň v \(J\) i v \(K\).

Prvky \(J\) jsou \(1,2,3,4,5,6,7\).

Prvky \(K\) jsou \(2,4,6,8\).

Průnik je tedy \( \{2,4,6\} \), protože \(8\) není v \(J\).

Tedy \(|J \cap K| = 3\).

Řešení příkladu:

Množina \(L\) obsahuje čísla \(-3, -2, -1, 0, 1, 2, 3\).

Množina \(M\) obsahuje pouze kladná čísla z \(L\), tedy \(1, 2, 3\).

Mohutnost \(M\) je počet těchto čísel, což je \(3\).

Tedy \(|M| = 3\).

Řešení příkladu:

Množina \(A\) obsahuje všechna přirozená čísla od \(1\) do \(15\), která jsou dělitelná 3.

Jsou to čísla: \(3, 6, 9, 12, 15\).

Počet těchto čísel spočítáme jako:

\(\left\lfloor \frac{15}{3} \right\rfloor = 5\).

Tedy \(|A| = 5\).

Řešení příkladu:

Každý prvek posloupnosti může být buď \( 0 \), nebo \( 1 \), tedy \( 2 \) možnosti.

Posloupnost má délku \( 4 \), takže celkový počet různých posloupností je:

\( 2^4 = 16 \).

Tedy mohutnost množiny je \( 16 \).

Řešení příkladu:

Počet funkcí z množiny s \(m\) prvky do množiny s \(n\) prvky je \(n^m\).

Zde je \(m = |B| = 3\) a \(n = |C| = 4\).

Počet funkcí je tedy:

\(4^3 = 64\).

Tedy mohutnost množiny všech funkcí je \(64\).

Řešení příkladu:

Počet dvojic (podmnožin velikosti \( 2 \)) z množiny o \( 6 \) prvcích je kombinace:

\( \frac{6!}{2! \times 4!} = \frac{720}{2 \times 24} = \frac{720}{48} = 15 \).

Tedy existuje \( 15 \) různých dvojic.

Řešení příkladu:

Počet podmnožin o velikosti \(1\) z množiny o velikosti \(3\) je:

\(\frac{3!}{1! \cdot 2!} = 3\).

Tedy jsou tři takové podmnožiny, každá obsahuje jeden z prvků \(x\), \(y\) nebo \(z\).

Řešení příkladu:

Každý prvek trojice může být jeden z \(5\) prvků množiny \(F\).

Proto počet všech uspořádaných trojic je:

\(5 \times 5 \times 5 = 5^3 = 125\).

Řešení příkladu:

Počet podmnožin s \( 0 \) prvky (prázdná množina):

\( \frac{5!}{0! \times 5!} = \frac{120}{1 \times 120} = 1 \).

Počet podmnožin s \( 1 \) prvkem:

\( \frac{5!}{1! \times 4!} = \frac{120}{1 \times 24} = 5 \).

Počet podmnožin s \( 2 \) prvky:

\( \frac{5!}{2! \times 3!} = \frac{120}{2 \times 6} = 10 \).

Celkem tedy podmnožin s nejvýše \( 2 \) prvky:

\( 1 + 5 + 10 = 16 \).

Řešení příkladu:

Pro každou pozici v řetězci jsou \(3\) možnosti \((a, b, c)\).

Počet všech řetězců délky \(3\) je tedy:

\(3^3 = 27\).

Řešení příkladu:

\(|H| = 4\), \(|I| = 4\).

Průnik \(H \cap I = \{3,4\}\), tedy \(|H \cap I| = 2\).

Mohutnost sjednocení spočítáme jako:

\(|H \cup I| = |H| + |I| – |H \cap I| = 4 + 4 – 2 = 6\).

Řešení příkladu:

Počet permutací množiny o \(n\) prvcích je \(n!\).

Pro množinu \(J\) s \(4\) prvky je to:

\(4! = 4 \times 3 \times 2 \times 1 = 24\).

Tedy mohutnost množiny všech permutací je \(24\).

Řešení příkladu:

Množina \(K\) obsahuje všechna celá čísla od \(-3\) do \(3\), tedy:

\(-3, -2, -1, 0, 1, 2, 3\).

Počet těchto prvků je:

\(3 – (-3) + 1 = 7\).

Tedy \(|K| = 7\).

Řešení příkladu:

Počet možností pro \(a\) je \(3\), pro \(b\) je \(2\).

Celkový počet uspořádaných dvojic je tedy:

\(3 \times 2 = 6\).

Řešení příkladu:

Počet všech podmnožin množiny o \(n\) prvcích je \(2^n\).

Pro \(n = 5\) máme:

\(2^5 = 32\).

Tedy množina \(L\) má \(32\) podmnožin.

Řešení příkladu:

Počet funkcí z množiny s \(m\) prvky do množiny s \(n\) prvky je \(n^m\).

Zde \(m = 2\), \(n = 3\).

Počet funkcí je:

\(3^2 = 9\).

Řešení příkladu:

Hledáme počet uspořádaných trojic z \(\{0,1,2\}\), jejichž součet je \(3\).

Možné trojice jsou například:

\((1,1,1), (2,1,0), (2,0,1), (1,2,0), (0,2,1), (1,0,2), (0,1,2)\).

Vyjmenováním nebo systematickým zkoumáním zjistíme, že těchto trojic je \(7\).

Řešení příkladu:

Každý znak má \(26\) možností.

Délka kódu je \(5\), takže počet všech kódů je:

\(26^5 = 11\,881\,376\).

Řešení příkladu:

Průnik obsahuje prvky, které jsou v obou množinách:

\(P \cap Q = \{3,4\}\).

Tedy \(|P \cap Q| = 2\).

Řešení příkladu:

Počet podmnožin o velikosti \( 3 \) z množiny o \( 4 \) prvcích je:

\( \frac{4!}{3! \times 1!} = \frac{24}{6 \times 1} = 4 \).

Řešení příkladu:

První prvek může být vybrán z \(5\) možností.

Druhý prvek musí být jiný než první, tedy \(4\) možnosti.

Třetí prvek musí být jiný než první dva, tedy \(3\) možnosti.

Celkový počet posloupností je:

\(5 \times 4 \times 3 = 60\).

Řešení příkladu:

Velikost množiny \( S \) je \( 6 \).

Počet podmnožin s přesně \( k \) prvky je \( \frac{6!}{k!(6-k)!} \).

Sudý počet prvků znamená \( k = 0, 2, 4, 6 \).

Počet těchto podmnožin je:

\( \frac{6!}{0! \times 6!} + \frac{6!}{2! \times 4!} + \frac{6!}{4! \times 2!} + \frac{6!}{6! \times 0!} = 1 + 15 + 15 + 1 = 32 \).

Tedy je \( 32 \) podmnožin s sudým počtem prvků.

Řešení příkladu:

Počet podmnožin s přesně \( 4 \) prvky z množiny o \( 7 \) prvcích je dán kombinačním číslem:

\( \frac{7!}{4! \cdot 3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35 \).

Tedy množina \( A \) má \( 35 \) podmnožin obsahujících právě \( 4 \) prvky.

Řešení příkladu:

Počet všech funkcí z množiny o \(m\) prvcích do množiny o \(n\) prvcích je \(n^m\).

Zde \(m = 3\), \(n = 2\).

Počet funkcí je:

\(2^3 = 8\).

Tedy existuje \(8\) různých funkcí z \(X\) do \(Y\).

Řešení příkladu:

Množina hodnot pro \(x\) bez prvku \(3\) je \(\{1,2,4\}\), tedy má 3 prvky.

Množina hodnot pro \(y\) má \(3\) prvky.

Celkový počet uspořádaných dvojic je:

\(3 \times 3 = 9\).

Řešení příkladu:

Hledáme počet posloupností délky \( 4 \) s přesně dvěma jedničkami a zbytkem nul.

Počet je roven počtu výběrů pozic pro jedničky v délce \( 4 \):

\( \frac{4!}{2! \cdot 2!} = 6 \).

Řešení příkladu:

Množina podmnožin, které neobsahují prvek 5, jsou vlastně všechny podmnožiny množiny \(B‘ = \{1,2,3,4\}\).

Počet podmnožin množiny o 4 prvcích je \(2^4 = 16\).

Tedy počet podmnožin množiny \(B\), které neobsahují prvek \(5\), je \(16\).

Řešení příkladu:

První prvek může být vybrán ze \(4\) možností.

Druhý prvek z \(3\) zbývajících možností.

Třetí prvek z \(2\) zbývajících možností.

Celkový počet takových trojic je:

\(4 \times 3 \times 2 = 24\).

Řešení příkladu:

Počet všech funkcí z množiny o \(2\) prvcích do množiny o \(4\) prvcích je \(4^2 = 16\).

Funkce musí být prosté (injektivní), tedy hodnoty na \(1\) a \(2\) musí být různé.

Pro první prvek je \(4\) možnosti, pro druhý pak \(3\) možnosti (jiný než první).

Celkový počet injektivních funkcí je:

\(4 \times 3 = 12\).

Řešení příkladu:

Celkový počet podmnožin množiny o \(5\) prvcích je \(2^5 = 32\).

Počet podmnožin, které neobsahují ani \(a\), ani \(b\), je počet podmnožin množiny \(\{c,d,e\}\), tedy \(2^3 = 8\).

Počet podmnožin obsahujících \(a\), nebo \(b\), nebo oba je:

\(32 – 8 = 24\).

Řešení příkladu:

\(|X| = 5\), \(|Y| = 4\).

Průnik \(X \cap Y = \{4,5\}\), tedy \(|X \cap Y| = 2\).

Mohutnost sjednocení je:

\(|X \cup Y| = |X| + |Y| – |X \cap Y| = 5 + 4 – 2 = 7\).

Řešení příkladu:

Množina má \( 4 \) prvky.

Podmnožiny s lichým počtem prvků jsou ty s \( 1 \) a \( 3 \) prvky:

Počet těchto podmnožin je:

\( \frac{4!}{1! \cdot 3!} + \frac{4!}{3! \cdot 1!} = 4 + 4 = 8 \).

Řešení příkladu:

Sudé prvky v množině \(A\) jsou \(2\) a \(4\), tedy \(2\) sudé prvky celkem.

Chceme podmnožiny s právě dvěma sudými prvky, tedy musí obsahovat oba sudé prvky \(2\) i \(4\).

Zbývající prvky jsou \(1, 3, 5\) (liché), jejich počet je \(3\).

Podmnožina může obsahovat libovolnou kombinaci těchto lichých prvků (od \(0\) do \(3)\).

Počet podmnožin, které obsahují oba sudé prvky a libovolné liché, je počet podmnožin množiny \(\{1,3,5\}\), tedy \(2^3 = 8\).

Tedy odpověď je \(8\).

Řešení příkladu:

Funkce přiřazuje každému prvku z \( X \) hodnotu z \( Y \).

Chceme funkce, které mají právě jedno místo s hodnotou \( 1 \) a zbytek \( 0 \).

Počet takových funkcí odpovídá počtu možností vybrat přesně jedno místo z \( 4 \), kde bude hodnota \( 1 \):

\( \frac{4!}{1! \cdot 3!} = 4 \).

Řešení příkladu:

Počet všech uspořádaných dvojic je \(3 \times 4 = 12\).

Musíme odečíst dvojice, kde \(a = b\), tedy kde \(a\) a \(b\) jsou stejné.

Společný prvek je jen \(3\), takže jedna taková dvojice \((3,3)\).

Počet dvojic s \(a \neq b\) je:

\(12 – 1 = 11\).

Řešení příkladu:

Chceme uspořádané trojice, kde se žádný prvek neopakuje a všechny prvky z množiny \(\{x,y,z\}\) jsou použity.

Počet permutací 3 prvků je \(3! = 6\).

Řešení příkladu:

Celkový počet podmnožin množiny o 4 prvcích je \(2^4 = 16\).

Počet podmnožin, které neobsahují žádný prvek (prázdná množina), je 1.

Počet podmnožin obsahujících alespoň jeden prvek je tedy:

\(16 – 1 = 15\).

Řešení příkladu:

Množina má \(6\) prvků.

Podmnožiny s sudým počtem prvků mají velikost \(0\), \(2\), \(4\) nebo \(6\).

Počet podmnožin je:

\( \frac{6!}{0!(6-0)!} + \frac{6!}{2!(6-2)!} + \frac{6!}{4!(6-4)!} + \frac{6!}{6!(6-6)!} = 1 + 15 + 15 + 1 = 32 \).

Řešení příkladu:

Počet všech funkcí z množiny o 3 prvcích do množiny o 2 prvcích je \(2^3 = 8\).

Injektivní funkce nemůže existovat, protože nelze přiřadit 3 různé prvky do 2 bez opakování hodnoty.

Tedy počet injektivních funkcí je 0.

Počet neinjektivních funkcí je tedy celkový počet funkcí, tedy 8.

Řešení příkladu:

Celkový počet funkcí je \(2^4 = 16\).

Počet funkcí, které nemají žádné \(a\), tedy mají všechny hodnoty \(b\), je \(1\) (konstantní funkce na \(b\)).

Počet funkcí, které mají alespoň jedno \(a\), je tedy:

\(16 – 1 = 15\).

Řešení příkladu:

Počet podmnožin o velikosti \(3\) z množiny o \(5\) prvcích je:

\( \frac{5!}{3! \cdot 2!} = 10 \).

Řešení příkladu:

Každý prvek množiny \(A\) může být v množině \(X\), nebo v množině \(Y\), nebo v žádné z nich.

Prvky nemohou být zároveň v \(X\) i v \(Y\), protože \(X \cap Y = \emptyset\).

Pro každý prvek tedy máme \(3\) možnosti: být v \(X\), být v \(Y\), nebo nebýt v žádné z množin.

Celkový počet takových dvojic je:

\(3^4 = 81\).

Řešení příkladu:

Množina \( A \) má \( 8 \) prvků.

Podmínka: podmnožina nesmí obsahovat prvek \( 1 \), tedy vybíráme z množiny \( B = A \setminus \{1\} = \{2,3,4,5,6,7,8\} \), která má \( 7 \) prvků.

Počet podmnožin \( B \) s sudým počtem prvků je:

Velikost podmnožiny může být \( 0, 2, 4, 6 \) (sudé počty menší nebo rovné \( 7 \)). Pozor, protože \( 7 \) je liché, nemůžeme mít sudou podmnožinu velikosti \( 7 \).

Počet podmnožin o velikosti \( k \) je \( \frac{7!}{k!(7-k)!} \).

Počet podmnožin s sudým počtem prvků je tedy součet:

\( \frac{7!}{0!(7-0)!} + \frac{7!}{2!(7-2)!} + \frac{7!}{4!(7-4)!} + \frac{7!}{6!(7-6)!} \).

Vypočítáme jednotlivé členy:

\( \frac{7!}{0!(7-0)!} = 1 \)

\( \frac{7!}{2!(7-2)!} = \frac{7 \cdot 6}{2} = 21 \)

\( \frac{7!}{4!(7-4)!} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2} = 35 \)

\( \frac{7!}{6!(7-6)!} = \frac{7}{1} = 7 \)

Součet je \( 1 + 21 + 35 + 7 = 64 \).

Odpověď: Existuje \( 64 \) podmnožin množiny \( A \), které neobsahují prvek \( 1 \) a mají sudý počet prvků.

Řešení příkladu:

Celkový počet všech funkcí z množiny o \( 4 \) prvcích do množiny o \( 3 \) prvcích je \( 3^4 = 81 \).

Funkce, které jsou konstantní (mají stejnou hodnotu na všech \( 4 \) prvcích), je přesně \( 3 \) (jedna pro každou hodnotu \( a, b, c \)).

Chceme spočítat počet funkcí, které nejsou konstantní a mají hodnotu \( a \) nejméně na \( 2 \) prvcích.

Nejprve spočítáme počet funkcí s hodnotou \( a \) právě na \( k \) prvcích, kde \( k \geq 2 \).

Pro fixní \( k \) vybíráme \( k \) prvků z \( 4 \), kde bude hodnota \( a \), počet možností je \( \frac{4!}{k!(4-k)!} \).

Na zbylých \( 4 – k \) prvcích musí být hodnoty z \( \{b,c\} \), tedy \( 2 \) možnosti pro každý z těchto prvků.

Počet funkcí pro pevné \( k \) je tedy:

\( \frac{4!}{k!(4-k)!} \cdot 2^{4-k} \).

Sečteme pro \( k = 2, 3, 4 \):

Pro \( k=2 \): \( \frac{4!}{2!(4-2)!} \cdot 2^2 = 6 \cdot 4 = 24 \)

Pro \( k=3 \): \( \frac{4!}{3!(4-3)!} \cdot 2^1 = 4 \cdot 2 = 8 \)

Pro \( k=4 \): \( \frac{4!}{4!(4-4)!} \cdot 2^0 = 1 \cdot 1 = 1 \)

Celkem \( 24 + 8 + 1 = 33 \).

Z těchto \( 33 \) funkcí je jedna konstantní (ta s \( a \) na všech \( 4 \) prvcích), kterou musíme odečíst, protože nechceme konstantní funkce.

Odpověď je tedy \( 33 – 1 = 32 \).

Řešení příkladu:

Množina má 6 prvků. Počet všech podmnožin je \(2^6 = 64\).

Chceme spočítat počet podmnožin, které obsahují alespoň jeden prvek z \(\{1,2\}\) a zároveň alespoň jeden prvek z \(\{5,6\}\).

Použijeme princip inkluze a vyloučení:

Definujme množiny:

• \(X =\) množiny, které neobsahují žádný prvek z \(\{1,2\}\)
• \(Y =\) množiny, které neobsahují žádný prvek z \(\{5,6\}\)

Chceme počet podmnožin mimo \(X \cup Y\), tedy \( |(X \cup Y)^c| = 2^6 – |X \cup Y| \).

Počet množin v \(X\): Můžeme vybírat pouze z \(\{3,4,5,6\}\), tj. \(2^4 = 16\).

Počet množin v \(Y\): Můžeme vybírat pouze z \(\{1,2,3,4\}\), tj. \(2^4 = 16\).

Počet množin v \(X \cap Y\): Můžeme vybírat pouze z \(\{3,4\}\), tj. \(2^2 = 4\).

Podle inkluze-vyloučení:

\(|X \cup Y| = |X| + |Y| – |X \cap Y| = 16 + 16 – 4 = 28\).

Odpověď je tedy:

\(64 – 28 = 36\).

Řešení příkladu:

Máme množiny: definiční obor \( X = \{1,2,3,4,5\} \), cílovou množinu \( Y = \{a,b,c,d\} \).

Celkový počet funkcí je \( 4^5 = 1024 \).

Chceme počet funkcí, které jsou surjektivní, tj. pokrývají všechny \( 4 \) hodnoty v obraze.

Použijeme inkluzi-vyloučení:

Nechť \( A_i \) je množina funkcí, které neobsahují prvek \( y_i \in Y \) v obraze.

Pak podle principu inkluze-vyloučení:

\[ |\text{surjektivní}| = \sum_{k=0}^{4} (-1)^k \cdot \frac{4!}{k!(4-k)!} \cdot (4 – k)^5 \]

Počítáme jednotlivé členy:

Pro \( k=0 \): \( \frac{4!}{0!(4-0)!} \cdot 4^5 = 1 \cdot 1024 = 1024 \)

Pro \( k=1 \): \( \frac{4!}{1!(4-1)!} \cdot 3^5 = 4 \cdot 243 = 972 \)

Pro \( k=2 \): \( \frac{4!}{2!(4-2)!} \cdot 2^5 = 6 \cdot 32 = 192 \)

Pro \( k=3 \): \( \frac{4!}{3!(4-3)!} \cdot 1^5 = 4 \cdot 1 = 4 \)

Pro \( k=4 \): \( \frac{4!}{4!(4-4)!} \cdot 0^5 = 1 \cdot 0 = 0 \)

Dosadíme do vzorce:

\[ 1024 – 972 + 192 – 4 + 0 = 240 \]

Odpověď: Počet surjektivních funkcí je \( 240 \).

Řešení příkladu:

Chceme spočítat počet uspořádaných dvojic \( (X,Y) \), kde \( X, Y \subseteq A \) a \( X \subseteq Y \).

Postup:

Vyberme nejdříve množinu \( Y \). Počet možností je \( 2^{10} = 1024 \).

Pro fixované \( Y \) je počet možných množin \( X \) podmnožin \( Y \) roven \( 2^{|Y|} \), protože \( X \) může být libovolná podmnožina \( Y \).

Celkový počet dvojic je tedy součet přes všechny \( Y \):

\[ \sum_{k=0}^{10} \frac{10!}{k!(10-k)!} \cdot 2^k \]

Protože existuje \( \frac{10!}{k!(10-k)!} \) množin \( Y \) o velikosti \( k \).

Vzorec lze rozepsat jako:

\[ \sum_{k=0}^{10} \frac{10!}{k!(10-k)!} 2^k = (1 + 2)^{10} = 3^{10} \]

Odpověď: Počet uspořádaných dvojic je \( 3^{10} = 59049 \).

Řešení příkladu:

Chceme spočítat počet trojic podmnožin \(A,B,C\) tak, aby jejich sjednocení pokrylo celou množinu \(\{1,2,3,4,5\}\).

Pro každý prvek \(x \in \{1,2,3,4,5\}\) platí, že musí být v alespoň jedné z množin \(A, B, C\).

Pro každý prvek existuje \(2^3 = 8\) možností, zda je či není v množinách \(A,B,C\) (každá množina může prvek obsahovat nebo neobsahovat).

Musíme však vyloučit možnost, kdy prvek není v žádné množině (1 možnost).

Pro každý prvek je tedy počet možností umístění do množin \(A,B,C\), aby byl alespoň v jedné, roven \(8 – 1 = 7\).

Protože máme 5 prvků nezávislých, celkový počet uspořádaných trojic je:

\(7^5 = 16807\).

Řešení příkladu:

Funkce je definovaná na 5 prvcích množiny \(A\).

Podmínka 1: funkce je injektivní na prvcích \(\{1,2,3\}\), tj. hodnoty na těchto prvcích jsou různé.

Podmínka 2: funkce má na prvcích \(\{4,5\}\) stejnou hodnotu.

Postup:

1. Nejprve vybereme hodnoty na prvcích \(1,2,3\) tak, aby byly různé. Počet injektivních zobrazení z \(3\) prvků do \(4\) prvků je:

\(P(4,3) = 4 \times 3 \times 2 = 24\).

2. Na prvcích \(4\) a \(5\) musí být stejná hodnota. Tato hodnota může být libovolná z množiny \(B\), ale musí být zvolena nezávisle na hodnotách \(1,2,3,\)?

Nezávisle? Ne, protože hodnoty na \(4\) a \(5\) nemusí být různé od hodnot \(1,2,3,\) nemusí být injektivní, pouze musí být konstantní.

Protože injektivita je požadována jen na \(1,2,3,\) hodnotu na \(4,5\) můžeme zvolit jakoukoliv z \(4\) hodnot.

Celkem tedy počet funkcí je:

\(24 \times 4 = 96\).

Řešení příkladu:

Požadujeme, aby dvojice podmnožin \((X,Y)\) splňovala:

• \(X \cap Y = \emptyset\) (prvky jsou v \(X\) nebo v \(Y\), ale ne v obou)
• \(X \cup Y = \{1,2,3,4,5,6\}\) (každý prvek je v \(X\) nebo v \(Y\))

Tedy každý prvek z množiny je buď v \(X\), nebo v \(Y\), žádný prvek není mimo obě množiny a žádný není v obou současně.

Pro každý prvek máme přesně 2 možnosti – přiřadit ho do \(X\) nebo do \(Y\).

Počet takových dvojic je tedy:

\(2^6 = 64\).

Řešení příkladu:

Nejprve spočítáme počet uspořádaných dvojic \((X,Y)\), kde \(X, Y \subseteq \{1,2,3,4,5\}\) a \(X \cup Y = \{1,2,3,4,5\}\).

Pro každý prvek máme 3 možnosti:

• prvek je jen v \(X\),
• prvek je jen v \(Y\),
• prvek je v \(X\) i v \(Y\).

Protože sjednocení musí být celé \(\{1,2,3,4,5\}\), žádný prvek nesmí být mimo obě množiny.

Celkový počet takových dvojic je tedy \(3^5 = 243\).

Chceme ale, aby \(X \cap Y \neq \emptyset\), tedy existoval alespoň jeden prvek v obou množinách.

Vyloučíme případy, kdy \(X \cap Y = \emptyset\).

Tyto případy znamenají, že pro každý prvek je pouze možnost „jen v \(X\)“ nebo „jen v \(Y\)“.

Počet takových dvojic je \(2^5 = 32\).

Odpověď je tedy:

\(243 – 32 = 211\).

Řešení příkladu:

Máme podmínku: \(A \subseteq B \subseteq C \subseteq \{1,2,3,4\}\).

Pro každý prvek množiny rozhodujeme, do kterých z množin \(A, B, C\) bude patřit, přičemž musí platit: pokud je prvek v \(A\), pak je i v \(B\) a \(C\), pokud je v \(B\), pak musí být i v \(C\).

Tedy existuje přesně 4 možné stavy pro každý prvek:

• není v \(C\) (tedy není v \(B\) ani \(A\)),
• je v \(C\), ale ne v \(B\),
• je v \(B\), ale ne v \(A\),
• je v \(A\).

Počet možností pro každý prvek je tedy \(4\).

Celkový počet trojic je tedy:

\(4^4 = 256\).

Řešení:

Počet všech podmnožin množiny \(M\) o velikosti přesně 3 prvky se vypočítá pomocí kombinatorického vzorce pro výběr \(k\) prvků z \(n\) prvků, což je:

\(\frac{6!}{3! \cdot (6-3)!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20.\)

Tedy je \(20\) podmnožin o velikosti \(3\).

Řešení:

Celkový počet podmnožin množiny o \(5\) prvcích je \(2^5 = 32\).

Podmnožiny, které nevyhovují podmínce (tj. obsahují méně než \(2\) prvky), jsou podmnožiny prázdné a jednoprvkové.

Počet prázdných podmnožin je \(1\).

Počet jednoprvkových podmnožin je \(\frac{5!}{1! \cdot (5-1)!} = 5.\)

Celkem nevyhovujících je tedy \(1 + 5 = 6\).

Počet podmnožin obsahujících alespoň \(2\) prvky je tedy \(32 – 6 = 26.\)

Řešení:

Pro každého prvku z množiny \(P\) máme tři možnosti, jak může být zařazen v dvojici \((A,B)\) s podmínkou \(A \subseteq B\):

• prvek není v \(B\) → pak není ani v \(A\),
• prvek je v \(B\), ale není v \(A\),
• prvek je v \(A\) (tedy i v \(B\)).

Těchto možností je pro každý prvek \(3\), tedy celkový počet takových dvojic je \(3^{10} = 59049.\)

Řešení:

Nejdříve vybereme, které 2 prvky z množiny \(\{a,b,c,d\}\) budou obrazy funkce. Počet takových dvojic je:

\(\frac{4!}{2! \cdot (4-2)!} = 6.\)

Každá funkce z množiny o \(3\) prvcích do této dvojice může mít obraz právě těchto \(2\) prvků, tedy funkce jsou na množinu o \(2\) prvcích.

Počet funkcí \(f : \{1,2,3\} \to \{x,y\}\) (kde \(\{x,y\}\) je vybraná dvojice) je \(2^3 = 8\).

Musíme však odečíst funkce, které mají obraz menší než \(2\), tedy konstantní funkce (kde obraz je jen \(1\) prvek).

Počet konstantních funkcí je právě \(2\) (všechny prvky na \(x\) nebo všechny na \(y\)).

Takže počet funkcí s obrazem přesně \(2\) je \(8 – 2 = 6\) pro každou dvojici.

Celkový počet takových funkcí je tedy \(6 \times 6 = 36.\)

Řešení:

Celkový počet podmnožin množiny o \(7\) prvcích je \(2^7 = 128.\)

Počet podmnožin se sudým počtem prvků můžeme spočítat pomocí vlastnosti binomických koeficientů:

Součet všech \(\frac{7!}{k! \cdot (7-k)!}\) pro sudá \(k\) je:

\(\frac{1}{2} \cdot 2^7 = 64.\)

Tedy podmnožin se sudým počtem prvků je \(64\).

Řešení:

Počet injektivních funkcí je počet všech permutací výběru \(4\) prvků z \(6\) prvků, tedy:

\(6 \times 5 \times 4 \times 3 = 360.\)

Řešení:

Pro každý prvek ze základní množiny máme \(4\) možnosti zařazení do trojice \((A,B,C)\) s podmínkou \(A \subseteq B \subseteq C\):

1. prvek není v \(C\) (a tedy není v \(B\) ani v \(A\))
2. prvek je v \(C\), ale není v \(B\) (a tedy není v \(A\))
3. prvek je v \(B\), ale není v \(A\) (musí být v \(C\))
4. prvek je v \(A\) (tedy i v \(B\) a v \(C\))

Těchto možností je 4 pro každý z 3 prvků, takže celkem \(4^3 = 64\) trojic.

Řešení:

Surjektivní funkce musí mít obraz rovný celé množině \(\{a,b,c,d\}\).

Jelikož doména má \(3\) prvky a kodoména \(4\) prvky, není možné mít surjektivní funkci, protože do \(3\) prvků nemůžeme pokrýt \(4\) prvky kodomény.

Tedy počet surjektivních funkcí je \(0\).

Řešení:

Podmnožiny, které neobsahují prvek \(3\), jsou všechny podmnožiny množiny \(\{1,2,4,5\}\), protože prvek \(3\) není v nich.

Počet všech podmnožin této čtyřprvkové množiny je \(2^4 = 16.\)

Řešení:

Každý prvek ze základní množiny může být zařazen do jednoho ze tří disjunktních „košů“:

• prvek je v \(A\),
• prvek je v \(B\),
• prvek není v \(A\) ani v \(B\).

Těchto možností je tedy \(3\) pro každý ze \(4\) prvků.

Celkový počet uspořádaných dvojic s disjunktními množinami \(A, B\) je tedy \(3^4 = 81.\)

Řešení:

Nejdříve si všimneme, že prvek \( 3 \) musí být v podmnožině \( A \). To znamená, že vybíráme podmnožiny z množiny \( S‘ = S \setminus \{3\} = \{1,2,4,5,6,7,8\} \), a k nim vždy přidáme prvek \( 3 \).

Chceme podmnožiny \( A \), které mají lichý počet prvků. Jelikož prvek \( 3 \) už máme zahrnutý, stačí, aby podmnožina z \( S‘ \) měla sudý počet prvků (protože lichý počet = \( 1 \) (prvek \( 3 \)) + sudý počet zbytku).

Množina \( S‘ \) má \( 7 \) prvků. Počet podmnožin se sudým počtem prvků je polovina všech podmnožin:

Celkový počet podmnožin množiny o \( 7 \) prvcích je \( 2^7 = 128 \).

Počet podmnožin se sudým počtem prvků je tedy \( \frac{128}{2} = 64 \).

Tedy celkový počet podmnožin \( A \) splňujících podmínky je \( 64 \).

Řešení:

Podmínky říkají, že \( A \) a \( B \) jsou disjunktní (nemají společné prvky) a jejich sjednocení je celá množina \( \{1,2,3,4,5\} \).

To znamená, že každý prvek této množiny je právě v jedné z množin \( A \) nebo \( B \).

Pro každý z \( 5 \) prvků máme tedy \( 2 \) možnosti – je v \( A \) nebo je v \( B \).

Celkový počet uspořádaných dvojic je tedy \( 2^5 = 32 \).

Řešení:

Celkový počet podmnožin množiny o \( 8 \) prvcích je \( 2^8 = 256 \).

Musíme spočítat součet počtu podmnožin velikosti \( 3 \), \( 4 \), \( 5 \) a \( 6 \).

Počet podmnožin velikosti \( k \) je dán vzorcem \( \frac{8!}{k! \cdot (8-k)!} \).

Vypočteme jednotlivě:

• \( k = 3: \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 \)
• \( k = 4: \frac{8!}{4! \cdot 4!} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70 \)
• \( k = 5: \frac{8!}{5! \cdot 3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 \)
• \( k = 6: \frac{8!}{6! \cdot 2!} = \frac{8 \times 7}{2 \times 1} = 28 \)

Součet: \( 56 + 70 + 56 + 28 = 210 \).

Tedy existuje \( 210 \) podmnožin splňujících podmínky.

Řešení:

Nejprve spočítáme celkový počet funkcí z množiny o \( 4 \) prvcích do množiny o \( 3 \) prvcích:

\( 3^4 = 81 \).

Počet injektivních funkcí lze spočítat pouze tehdy, pokud je velikost kodomény alespoň velikost domény. Zde je doména \( 4 \) prvky, kodoména \( 3 \), tedy není možné mít injektivní funkci, protože by neměla dostatek různých hodnot.

Tedy počet injektivních funkcí je \( 0 \).

Počet funkcí, které nejsou injektivní, je tedy celkový počet funkcí \( 81 \).

Řešení:

Každý prvek základní množiny musí být v právě jedné z množin \( A \), \( B \), \( C \), protože jejich sjednocení je celá množina a jsou navzájem disjunktní.

Pro každý prvek máme tedy \( 3 \) možnosti – zařadit jej do \( A \), nebo \( B \), nebo \( C \).

Počet uspořádaných trojic je tedy \( 3^3 = 27 \).

Řešení:

Prvky \( 1 \) a \( 2 \) musí být v podmnožině, prvek \( 6 \) nesmí být obsažen.

Zbývá nám tedy vybrat podmnožinu z množiny \( S‘ = \{3,4,5\} \), protože ostatní prvky jsou fixní (\( 1 \), \( 2 \) musí být a \( 6 \) nesmí být).

Počet všech podmnožin \( S‘ \) je \( 2^3 = 8 \).

Tedy existuje \( 8 \) podmnožin množiny \( \{1,2,3,4,5,6\} \), které obsahují \( 1 \) a \( 2 \) a neobsahují \( 6 \).

Řešení:

Počet všech funkcí je \(2^5 = 32\), protože každému z \(5\) prvků můžeme přiřadit \(0\) nebo \(1\).

Potřebujeme spočítat počet funkcí, kde hodnota \(1\) je přiřazena alespoň dvěma prvkům.

Nejprve spočítáme počet funkcí, kde je hodnota \(1\) přiřazena méně než dvěma prvkům, tedy buď žádnému nebo právě jednomu.

• Počet funkcí, kde není přiřazena žádná \(1\): pouze jedna funkce, kde všem prvkům je přiřazeno \(0\).
• Počet funkcí, kde je přiřazena právě jedna \(1\): vybereme, kterému z \(5\) prvků přiřadíme \(1\), ostatním \(0\), což je \(5\) funkcí.

Celkem tedy \(1 + 5 = 6\) funkcí mají méně než dvě hodnoty \(1\).

Počet funkcí s alespoň dvěma jedničkami je tedy \(32 – 6 = 26\).

Řešení:

Podmínka \( A \subseteq B \) znamená, že každý prvek \( A \) je zároveň v \( B \).

Postup:

1. Nejprve vybereme množinu \( B \) – ta může být libovolná podmnožina \( M \), tedy \( 2^7 = 128 \) možností.
2. Pro dané \( B \) vybíráme \( A \) jako libovolnou podmnožinu \( B \). Počet podmnožin \( B \) je \( 2^{|B|} \).

Celkový počet dvojic \( (A,B) \) s \( A \subseteq B \) je tedy součet přes všechny \( B \subseteq M \) počtu podmnožin \( A \subseteq B \):

\[ \sum_{k=0}^7 2^k \cdot 2^k = \sum_{k=0}^7 2^{2k} \]

Využijeme rozvoj Newtonova binomu:

\[ \sum_{k=0}^7 2^{2k} = (1+4)^7 = 5^7 = 78125. \]

Tedy existuje \( 78125 \) takových dvojic.

Řešení:

Prvky \( 2 \) a \( 5 \) nemohou být v podmnožině, takže vybíráme podmnožiny ze zbývajících \( 8 \) prvků: \( \{1,3,4,6,7,8,9,10\} \).

Počet podmnožin této množiny s velikostí menší než \( 5 \) je součet počtu podmnožin o velikosti \( 0 \), \( 1 \), \( 2 \), \( 3 \), a \( 4 \).

Počet podmnožin velikosti \( k \) je dán výpočtem \( \frac{8!}{k!(8-k)!} \).

Vypočteme součet:

\[ \frac{8!}{0!(8-0)!} + \frac{8!}{1!(8-1)!} + \frac{8!}{2!(8-2)!} + \frac{8!}{3!(8-3)!} + \frac{8!}{4!(8-4)!} \]

= \( 1 + 8 + 28 + 56 + 70 = 163 \).

Tedy existuje \( 163 \) takových podmnožin.

Řešení:

Podmínky jsou:

• \( A \subseteq B \)
• \( |B| = 4 \)

Postup řešení:

1. Nejprve vybereme množinu \( B \) o velikosti \( 4 \) z \( 6 \) prvků. Počet možností je dán výpočtem \( \frac{6!}{4!(6-4)!} = 15 \).
2. Pro každé \( B \) vybíráme \( A \) jako libovolnou podmnožinu \( B \). Počet podmnožin \( B \) je \( 2^4 = 16 \).

Celkový počet uspořádaných dvojic \( (A,B) \) je tedy \( 15 \times 16 = 240 \).

Řešení:

Podmínky znamenají, že množiny \(A, B, C\) jsou disjunktní a jejich sjednocení pokrývá celou množinu \(M\). Jinými slovy, každý prvek z \(M\) je právě v jedné z množin \(A\), \(B\) nebo \(C\).

Pro každý z \(9\) prvků máme \(3\) možnosti, kam jej zařadit: do \(A\), \(B\) nebo \(C\).

Tedy počet všech takových uspořádaných trojic je

\(3^9 = 19683.\)

Protože neexistují žádná další omezení, každý výběr je platný.

Řešení:

Celkový počet podmnožin množiny o \( 10 \) prvcích je \( 2^{10} = 1024 \).

Podmnožiny s velikostí sudou a alespoň \( 3 \) prvky jsou podmnožiny o velikosti \( 4 \), \( 6 \), \( 8 \), \( 10 \).

Vyjmenujme jednotlivé případy pomocí kombinací:

• \( k = 4 :\ \frac{10!}{4!(10-4)!} = 210 \)
• \( k = 6 :\ \frac{10!}{6!(10-6)!} = 210 \)
• \( k = 8 :\ \frac{10!}{8!(10-8)!} = 45 \)
• \( k = 10 :\ \frac{10!}{10!(10-10)!} = 1 \)

Sečteme všechny:

\( 210 + 210 + 45 + 1 = 466 \).

Tedy je \( 466 \) takových podmnožin.

Řešení:

Nejprve vybereme množinu \( B \) z množiny \( U \) o \( 12 \) prvcích tak, aby \( |B| = 7 \).

Počet takových množin je \( \frac{12!}{7!(12-7)!} = 792 \).

Pro každou takovou množinu \( B \) vybíráme \( A \) jako libovolnou podmnožinu \( B \).

Počet podmnožin množiny s \( 7 \) prvky je \( 2^7 = 128 \).

Celkový počet uspořádaných dvojic \( (A,B) \) je tedy \( 792 \times 128 = 101376 \).

Řešení:

Chceme podmnožiny, které obsahují prvek \(1\) nebo prvek \(2\), ale ne oba zároveň – jde o tzv. symetrický rozdíl množin \(\{1\}\) a \(\{2\}\).

Postup:

1. Celkem je \(10\) prvků, z toho \(2\) jsou speciální (\(1\) a \(2\)), ostatních je \(8\).
2. Podmnožiny mohou obsahovat:
• Prvek \(1\) a prvek \(2\) neobsahují – to je zakázáno.
• Prvek \(1\) je, prvek \(2\) není.
• Prvek \(2\) je, prvek \(1\) není.
3. Pro zbývajících \(8\) prvků vybíráme libovolnou podmnožinu.

Počet podmnožin obsahujících prvek \(1\), ale ne prvek \(2\) je \(2^8 = 256\).

Počet podmnožin obsahujících prvek \(2\), ale ne prvek \(1\) je také \(2^8 = 256\).

Tyto dvě množiny jsou disjunktní, takže celkový počet je \(256 + 256 = 512\).

Řešení:

Nejprve určíme sudé prvky v množině. Pokud \(X = \{1,2,3,4,5,6,7\}\), sudé prvky jsou \(\{2,4,6\}\), tedy \(3\) sudé prvky.

Chceme podmnožiny, které obsahují přesně tři sudé prvky, tedy musí obsahovat všechny sudé prvky.

Zbytek podmnožiny tvoří prvky z množiny lichých prvků \(L = \{1,3,5,7\}\) (\(4\) prvky).

Tyto prvky můžeme do podmnožiny zařadit libovolně.

Počet podmnožin z \(L\) je \(2^4 = 16\).

Tedy celkový počet podmnožin \(X\), které obsahují všechny \(3\) sudé prvky a libovolnou podmnožinu z lichých prvků, je \(16\).

Řešení:

Podmínka \( A \cap B = \emptyset \) znamená, že množiny \( A \) a \( B \) jsou disjunktní.

Máme celkem \( 5 \) prvků.

Postup:

1. Vybereme množinu \( A \) o velikosti \( 2 \) z \( 5 \) prvků. Počet možností je \( \frac{5!}{2!(5-2)!} = 10 \).
2. Zbývají prvky, které nejsou v \( A \), tedy \( 5 – 2 = 3 \) prvky.
3. Z těchto \( 3 \) zbývajících prvků vybereme množinu \( B \) o velikosti \( 3 \). Počet možností je \( \frac{3!}{3!(3-3)!} = 1 \).

Celkový počet uspořádaných dvojic je tedy \( 10 \times 1 = 10 \).

Řešení:

Podmínky:

• \( A \cup B = M \) – společně pokrývají všechny prvky.
• \( |A \cap B| = 2 \) – mají právě \( 2 \) společné prvky.

Postup:

1. Vybereme \( 2 \) prvky, které budou společné – počet možností je \( \frac{8!}{2!(8-2)!} = 28 \).
2. Zbývá \( 6 \) prvků, které musí být v \( A \cup B \), ale ne v průniku.
3. Každý z těchto \( 6 \) prvků může být v \( A \), v \( B \), ale nesmí být v obou najednou.
4. Pro každý prvek tedy máme \( 2 \) možnosti: přiřadit ho do \( A \) nebo do \( B \), ale ne do obou.
5. Počet možností pro zbývajících \( 6 \) prvků je tedy \( 2^6 = 64 \).

Celkový počet uspořádaných dvojic \( (A,B) \) je \( 28 \times 64 = 1792 \).

Řešení:

Prvky menší než \( 3 \) jsou \( 1 \) a \( 2 \). Podmínka říká, že v podmnožině nemůže být ani \( 1 \), ani \( 2 \).

Zbývá tedy množina \( \{3,4,5,6,7\} \) s \( 5 \) prvky.

Potřebujeme spočítat počet podmnožin této množiny o velikosti právě \( 3 \).

Počet je \( \frac{5!}{3!(5-3)!} = 10 \).

Řešení:

Chceme funkce, které používají právě \( 2 \) hodnoty z množiny \( \{a,b,c\} \).

Postup:

1. Nejprve vybereme dvojici hodnot, které bude funkce používat. Počet dvojic z \( 3 \) prvků je \( \frac{3!}{2!(3-2)!} = 3 \).
2. Funkce z množiny \( 4 \) prvků do \( 2 \) hodnot má \( 2^4 = 16 \) možných funkcí.
3. Mezi těmito funkcemi ale musíme odečíst ty, které používají jen jednu hodnotu (tedy konstantní funkce). Pro každou dvojici hodnot jsou \( 2 \) takové konstantní funkce (jedna pro každou hodnotu).
4. Takže funkce používající právě \( 2 \) různé hodnoty jsou \( 16 – 2 = 14 \) pro každou dvojici hodnot.

Celkem tedy počet takových funkcí je \( 3 \times 14 = 42 \).

Řešení:

Podmínky:

• \( A \subseteq B \)
• \( B \subseteq C \)
• \( |C| = 4 \)

Postup:

1. Vybereme množinu \( C \) o velikosti \( 4 \) z \( 6 \) prvků. Počet možností je \( \frac{6!}{4!(6-4)!} = 15 \).
2. Pro dané \( C \) vybíráme množinu \( B \), která je podmnožinou \( C \), tedy počet možností je \( 2^4 = 16 \).
3. Pro každé \( B \) vybíráme množinu \( A \), která je podmnožinou \( B \), počet možností je \( 2^{|B|} \).

Celkový počet trojic je tedy:

\( \sum_{k=0}^{4} \frac{4!}{k!(4-k)!} \cdot 2^{k} \), kde \( k = |B| \).

Vypočítáme tento součet:

\( \sum_{k=0}^{4} \frac{4!}{k!(4-k)!} 2^k = (1+2)^4 = 3^4 = 81 \).

Tedy pro každé \( C \) existuje \( 81 \) možností pro dvojici \( (A,B) \).

Celkový počet uspořádaných trojic je tedy \( 15 \times 81 = 1215 \).

Řešení:

Počet podmnožin o velikosti \(3\) je dán kombinacemi výběru \(3\) prvků z \(8\):

\(\frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56.\)

Řešení:

Sudé velikosti jsou \(0\), \(2\) a \(4\).

Počet podmnožin velikosti \(0\):

\(\frac{5!}{0! \cdot 5!} = 1\)

Počet podmnožin velikosti \(2\):

\(\frac{5!}{2! \cdot 3!} = \frac{5 \times 4}{2 \times 1} = 10\)

Počet podmnožin velikosti \(4\):

\(\frac{5!}{4! \cdot 1!} = 5\)

Celkem tedy \(1 + 10 + 5 = 16\) podmnožin.

Řešení:

Postup:

1. Vybereme množinu \(A\) o \(2\) prvcích z \(5\). Počet možností je \(\frac{5!}{2! \cdot 3!} = 10.\)
2. Protože \(A \subseteq B\), vybíráme \(B\) tak, aby obsahovala \(A\) a měla velikost \(3\).
3. Počet zbývajících prvků pro \(B\) je \(3 – 2 = 1\), vybíráme z \(5 – 2 = 3\) prvků mimo \(A\).
4. Počet možností je \(\frac{3!}{1! \cdot 2!} = 3.\)

Celkový počet uspořádaných dvojic \((A, B)\) je \(10 \times 3 = 30.\)

Řešení:

Fixujeme \(C = M\), počet možností je \(1\).

Počet podmnožin \(B\) množiny \(M\) je \(2^4 = 16\).

Pro každé \(B\) počet podmnožin \(A \subseteq B\) je \(2^{|B|}\).

Celkový počet trojic je tedy

\(\sum_{k=0}^4 \left(\frac{4!}{k! \cdot (4-k)!} \times 2^k\right) = (1+2)^4 = 3^4 = 81.\)

Řešení:

1. Vybereme množinu \(A\) o \(4\) prvcích z \(9\). Počet možností je \(\frac{9!}{4! \cdot 5!} = 126\).
2. Protože \(A \subseteq B\), vybíráme množinu \(B\) tak, aby obsahovala \(A\) a měla velikost \(5\).
3. Počet zbývajících prvků pro \(B\) je \(5 – 4 = 1\), který musí být vybrán z \(9 – 4 = 5\) prvků mimo \(A\).
4. Počet možností je \(\frac{5!}{1! \cdot 4!} = 5\).

Celkový počet uspořádaných dvojic \((A, B)\) je \(126 \times 5 = 630\).

Řešení:

Definiční obor má \(5\) prvků, obor hodnot \(4\) prvky.

Injektivní funkce mohou existovat pouze pokud je počet prvků definičního oboru menší nebo roven počtu prvků oboru hodnot.

Zde je \(5 > 4\), tedy žádná prostá funkce neexistuje.

Počet takových funkcí je \(0\).

Řešení:

Celkový počet funkcí je \(4^4 = 256\).

Použijeme princip inkluze-vyloučení:

1. Funkce bez \(a\): \(3^4 = 81\)
2. Podobně pro \(b, c, d\), tedy \(4\) množiny po \(81\) funkcích.
3. Funkce bez \(a, b\): \(2^4 = 16\), je \(6\) dvojic hodnot.
4. Funkce bez \(a, b, c\): \(1^4 = 1\), \(4\) trojice hodnot.

Počet surjektivních funkcí je:

\(256 – 4 \times 81 + 6 \times 16 – 4 \times 1 = 256 – 324 + 96 – 4 = 24\).

Řešení:

Každý prvek množiny \(M\) musí být v přesně jedné z množin \(A\) nebo \(B\).

Počet možností rozdělení prvků do dvou disjunktních množin je tedy \(2^7 = 128\).

Řešení:

Vybereme množinu \(B\) o \(4\) prvcích z \(5\). Počet možností je \(\frac{5!}{4! \cdot 1!} = 5.\)

Pro každé \(B\) vybíráme podmnožinu \(A\) z \(B\), tedy \(2^{4} = 16\) možností.

Celkem uspořádaných dvojic je \(5 \times 16 = 80.\)

Řešení:

Postup:

1. Vybereme množinu \(A\) o \(2\) prvcích z \(5\). Počet možností je \(\frac{5!}{2! \cdot 3!} = 10.\)
2. Protože \(A\) a \(B\) jsou disjunktní, vybíráme \(B\) o \(3\) prvcích z \(5 – 2 = 3\) zbývajících prvků.
3. Počet možností je \(\frac{3!}{3! \cdot 0!} = 1.\)

Celkový počet uspořádaných dvojic je \(10 \times 1 = 10.\)