Главная > Математика > Дискретная математика. Алгоритмы и программы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.6. Сочетания

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

элементов. Общее число сочетаний обозначают через С или

Определим это число. Составим все сочетания из по k. Затем переставим в каждом сочетании элементы всеми возможными способами. Теперь мы получили расстановки, отличающиеся либо составом, либо порядком, т.е. это все размещения без повторений из по k. Их число равно Учитывая, что каждое сочетание дает размещений, то по правилу произведения можно записать Тогда или

(см. скан)

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

Решение. Прямоугольник однозначно определяется положением его сторон. Горизонтальные стороны могут занимать любое из положения. Тогда число способов их выбора равно Вертикальные стороны можно выбрать способами. По правилу прямого произведения заключаем, что количество прямоугольников равно

<< Предыдущий параграф Следующий параграф >>
Оглавление