Udowodnij że liczba wszystkich injekcji ze zbioru m elementowego w zbiór n elementowy, gdzie \(m \le n\) jest \(\frac{n!}{(n-m)!}\). Injekcją nazywamy funkcję różnowartościową, to znaczy taką, że dla każdych różnych argumentów \(x_1,x_2 \in D_f, x1 \neq x2\) przyjmuje różne wartości \(f(x_1) \neq f(x_2)\)
Podpowiedź: Ustaw wszystkie argumenty funkcji z dzidziny w pewnej kolejności i zastanów się po kolei na ile sposobów mozna im przydzielać kolejne wartości
Weźmy \(x_1\). Można mu przyporządkować każda z m wartości. Jeśli już przyporządkujemy argumentowi jakąś wartość, to dla każdego takiego przyporządkowania dla argumentu \(x_2\) takich możliwości jest już tylko (n-1). Jeśli przyporządkujemy argumentom \(x_1\ i\ x_2\) konkretne wartości, to dla \(x_3\) mamy takich możliwości (n-2) i tak dalej. Dla argumentu \(x_m\) zostaje takich możliwości (n-(m-1))=(n-m+1) (bo "wykorzystano" już (m-1) wartości spośród n wartości). Czyli takich przyporządkowań różnowartościowych, gdzie każdemu argumentowi z m-elementowego zbioru wartości ze zbioru n-elementowego (\(m \le n\))jest: