Matematyka.pl

Udowodnić, że jeśli \(\displaystyle{ A}\) jest zbiorem \(\displaystyle{ k}\)-elementowym zaś \(\displaystyle{ B}\) jest zbiorem \(\displaystyle{ n}\)-elementowym, \(\displaystyle{ k < n}\), to istnieje \(\displaystyle{ n(n-1)...(n-k+1)}\) funkcji różnowartościowych z \(\displaystyle{ A}\) w \(\displaystyle{ B.}\)

Zauważ najpierw, że intuicyjnie jest to zupełnie oczywiste. Chcesz zliczyć wszystkie funkcję różnowartościowe pomiędzy dwoma zbiorami skończonymi. Ponieważ są to zbiory skończone, to wpierw numerujesz ich elementy. Pierwszemu elementowi przypisujesz dowolny element zbioru \(\displaystyle{ B}\). Zbiór \(\displaystyle{ B}\) ma \(\displaystyle{ n}\) elementów, więc można to zrobić na \(\displaystyle{ n}\) sposobów. Drugiemu elementowi zbioru \(\displaystyle{ A}\) przypisujesz drugi element zbioru \(\displaystyle{ B}\), ale tak aby był różny od pierwszego przypisanego elementu, bo funkcje mają być różnowartościowe, więc można to zrobić na \(\displaystyle{ \left( n-1\right)}\) sposobów. Trzeciemu elementowi zbioru \(\displaystyle{ A}\) przypisujesz element różny od przypisanych pierwszych dwóch elementów zbioru \(\displaystyle{ B}\), zatem można to zrobić na \(\displaystyle{ \left( n-2\right)}\) sposobów, itd. ... dla każdego z \(\displaystyle{ k}\) elementów dziedziny \(\displaystyle{ A}\). Ostatecznie, te funkcje różnowartościowe można utworzyć na:
\(\displaystyle{ \underbrace{n \cdot \left( n-1\right) \cdot (n-2)\ldots \left( n-k+1\right)}_{ k \hbox{ składników}}= \frac{n!}{ \left( n-k\right)! },}\)
sposobów.
A ścisły dowód tego faktu przeprowadzasz indukcyjnie, indukcją po zmiennej \(\displaystyle{ k}\).