Размещения с повторениями

Упорядоченная выборка, в которой элементы могут повторяться, называется размещением с повторениями. Число всех размещений с

повторениями из n пo r будем обозначать По определению

ТЕОРЕМА.

Доказательство проведем методом полной математической индукции по переменной r. Очевидно, что Предположим, что для справедливо равенство Пусть С помощью правила умножения можно доказать равенство

(1)

Отсюда ■

ТЕОРЕМА. Число всех подмножеств конечного множества из n элементов равно

Доказательство. Выберем подмножество. Если элемент принадлежит подмножеству, то кодируем эту ситуацию символом 1, а если не принадлежит, то символом 0. Элементы исходного множества пронумеруем. Тогда каждому подмножеству ставится во взаимнооднозначное соответствие размещение с повторениями из двух элементов 0 и 1 по n. Таких размещений поэтому и подмножеств ■