Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ЗАДАНИЕ 3 Пересчет и перечисление сочетаний и перестановок

Цель задания: изучение формул пересчета и алгоритмов перечисления таких простейших комбинаторных объектов, как сочетания и перестановки. Из большого числа известных алгоритмов взяты для рассмотрения только те, которые генерируют комбинаторные объекты в лексикографическом порядке.

Определение комбинаторных объектов

Пусть X—ь хя} - некоторое конечное множество. Размещением элементов из X по к (или из п по к) называется упорядоченное подмножество из к элементов, принадлежащих Х(1 <к<п). Число А(п, к) различных размещений из п по к при 1 < к < п равно

Считают, что А(0, 0) = А(п, 0) = 1 и А(п, к) = 0, если к > п.

Перестановка из п элементов - частный случай размещения при к = п. Поэтому число Р(п) различных перестановок из п элементов равно

Полагают, что Р(0) = 0! = 1.

Сочетанием элементов из X по к (или из п по к) называется неупорядоченное подмножество из к элементов, принадлежащих X. Сочетание отличается от размещения тем, что в нем не учитывается порядок элементов. Поэтому каждому сочетанию соответствует к размещений. Отсюда следует формула для числа С{п, к) сочетаний из п элементов по А: (1 <к<п):

Из этой формулы вытекает справедливость равенств:

Считают, что С(п, к) = 0 при к > п.

Величины А(п, к), Р(п), Р(п, к) называются комбинаторными числами. Формулы их вычисления позволяют пересчитать соответствующие комбинаторные объекты.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>