5. Число отображений k-множества в m-множество.

Выведенная выше формула для числа кортежей позволяет решать различные задачи комбинаторики. Вспомним, что кортеж длины из элементов -множества это отображение множества Поэтому число таких кортежей равно числу отображений множества в -множество Очевидно, таким же будет число отображений любого -множества в любое -множество.

Итак, мы доказали, что число отображений -множества X в -множество равно

Например, если то имеем отображений. Если же то имеем отображений.

Рис. 3

Полученный результат можно сформулировать и иным образом. Если считать элементы множества X «предметами», а элементы множества -«ящиками», то при каждом отображении множества X во множество У происходит распределение предметов по ящикам (некоторые ящики могут при этом оказаться пустыми, поскольку может оказаться, что в элемент не отображается ни один элемент множества X). Например, если множество X состоит из элементов а множество из чисел 1,

2, 3, 4 и отображение задается схемой, показанной на рисунке 3, то в первый ящик попадают элементы а, с и во второй ящик — элементы в четвертый ящик — элементы а третий ящик остается пустым. Поскольку число отображений -множества X в -множество равно то и число распределений различных предметов по различным ящикам (некоторые ящики могут оказаться пустыми) равно .

Этот результат позволяет найти число подмножеств -множества X. В самом деле, возьмем два числа 0 и 1 (или, если угодно, два ящика). Каждому подмножеству А множества X соответствует отображение множества X во множество при котором элементы из А отображаются в 1, а остальные элементы — в 0. Таким образом, существует взаимно однозначное соответствие между подмножествами множества X и отображениями этого множества в -множество Но число этих отображений равно где число элементов множества Значит, и число подмножеств -множества X равно

В качестве примера рассмотрим -множество Оно должно иметь подмножеств. Ими являются

Утверждение о числе подмножеств -множества можно доказать, используя метод математической индукции. При оно истинно, так как а -множество имеет два подмножества — само множество и пустое множество 0. Предположим теперь, что утверждение справедливо при т. е. что -множество имеет подмножеств. Присоединив ко множеству элемент получим -множество Любое из подмножеств множества У либо не содержит нового элемента либо содержит его. В первом случае оно является подмножеством -множества Число таких подмножеств равно 2. Во втором случае, отбрасывая элемент снова получаем подмножество множества Итак, число подмножеств второго вида равно числу подмножеств первого вида, т. е. равно 2. Но тогда общее число подмножеств множества У равно

Итак, мы доказали, что наше утверждение истинно при а из его истинности при вывели, что оно истинно и при Значит, оно верно при всех значениях