Размещения и сочетания

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

Используя цифры 7, 4 и 5, мы образовывали различные двузначные числа: 77, 74, 75, 47, 44, 45, 57, 55. В записи этих чисел цифры повторяются.

С теоретико-множественной точки зрения запись любого двузначного числа – это кортеж длины 2. Записывая различные двузначные числа с помощью цифр 7, 4 и 5, мы по сути дела образовывали из данных трех цифр различные кортежи длины 2 с повторяющимися элементами. В комбинаторике такие кортежи называют размещениями с повторениями из трех элементов по два элемента.

Определение. Размещение с повторениями из k элементов по m элементов – это кортеж, составленный из m элементов k-элементного множества.

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

Например, два двузначных числа из перечисленных (а это размещения из трех элементов по два) отличаются друг от друга либо составом элементов (74 и 75), либо порядком их расположения (74 и 47).

Относительно размещений часто возникает вопрос: «Сколько всевозможных размещений по m элементов каждое можно образовать из k элементов данного множества?» Например, сколько всевозможных двузначных чисел можно записать, используя цифры 7, 4 и 5?

Число всевозможных размещений с повторениями из k элементов по m элементов обозначают Ã и подсчитывают по формуле Ã = k .

Выведем эту формулу.

Пусть в множестве Х содержит k элементов. Будем образовывать из них различные кортежи по m элементов. Такие кортежи образуют множество Х х Х х…х Х, содержащее m множителей. По правилу произведения

n (Х х Х х…х Х) = n (Х)•n (Х)•… • n (Х) = k• k•…• k = k .

m множителей m множителей

Следовательно, Ã = k .

Подсчитаем число двузначных чисел, которые можно составить из цифр 7, 4 и 5. Ã = 9.

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

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

Число всевозможных размещений без повторений из k элементов по m элементов обозначают Аⁿ k и подсчитывают по формуле:

А = k• (k-1)•…• (k- m+1).

Выведем эту формулу.

Пусть в множестве Х содержит k элементов. Будем образовывать из них различные размещения без повторений из m элементов. Тогда выбор первого элемента таких кортежей можно осуществить k способами; если первый элемент выбран, то выбор второго элемента можно осуществить k-1 способами (так как после выбора первого элемента кортежа в множестве Х остается k-1 элемент). Третий элемент размещения можно выбрать k-2 способами и т.д., m-й элемент можно выбрать k- (m-1) способами. Но выбор упорядоченного набора из m элементов можно осуществить k• (k-1)•…• (k- m+1). Значит, А = k• (k-1)•…• (k- m+1).

m множителей

Например, число двузначных чисел, записанных с помощью цифр 7, 4 и 5 так, что цифры в записи числа не повторяются, есть число размещений без повторений из трех элементов по два: А = 3• (3-1) = 3•2 = 6.

Задача 1. Сколько всевозможных трехзначных чисел можно записать, используя цифры 7, 4 и 5 так, чтобы цифры в записи числа не повторялись?

Решение. В задаче рассматриваются размещения без повторений из трех элементов по три, и их число можно подсчитать по формуле:

А = 3•(3-1)•(3-2) = 3•2•1= 6.

Эти числа таковы: 745, 754, 475, 457, 547, 574.

Заметим, что в данном случае разные числа получаются в результате перестановки цифр.

Определение. Перестановками из k элементов без повторений называют размещения из k элементов по k элементов.

Число перестановок без повторений из k элементов обозначают Р k и подсчитывают по формуле Р k = k!, где k! = 1•2•3•…• k и k! Читают «k факториал». Считают, что 1! = 1, 0! = 1. Например, 5! = 1•2•3•4•5 = 120; 7! = 1•2•3•4•5•6•7 = 5040.

Из элементов множества Х = {7, 4, 5} можно образовывать не только кортежи различной длины, но и различные подмножества, например двухэлементные. В комбинаторике их называют сочетаниями без повторений из трех элементов по два элемента.

Определение. Сочетание без повторения из k элементов по m элементов – это m-элементное подмножество множества, содержащего k элементов.

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

Число всевозможных сочетаний без повторений из k элементов по m элементов обозначают C . Как находить это число?

Обратимся сначала к примеру. Образуем различные двухэлементные подмножества из элементов множества Х = {7, 4, 5}. Их будет три: {7, 4}{7, 5}{4, 5}. Из элементов каждого такого подмножества можно образовать 2! кортежей длины 2:

(7, 4) (7, 5) (4, 5)

(4, 7) (5, 7) (5, 4)

Все полученные кортежи являются размещениями без повторения из трех элементов по два и их число равно А = 3•2 = 6. Но, с другой стороны, это число равно произведению 2! • С . Значит, А = 2! • С , откуда С = .

Докажем справедливость этой зависимости в общем виде, т.е., что С = .

Пусть в множестве Х содержится k элементов. Образуем из них сочетания без повторений по m элементов. Они будут представлять собой m-элементные подмножества множества Х. Всего таких подмножеств будет С .

Из элементов каждого m-элементного подмножества можно образовать m! Перестановок, т.е. кортежей длины m. В итоге получим m! С кортежей длины m, образованных из k элементов множества Х. Их число равно А . Таким образом,

А = m! С , откуда С = .

Конечно, применение формул облегчает подсчет числа возможных вариантов решений той или иной комбинаторной задачи. Однако чтобы воспользоваться формулой, необходимо определить вид соединений (комбинаций), о которых идет речь в задаче, что бывает сделать не очень просто.

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

1) Сколько всего двузначных чисел? (Используются размещения с повторениями)

2) Сколько всего двузначных чисел, в записи которых цифры не повторяются? (Используется размещения без повторений)

3) На прямой взяли десять точек. Сколько всего получилось отрезков, концами которых являются эти точки? (Используются сочетания без повторений).

Основные выводы

Изучив материал этого параграфа, установили, что решение комбинаторных задач предполагает усвоение следующих понятий: способ выбора объекта; дерево возможных вариантов; размещение из m элементов по k элементов (с повторениями и без повторений); сочетание из m элементов по k элементов (без повторений).

В основе решения комбинаторных задач лежат различные правила: правило суммы, правило произведения, правила подсчета указанных комбинаций (см. выше).