§6. Комбинаторные задачи и их решение

Лекция 13.Комбинаторные задачи и их решение

План:

1. Правила суммы и произведения

2. Размещения, перестановки с повторениями и без повторений. Сочетания без повторений. Число подмножеств конечного множества. Бином Ньютона.

3. Выводы

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

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

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

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

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

Комбинаторные задачи в начальном курсе математики решаются, как правило, методом перебора. Для облегчения этого процесса нередко используются таблицы и графы. В связи с этим учителю начальных классов необходимы определенные умения и навыки решения комбинаторных задач. Прежде всего, он должен, решая несложные комбинаторные задачи, уметь грамотно осуществлять перебор возможных вариантов и при этом быть уверенным в том, что перебор осуществлен правильно. Учителю надо знать общие правила комбинаторики (в частности, правила суммы и произведения), некоторые виды комбинаций, число которых может быть подсчитано с помощью формул. Поэтому предложенный в данном пособии путь освоения способов решения комбинаторных задач состоит из нескольких этапов: сначала они решаются методом перебора и для записи возможных вариантов используются различные способы; затем появляются правила суммы и произведения и процесс решения комбинаторных задач несколько формализуется, и, наконец, рассматриваются некоторые виды комбинаций, а их число подсчитывается по формулам.

35. Правила суммы и произведения

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

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

Задача 1. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

Решение. По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсина», то его, согласно правилу суммы, можно осуществить 5 + 4 = 9 способами.

Правило нахождения числа элементов декартова произведения двух множеств называют в комбинаторике правилом произведенияи формулируют в таком виде:

Если объект а можно выбрать m способами, а объект b – k способами, то пару (а, b) можно выбрать m • k способами.

Правило суммы и произведения, сформулированные для двух объектов, можно обобщить и на случай tобъектов.

Задача 2. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать пару плодов, состоящую из яблока и апельсина?

Решение. По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе пары (яблоко, апельсина), то ее, согласно правилу произведения, можно осуществить 5 •4 = 20 способами.

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

Решение. Чтобы записать двузначное число, надо выбрать цифру десятков и цифру единиц. Согласно условию на месте десятков в записи числа может быть любая из цифр 7, 4 и 5. Другим словом, выбрать цифру десятков можно тремя способами. После того как цифра десятков определена, для выбора цифры единиц остаются две возможности, поскольку цифры в записи числа не должны повторяться. Так как любое двузначное число – это упорядоченная пара, состоящая из цифры десятков и цифры единиц, то ее выбор, согласно правилу произведения, можно осуществить 3 • 2 = 6 способами.

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

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

Задача 5. Сколько всего четырехзначных чисел можно составить из цифр 0 и 3?

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

Итак, цифру тысяч можно выбрать одним способом, цифру сотен – двумя, цифру десятков – двумя, цифру единиц – двумя. Чтобы узнать, сколько всего четырехзначных чисел можно составить из цифр 0 и 3, согласно правилу произведения, способы выбора каждой цифры надо перемножить: 1 • 2 • 2 • 2 = 8.

Таким образом, имеем 8 четырехзначных чисел.

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

Решение. Так как запись числа не может начинаться с нуля, то цифру сотен можно выбрать пятью способами; выбор цифры десятков можно осуществить также пятью способами, поскольку цифры в записи числа не должны повторяться, а одна из шести данных цифр будет уже использоваться для записи сотен; после выбора двух цифр (для записи сотен и десятков) выбрать цифру единиц из данных шести можно четырьмя способами. Отсюда, по правилу произведения, получаем, что всего трехзначных чисел (из данных шести цифр) можно образовать 100; 5 • 5 • 4 = 100.

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

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

Используя цифры 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. На прямой взяли десять точек. Сколько всего получилось отрезков, концами которых являются эти точки? (Используются сочетания без повторений).

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

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

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

Лекция 14.Алгоритмы и их свойства

План:

1. Понятие алгоритма

2. Виды алгоритмов

3. Приемы построения алгоритмов

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