Схема выбора, приводящая к размещениям и перестановкам

КОМБИНАТОРНЫЕ ЗАДАЧИ

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

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

После того, как выбор осуществлен тем или иным способом, отобранные элементы могут быть либо упорядочены ( т.е. выложены в последовательную цепочку ), либо нет. Это зависит от условий конкретной задачи, которую мы решаем.

Таким образом, мы будем рассматривать различные задачи по выбору наудачу определенного числа элементов из заданного множества, т.е. определенных комбинаций с использованием соответствующих схем выбора. Изучение этих схем и составит основное содержание данной главы. Но сначала мы рассмотрим два общих правила, с помощью которых решаются задачи комбинаторики – правило суммы и правило произведения.

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

Начнем рассмотрение общих правил комбинаторики с примера.

Допустим, что в магазине имеются 5 различных видов коробок конфет и 4 различных вида коробок печенья. Поставим два вопроса: «Сколькими способами можно выбрать в подарок коробку конфет или коробку печенья? Сколькими способами можно составить набор, состоящий из коробки конфет и коробки печенья?»

На первый вопрос ответ очевиден. Коробку конфет можно выбрать пятью способами, коробку печенья – четырьмя способами. Следовательно, конфеты или печенье можно выбрать 5+4=9 способами.

Если мы составляем набор, то к каждой из пяти различных коробок конфет можно подобрать печенье четырьмя способами: к коробке конфет первого вида – 4 способа выбора печенья, к коробке конфет второго вида – опять 4 способа выбора и т.д. Всего 5·4=20 различных способов.

Этот простейший пример показывает применение правил суммы и произведения. Как мы видим, союзу «или» в постановке задачи соответствует сложение, союзу «и» - умножение. Сформулируем теперь правила в общем виде.

Правило суммы. Если некоторый объект А можно выбрать m способами, а объект В – k способами ( не таким, как А ), то объект «А или В» можно выбрать (m+k) способами.

Правило произведения. Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать ( независимо от выбора А ) k способами, то объект «А и В» можно выбрать (m·k) способами.

Теперь перейдем к рассмотрению различных схем выбора, которые приводят к построению различных комбинаций.

КОМБИНАТОРНЫЕ ЗАДАЧИ

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

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

После того, как выбор осуществлен тем или иным способом, отобранные элементы могут быть либо упорядочены ( т.е. выложены в последовательную цепочку ), либо нет. Это зависит от условий конкретной задачи, которую мы решаем.

Таким образом, мы будем рассматривать различные задачи по выбору наудачу определенного числа элементов из заданного множества, т.е. определенных комбинаций с использованием соответствующих схем выбора. Изучение этих схем и составит основное содержание данной главы. Но сначала мы рассмотрим два общих правила, с помощью которых решаются задачи комбинаторики – правило суммы и правило произведения.

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

Начнем рассмотрение общих правил комбинаторики с примера.

Допустим, что в магазине имеются 5 различных видов коробок конфет и 4 различных вида коробок печенья. Поставим два вопроса: «Сколькими способами можно выбрать в подарок коробку конфет или коробку печенья? Сколькими способами можно составить набор, состоящий из коробки конфет и коробки печенья?»

На первый вопрос ответ очевиден. Коробку конфет можно выбрать пятью способами, коробку печенья – четырьмя способами. Следовательно, конфеты или печенье можно выбрать 5+4=9 способами.

Если мы составляем набор, то к каждой из пяти различных коробок конфет можно подобрать печенье четырьмя способами: к коробке конфет первого вида – 4 способа выбора печенья, к коробке конфет второго вида – опять 4 способа выбора и т.д. Всего 5·4=20 различных способов.

Этот простейший пример показывает применение правил суммы и произведения. Как мы видим, союзу «или» в постановке задачи соответствует сложение, союзу «и» - умножение. Сформулируем теперь правила в общем виде.

Правило суммы. Если некоторый объект А можно выбрать m способами, а объект В – k способами ( не таким, как А ), то объект «А или В» можно выбрать (m+k) способами.

Правило произведения. Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать ( независимо от выбора А ) k способами, то объект «А и В» можно выбрать (m·k) способами.

Теперь перейдем к рассмотрению различных схем выбора, которые приводят к построению различных комбинаций.

Схема выбора, приводящая к размещениям и перестановкам

Представим себе, что нам нужно из множества, состоящего из трех элементов a, b и c составить различные комбинации по два элемента, которые могут отличаться не только набором элементов, но и их порядком. Понятно, что получатся следующие комбинации: ab, ba, ac, ca, bc, cb.

Пусть теперь множество E = {a₁ , a₂,…, a_n} состоит из n различных элементов. Из этого множества будем выбирать k элементов без повторения (или без возвращения), т.е. мы будем выбирать последовательно по одному элементу, причем каждый отобранный элемент не может быть выбран снова. Пусть нам при этом важен порядок выбора. Тогда различными результатами данного опыта будут упорядоченные m – элементные подмножества множества l, отличающиеся либо набором элементов, либо порядком их следования. Эти упорядоченные подмножества называются размещениями из n элементов по k, а их общее число обозначается .

Рассмотрим в качестве примера следующую задачу.

Допустим, в соревнованиях по футболу принимает участие 10 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?

В данной задаче мы имеем дело с выборками-размещениями из 10 элементов по 3. Действительно, из 10 команд нужно выбрать 3 , причем команды не должны повторяться, и важен порядок выбора (любой команде не безразлично, займет она первое, второе или третье место).

Подсчитаем . Очевидно, что на первое место можно поставить команду 10 способами, на второе – уже 9 способами ( из 9 оставшихся команд ), на третье – 8 способами. По правилу произведения общее число способов: = 10·9·8 = 720.

Например, пусть рассматривается множество, состоящее из 8 первых букв русского алфавита. Опыт заключается в выборе без повторения четырех букв и записи слова в порядке поступления букв. Сколько четырехбуквенных слов может быть получено? Сколько таких слов начинается с буква а?

Число четырехбуквенных слов в данном опыте вычисляется по формуле: А⁴₈ = 8·7·6·5 = 1680.

Если на первом месте стоит буква а, то количество слов равно числу способов размещения на три оставшихся места по одному символу из семи (символ а исключен из рассмотрения, поскольку его место уже определено). Таким образом, число слов, начинающихся с буквы а, равно = 7·6·5 = 210.

Если мы имеем дело с выборками-размещениями в частном случае, когда m = n, то опыт состоит в произвольном упорядочивании всего множества Е, а – число размещений, которые отличаются друг от друга только порядком расположения элементов Е. Такие размещения называются перестановками. Их общее число обозначается P_n .

P_n = n!

Представим себе следующую ситуацию: три студента А, В и С победили на олимпиаде. Сколько существует различных способов вручения им дипломов первой, второй и третьей степени?

В задаче требуется найти число способов упорядочивания множества {A, B, C}, т.е. число перестановок. Имеем Р₃ = 3·2·1 = 6. Эти способы легко выписать АВС, АСВ, ВАС, ВСА, САВ, СВА.

Замечание 1. Число n может принимать не только натуральные значения, оно может быть равно нулю. Естественно считают, что пустое множество упорядочивается только одним способом, по определению полагать 0!=1.