Спирина, М.С. Дискретная математика

Рис. 1.10. Классификация множеств в зависимости от их мощности и характера соответствия натуральному ряду чисел этих определений данному нами, но в рамках некоторых допуще­ ний (подробнее о подобных доказательствах см. в гл. 5). Множество А можно отобразить во множество В различными способами. Найдем, сколько существует различных отображений А в В. Пусть А и В конечны, причем \А\ = п, а |Z?| = к. Каждый из п аргументов может независимо отобразиться в любой из к элемен­ тов В. Поскольку характер множества В не влияет на число функ­ ций, возьмем для удобства записи символов множество В = {1, 2, ..., к). Зададим функцию g таким образом, что на первом месте стоит #(Я|), на п-м g(an). Таким образом, функция может ме­ няться по п «направлениям» (последние два — в плоскости листа) и принимать любые из к значений. Поэтому всего таких записей может быть к к ■... к = к". Это и есть искомое число функций. П ( 1 , 1 , .... 1 , 1 , 1 ) ( 1 , 1 , .... 1 , 2 , 1 ) . ( 1 , 1 , 1 , к, 1 ) ( 1 , 1 , .... 1 , 1 , 2 ) ( 1 , 1 , 1 , 2 , 2 ) ( 1 , 1 , 1 , 2 , 2 ) ( 1 , 1 , 1 , 1 , к) ( 1 , 1 , 1 , 2 , к) ’’ ( 1 , 1 , 2 , к) 30