Liczba wszystkich funkcji odwzorujących

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
xkatekx
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 22 kwie 2022, o 16:34
Płeć: Kobieta
wiek: 20
Podziękował: 12 razy

Liczba wszystkich funkcji odwzorujących

Post autor: xkatekx »

1. Wyznacz liczbę wszystkich funkcji odwzorujących zbiór 10-elementowy \(\displaystyle{ X}\) w zbiór 5-elementowy \(\displaystyle{ A}\).
To według mnie będzie tak, \(\displaystyle{ \left|X\right|=10 }\), \(\displaystyle{ \left| A\right| =5}\), \(\displaystyle{ f:X \rightarrow A}\)
Liczba wszystkich takich funkcji \(\displaystyle{ f}\) jest równa \(\displaystyle{ 5^{10}}\).
Dobrze?

2. Wyznacz liczbę wszystkich suriekcji odwzorujących zbiór 10-elementowy \(\displaystyle{ X}\) na zbiór 3-elementowy \(\displaystyle{ B}\).
To według mnie będzie tak, \(\displaystyle{ \left|X\right|=10 }\), \(\displaystyle{ \left| B\right| =3}\), \(\displaystyle{ f:X \xrightarrow{na} B}\)
\(\displaystyle{ s(10,3)= \sum_{k=0}^{3} (-1)^k {3 \choose k} (3-k)^{10} =55980}\)
Ale nie jestem pewna.

3. Wyznacz liczbę wszystkich iniekcji odwzorujących zbiór 7-elementowy \(\displaystyle{ C}\) w zbiór 10-elementowy \(\displaystyle{ X}\).
To według mnie będzie tak, \(\displaystyle{ \left|X\right|=10 }\), \(\displaystyle{ \left| C\right| =7}\)
\(\displaystyle{ \frac{10!}{(10-7)!}=604800}\) ?
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Liczba wszystkich funkcji odwzorujących

Post autor: janusz47 »

1.
\(\displaystyle{ f: X \rightarrow A, \ \ f: \ \ \{x_{1},x_{2},x_{3}, x_{4}, x_{4}, x_{6},x_{7},x_{8},x_{9}, x_{10} \} \rightarrow \{a_{1},a_{2},a_{3},a_{4}, a_{5} \}}\)

\(\displaystyle{ f(x_{1}) = a_{1} }\)
\(\displaystyle{ f(x_{1}) = a_{2} }\)
\(\displaystyle{ f(x_{1}) = a_{3} }\)
\(\displaystyle{ f(x_{1}) = a_{4} }\)
\(\displaystyle{ f(x_{1}) = a_{5} }\)

\(\displaystyle{ f(x_{2}) = a_{1} }\)
\(\displaystyle{ f(x_{2}) = a_{2} }\)
\(\displaystyle{ f(x_{2}) = a_{3} }\)
\(\displaystyle{ f(x_{2}) = a_{4} }\)
\(\displaystyle{ f(x_{2}) = a_{5} }\)

...............

\(\displaystyle{ f(x_{10}) = a_{1} }\)
\(\displaystyle{ f(x_{10}) = a_{2} }\)
\(\displaystyle{ f(x_{10}) = a_{3} }\)
\(\displaystyle{ f(x_{10}) = a_{4} }\)
\(\displaystyle{ f(x_{10}) = a_{5} }\)

\(\displaystyle{ a_{1}\cdot a_{2}\cdot a_{3} \cdot a_{4}\cdot a_{5} \ \ \cdot \ \ a_{1}\cdot a_{2}\cdot a_{3} \cdot a_{4}\cdot a_{5} \cdot \ \ ...\ \ \cdot a_{1} \cdot a_{2}\cdot a_{3} \cdot a_{4}\cdot a_{5} = 5^{10}. }\)

2.
\(\displaystyle{ g: X \xrightarrow{na} B, \ \ f: \{ x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9},x_{10}\}\xrightarrow{na} \{ b_{1},b_{2},b_{3}\} }\)


\(\displaystyle{ |X| =10 , \ \ |B| = 3 }\)

Niech \(\displaystyle{ S }\) będzie zbiorem wszystkich funkcji \(\displaystyle{ g : \ \ X \rightarrow B }\).

Niech \(\displaystyle{ W_{i} }\) będzie taką własnością , że element \(\displaystyle{ b_{i} \in B }\) nie jest obrazem funkcji \(\displaystyle{ g, }\)

wtedy \(\displaystyle{ N_{1} = (3-1)^{10} }\)

Ponieważ, każdy z dziesięciu elementów zbioru \(\displaystyle{ X }\) może być obrazem "na " funkcji \(\displaystyle{ g, }\) z każdym z dwóch pozostałych elementów zbioru \(\displaystyle{ B }\), więc na podstawie "Zasady Włączeń i Wyłaczeń " - liczba surjekcji zbioru \(\displaystyle{ X }\) na zbiór \(\displaystyle{ B }\) (liczba elementów zbioru \(\displaystyle{ S }\) nie posiadających własności \(\displaystyle{ W_{i}) }\) jest równa:

\(\displaystyle{ 3^{10} - {3\choose1} (3-1)^{10}+ {3\choose 2}(3-2)^{10}- {3\choose 3}(3-3)^{10} = 3^{10} - 3\cdot 2^{10} + 3\cdot 1^{10} - 0 = 55980 = \sum_{k=0}^{3} (-1)^{k} { 3\choose k} (3 -k)^{10}. }\)

3.
\(\displaystyle{ i: C \xrightarrow{1-1} X \ \ i: \{c_{1},c_{2},c_{3},c_{4},c_{5},c_{6},c_{7}\} \xrightarrow{1-1} \{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9},x_{10}\} }\)

Element \(\displaystyle{ c_{1} }\) może być obrazem każdego z \(\displaystyle{ 10 }\) elementów zbioru \(\displaystyle{ X }\)

Element \(\displaystyle{ c_{2} }\) może być obrazem każdego z \(\displaystyle{ 9 }\) elementów zbioru \(\displaystyle{ X }\)

.............................................................................

Element \(\displaystyle{ c_{7} }\) może być obrazem każdego z \(\displaystyle{ 4 }\) elementów zbioru \(\displaystyle{ X }\)

Stąd wynika, że liczba wszystkich injekcji (funkcji różnowartościowych) odwzorujących zbiór \(\displaystyle{ C }\) w zbiór \(\displaystyle{ X }\) jest równa:

\(\displaystyle{ 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3\cdot 2 \cdot 1} = \frac{10!}{(10 - 7)!} = \frac{10!}{3!} = 604800. }\)
ODPOWIEDZ