Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Rešitev

Preslikava $f$ je v relaciji $\sim {_N}$ z natanko tistimi preslikavami, pri katerih se elementa $c_1$ in $c_2$ pojavita med slikami dvakrat, element $c_3$ pa enkrat.
Nadalje, preslikava $f$ je v relaciji $\sim{_K}$ s tistimi preslikavami $g$, za katere je

$$g(1) = g(2), g(3) = g(4),$$

elementi $g(1)$, $g(3)$ in $g(5)$ pa so paroma različni. Nazadnje, preslikava $f$ je v relaciji $\sim{_{N,K}}$ z vsemi tistimi funkcijami, pri katerih se dva izmed treh elementov $\{c_1,c_2,c_3\}$ pojavita med slikami dvakrat, tretji pa enkrat.

Dokaz

Naj bo $N = \{a_1,...,a_n\}$ in $K = \{c_1,...,c_k\}$. Oglejmo si najprej relacijo $\sim{_N}$. Množico ekvivalenčnih razredov množice $K^N$ označimo s $[K^N]_N$.
Vzemimo preslikavo $f: N \to K$ in ji priredimo multimnožico $\mu= [f(a_1),...,f(a_n)]$ moči $n$ z elementi iz $K$. Multimnožica, ki pripada ekvivalentni preslikavi $g = f \circ \rho, \rho \in Sym(N)$, je enaka $\mu' = [f(\rho(a_1)),...,f(\rho(a_n))]$. Ker vrstni red pri navajanju elementov multimnožice ni pomemben, je $\mu = \mu'$. Zato lahko definiramo preslikavo

$\varphi: [K^N]_N \to \bar{\mathcal{K}}(K,n)$, $\varphi([f])= [f(a_1),...,f(a_n)]$.

Bijektivnost preslikave $\varphi$ dokažemo tako, da ji poiščemo inverzno preslikavo $\psi$, ki multimnožico $[b_1,...,b_n]$ moči $n$ z elementi iz $K$ preslika v ekvivalenčni razred preslikave $f: N \to K$, $f(a_i) = b_i$ za $i= 1,...,n$. Bralcu prepuščamo, da preveri, da sta $\varphi$ in $\psi$ vzajemno inverzni preslikavi. S tem smo dokazali:

$$|[K^N]_N|=|\bar{\mathcal{K}}(K,n)|= {k+n-1 \choose n}.$$

Preslikava $f: N \to K$ je injektivna, če in samo če je kratnost vsakega elementa multimnožice $\varphi([f])$ enaka $1$, se pravi, natanko tedaj, ko je $\varphi([f])$ v resnici podmnožica množice $K$ moči $n$. Zato je ekvivalenčnih razredov injektivnih preslikav natanko toliko kot $n$-elementnih podmnožic množice $K$.

$$|[(K^N)_s]_N|=|{K \choose n}|= {k \choose n}.$$

Število ekvivalenčnih razredov surjektivnih preslikav določimo tako, da multimnožici $\mu: K \to \mathbb{N}_0$, ki pripada preslikavi $f \in (K^N)_s$, priredimo multimnožico $\mu': K \to \mathbb{N}_0$, $\mu'(c) = \mu(c)-1$. Opazimo, da pravilo $\mu \mapsto \mu'$ podaja bijektivno preslikavo med multimnožicami $\mu$ moči $n$ z lastnostjo $\mu(c) \ge 1$ za vsak $c \in K$ in multimnožicami moči $n-k$. Zato je

$$|[(K^N)_s]_N|=|\{\mu: K \to \mathbb{N}_0;|\mu|=n,\mu \ge 1\}|=|\bar{\mathcal{K}}(K,n-k)|= {n-1 \choose n-k}.$$

Osredotočimo se sedaj na relacijo $\sim{_K}$. Množico ekvivalenčnih razredov množice $K^N$ glede na to relacijo označimo s $[K^N]_K$. Vzemimo preslikavo $f: N \to K$ in ji priredimo razbitje

$$\{f^{-1}(c) : c \in Im(f)\}$$

množice $N$ na $|Im(f)|$ paroma disjunktnih nepraznih podmnožic. Opazimo, da poljubna ekvivalentna preslikava $g = \lambda \circ f$, $\lambda \in Sym(K)$, porodi isto razbitje množice $N$. Zato lahko za vsak $i \in \{1,...,k\}$ definiramo preslikavo, ki slika iz množice ekvivalenčnih razredov preslikav $f: N \to K$ z $i$-elementno sliko $Im(f)$ v množico razbitij množice $N$ na $i$ nepraznih podmnožic, po pravilu $[f] \mapsto \{f^{-1}(c) : c \in Im(f)\}$. Ni težko preveriti, da je ta preslikava bijektivna. Od tod neposredno sledita formuli za število ekvivalenčnih razredov na množicah $K^N$ in $(K^N)_s$.
Razbitje, ki pripada injektivni preslikavi, je natanko razbitje množice $N$ na enoelementne množice. Zato je ekvivalenčni razred injektivnih funkcij en sam, če seveda kašna injketivna preslikava iz $N$ v $K$ obstaja – sicer je število ekvivalenčnih razredov enako $0$.
Podobno razmislimo tudi situacijo v primeru relacije $\sim{_{N,K}}$. Tu vlogo razbitij množice $N$ nadomestijo razbitja naravnega števila $n$. Podrobnosti izpuščamo.