Дипломная работа

2.4 Комбинаторика

I-ое рекуррентное соотношение:

II-ое рекуррентное соотношение:

2.4.1 Перестановки с повторениями.


В
B=
элементов
если .

Т.е. множество выбираемых элементов ( элементов), которое разбито на классов , причем i-ый класс содержит ni элементов.

Перестановки из элементов данной спецификации называют перестановками с повторениями.
Оценим число перестановок с повторениями

Если переставлять буквы слова «мама», то поменяв местами буквы «м» и «а» мы ничего не изменим.

мама

Для вычисления заменим в множестве B элементы класса на элементы, которые различны между собой между всеми элементами множества B. Тогда число возрастает в раз (по правилу умножения)

Проделаем эту процедуру для


,

т. к. после замены все элементы в B стали различные и их можно переставить способами.

2.4.2 Перестановки с неограниченными повторениями

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



r раз

Пусть имеем n различных элементов. Чем сочетания отличаются от перестановок? Перестановки – упорядоченная выборка.

Сочетания – неупорядоченная выборка.





r!=

Неупорядоченную г-выборку можно упорядочить r! способами.

! Договариваемся

Комбинаторного смысла это не несет.

Рассмотрим