Пусть имеется набор из n объектов k типов, причем k < n. Так как k < n, то некоторые объекты в наборе должны повторяться. Подсчитаем количество возможных перестановок из этих объектов, если число объектов 1-го типа равно n1, количество объектов 2-го типа равно n2, ... , количество объектов k-го типа равно nk.
Если все объекты были различны, то общее число перестановок было бы равно n!. На самом деле число перестановок будет меньше, так как, поменяв местами объекты одного типа, мы не меняем перестановку. Выберем какую-либо конкретную перестановку и будем в ней менять местами между собой объекты одного конкретного типа. Если меняются местами объект 1-го типа, то число вариантов обмена будет равно n1!, если меняются местами объекты 2-го типа, то число вариантов обмена равно n2!, ..., если меняются объекты k-го типа, то число обменов равно nk!. Так как при каждом таком обмене перестановка не меняется, то общее число перестановок с повторениями описанного типа будет равно:
3.3.5. Определение числа k-сочетаний из n элементов
В сочетаниях, в отличие от размещений, не учитывается порядок следования
элементов. Поэтому, если взять все размещения, составленные из одного и того же
фиксированного набора из k элементов, и отказаться от учета порядка следования
элементов, то мы получим из них одно и то же сочетание этих элементов. Так как
такие размещения представляют собой перестановки из k элементов и их число
равно k!, то каждому k-сочетанию соответствует k! различных размещений из тех
же элементов. Таким образом, число k-сочетаний из n элементов в k! раз меньше
числа k-размещений из n элементов. Число k-сочетаний из n элементов принято
обозначать 
.
Сопоставляя (3.6) и (3.5), нетрудно видеть, что 
.
3.3.6. Определение числа k-сочетаний из элементов n типов с повторениями
Имеются элементы n типов. Количество элементов каждого типа не ограничено. Из этих элементов необходимо выбрать k элементов, причем элементы могут повторяться, а порядок их следования в наборе не имеет значения.
Для
определения числа таких сочетаний (его принято обозначать 
) поставим в соответствие каждому такому
сочетанию шифр, состоящий из нулей и единиц. Этот
шифр будем составлять следующим
образом: сначала
напишем столько единиц, сколько в сочетании имеется элементов 1-го типа, затем
напишем 0. После этого нуля напишем столько единиц, сколько в сочетании имеется
элементов 2-го типа, после чего опять напишем 0.
Если элементы какого-либо типа
в данном сочетании
отсутствуют, то единицы записывать не будем, но
0 поставим. Таким образом, в шифре будет k единиц и n –
1 ноль.
Нетрудно видеть, что каждое сочетание таким способом шифруется однозначно. С другой стороны, если мы имеем произвольный набор из k единиц и n – 1 нуля, то по нему можно однозначно составить k-сочетание из элементов n типов. То есть между описанными шифрами и сочетаниями с повторениями существует взаимно однозначное соответствие и число k-сочетаний с повторениями из элементов n типов равно количеству шифров. Но описанный шифр с точки зрения комбинаторики представляет собой перестановку с повторениями из элементов двух типов (нулей и единиц), содержащую k+n–1 элемент.
Таким образом,
Сравнивая эту формулу с формулой для числа сочетаний без повторений, получаем:
ЛИТЕРАТУРА
1. Коршунов Ю.М. Математические основы кибернетики. -М.: Энергия, 1972, 1980, 1987.
2. Основы кибернетики. Математические основы кибернетики/под ред. К.А. Пупкова. -М.: Высш. школа, 1974.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. -М.: Энергия, 1980, 1988.
4. Виленкин Н.Я. Популярная комбинаторика. -М.: Наука, 1975.
5. Кофман А. Введение в прикладную комбинаторику. -М.: Наука, 1975.
6. Кристофидес Н. Теория графов. -М.: Мир, 1978.
7. Ренин С.В. Сборник задач и упражнений по основам теории систем. - Новосибирск: НЭТИ, 1985.
8. Ренин С.В. Спецглавы математики. Сборник задач и упражнений. - Новосибирск: Изд-во НГТУ, 2000.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.