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

Соединения в комбинаторике

Общие правила комбинаторики

Комбинаторные задачи бывают самых разных видов. Но большинство задач решается с помощью двух основных правил – правила суммы и правила произведения.

Правило суммы: если некоторый объект А можно выбрать способами, а другой объект В можно выбратьспособами, то выбор «либо А, либо В» можно осуществитьспособами.

При использовании правила суммы в последней формулировке надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В (или, как мы говорим, чтобы ни одна комбинация не попала сразу в два класса). Если такие совпадения есть, правило суммы утрачивает силу, и мы получим лишь способов выбора, где - число совпадений.

Правило произведения: если объект А можно выбрать способами и если после каждого такого выбора объект В можно выбратьспособами, то выбор пары (А,В) в указанном порядке можно осуществитьспособами.

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

Предметы, из которых составляются соединения, называются элементами. Элементы обозначаются буквами.

Соединения могут быть трёх видов: размещения, перестановки, сочетания без повторений и с повторениями.

Рассмотрим каждый из видов в отдельности.

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

Другими словами, если две выборки, отличающиеся только порядком записи символов, считают различными, то говорят о размещении из m элементов по k.

Пусть дано элементов:. Сначала составим из них все размещения по 1.

Их, очевидно, будет. Значит,.

Теперь составим все размещения по 2. Для этого к каждому из ранее составленных размещений по 1 приставим последовательно все оставшиеся элементов по 1. Так, к элементу приставим последовательно оставшиеся элементы:; к элементу приставим последовательно оставшиеся элементы: и т.д. Получим следующие размещения по 2:

m строк

Так как всех элементов, то из каждого размещения по одному элементу мы получим размещений по 2, а всего их будет. Значит,.

Чтобы составить размещения по 3, берём каждое из составленных сейчас размещений по 2 и приставим к нему последовательно по одному все оставшихся элементов. Тогда получим следующие размещения по 3:

m(m-1) строк

Так как число всех размещений по 2 равно m(m-1) и из каждого получается m-2 размещения по 3, то всех таких размещений окажется: m(m-1)(m-2). Таким образом. Подобно этому получим:, и вообще:

Числитель и знаменатель умножим на произведение

.

Дата добавления: 2014-01-04