Формирование умений и навыков в решении комбинаторных задач

Изучить данную тему самостоятельно, переписать примеры в тетрадь и выполнить самостоятельную работу.

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

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

Множество будем записывать, располагая его элементы в фигурных скобка { a, b, c, …, e, f }.

Во множестве порядок элементов роли не играет, так { a, b } = { b, a }.

Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается символом ø.

Если каждый элемент множества А является элементом множества В, то говорят, что множество А является подмножеством множества В

Множество { a, b } является подмножеством множества { a, b, c, …, e, f }.

Задача: Перечислите возможные варианты подмножества множества { 3, 4, 5, 7, 9 }.

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

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

Комбинаторика – раздел математики, который занят поисками ответов на вопросы: сколько всего есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать наилучшую. Слово «комбинаторика» происходит от латинского слова «combinare», что в переводе на русский означает – «сочетать», «соединять». Термин "комбинаторика" был введён знаменитым Готфридом Вильгельмом Лейбницем, - всемирно известным немецким учёным.

Комбинаторика является важным разделом математики, который исследует закономерности расположения, упорядочения, выбора и распределения элементов с фиксированного множества.

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

ПРАВИЛО СУММИРОВАНИЯ

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

Пример №1

Из города А в город В можно добраться 12 поездами, 3 самолетами, 23 автобусами. Сколькими способами можно добраться из города А в город В?

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

N=12+13+23=38

Пример № 2

В ящике имеется n разноцветных шариков. Произвольным образом вынимаем один шарик. Сколькими способами это можно сделать?

Решение. Конечно, n способами.

Теперь эти n шариков распределены по двум ящикам: В первом m шариков, во втором k. Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами это можно сделать?

Решение. Из первого ящика шарик можно вытянуть m различными способами, из второго k различными способами, всего N = m + k способами.

ПРАВИЛО ПРОИЗВЕДЕНИЯ

Пусть две выполняемые одно за другим действия могут быть осуществлены в соответствии и способами. Тогда обе они могут быть выполнены способами.

Пример № 3

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

Решение. Первое место займет одна из 8 команд, второе - одна из 7, третье - одна из 6, так как каждая из них не может претендовать одновременно на два призовых места. Поэтому таких способов будет ровно

N=8 7 6 =336

Пример № 4

Сколько можно записать двузначных чисел в десятичной системе счисления?

Решение. Поскольку число двузначное, то число десятков (m) может принимать одно из девяти значений: 1,2,3,4,5,6,7,8,9. Число единиц (k) может принимать те же значения и может, кроме того быть равным нулю. Отсюда следует, что m = 9, а k = 10. Всего получим двузначных чисел

N = m · k = 9·10 =90.

Пример № 5

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

Решение. По правилу умножения двух девушек можно выбрать 14 ·13 = 182 способами, а двух юношей 6·5 = 30 способами. Следует выбрать двух студентов одного пола: двух студентов или студенток. Согласно правилу сложения таких способов выбора будет N =182 + 30 = 212.

Типы соединений

Множества элементов называются соединениями.

Различают три типа соединений:

· перестановки из n элементов;

· размещения из n элементов по m;

· сочетания из n элементов по m (m < n).

Перестановки. Число перестановок

На практике часто возникают задачи, связанные с установлением порядка во множестве. Например, число мест равно количеству людей, на которых мы должны разместить их. Такая ситуация встречается часто – рассадить n человек на n мест, или приписать каждому человеку номер. Первый человек может выбрать любое из n мест, второй человек выбирает из (n - 1) оставшихся мест, третий человек может выбрать из уже (n - 2) мест, …, предпоследний человек выбирает из 2 мест, последний человек получает последнее место. Мы получаем произведение всех целых чисел от n до 1.

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

n! = 1·2·3…(n – 2) · (n – 1) · n.

Установленный в конечном множестве порядок называют перестановкой его элементов.

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

Иными словами, это такое множество, для которого указано, какой элемент находится на первом месте, какой – на втором, какой- на третьем, …, какой – на n-м месте.

Перестановки можно образовывать из элементов любого конечного множества. Число перестановок из n элементов обозначают Р_n. Возьмем одноэлементное множество { a }. Ясно, что один элемент можно упорядочить единственным образом, следовательно, Р₁ = 1.

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

Возьмем двух элементное множество { a, b }. В нем можно установить два порядка: { a, b } или { b, a }. Следовательно, число перестановок из двух элементов Р₂ = 2.

Три буквы во множестве { a, b, c } можно расположить, по порядку шестью способами: { a, b, c }{ a, c, b }{ b, a, c }{ b, c, a }{ c, b, a }{ c, a, b }.

Следовательно, общее число способов упорядочения трех элементов множества

Р₃ = 3 · Р₂ = 3 · 2 · 1 = 6.

Р_n = n · (n - 1) · (n – 2) · … · 2 · 1 = n!

Определение: Пусть n - натуральное число. Через n! (читается "эн факториал") обозначается число, равное произведению всех натуральных чисел 1 от до n:

n! = 1 · 2 · 3 ·... · n.

В случае, если n = 0, по определению полагается: 0! = 1.

Пример № 6

Найдем значения следующих выражений:
1! = 1
2! = 1 · 2 = 2
3! = 1 · 2 · 3 = 6

Пример № 7

Чему равно а) Р ₅; б) Р _3.

Решение.

Р_n = n! = n · (n - 1) · (n – 2) · … · 2 · 1

Р ₅=5! = 5 · 4 · 3 · 2 ·1 = 120

Р ₃=3! = 1 · 2 · 3 = 6

Пример № 8

Упростите

а) 7! · 8 = 8!

б) 12! · 13 ·14 = 14!

в) κ! · (κ + 1) = (κ + 1)!

Пример № 9

Сколькими способами можно расставить 8 участниц финального забега на восьми беговых дорожках?

Решение.

n =8

Р ₈=8! = 8·7·6·5 · 4 · 3 · 2 ·1 =40320

Размещения.

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

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

Число размещений из m элементов по n обозначают (от французского «arrangement» - «размещение») и вычисляют по формуле:

Пример № 9

Учащиеся 11-го класса изучают 9 учебных предметов. В расписании учебных занятий на один день можно поставить 4 различных предмета. Сколько существует различных способов составления расписания на один день?

Решение.

Имеем 9-элементное множество, элементы которого учебные предметы. При составлении расписания мы будем выбирать 4-элементное подмножество (урока) и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре, то есть A ₉⁴:

Пример № 10

Сколькими способами из класса, где учатся 24 ученика, можно выбрать старосту и помощника старосты?

Решение.

Имеем 24-элементное множество, элементы которого ученики класса. При выборах старосты и помощника старосты мы будем выбирать 2-элементное подмножество (ученика) и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре(m=24, n=2), то есть A ₂₄²:

Сочетания.

Сочетаниями из m элементов по n элементов (n ≤ m) называются такие соединения, каждое из которых содержит n элементов, взятых из m данных элементов, и которые отличаются друг от друга по крайней мере одним элементом.

Определение. Сочетанием без повторений из n элементов по m -называется любое m элементное подмножество n -элементного множества

Число сочетаний из n элементов по m обозначают (от французского «combination» - «сочетание») и вычисляют по формуле:

Пример № 11

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

Решение.

n =24, m =2

Формирование умений и навыков в решении комбинаторных задач.

При решении комбинаторных задач и выборе типа соединений важно ответить на следующие вопросы:

ü Учитывается ли порядок следования элементов в соединении?

ü Все ли элементы входят в соединение?

Учитывается ли порядок следования элементов в соединении?

НЕТ

ДА

Все ли элементы входят в соединение?

ДА

НЕТ

СОЧЕТАНИЯ

ПЕРЕСТАНОВКИ Р_n = n! = n · (n - 1) · (n – 2) · … · 2 · 1

РАЗМЕЩЕНИЯ

Определить к какому типу относится соединений относится задача.

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

ü Учитывается ли порядок следования элементов в соединении? (да)

ü Все ли элементы входят в соединение? (да)

Вывод: перестановка

2. В 9«Б» классе 12 учащихся. Сколькими способами можно сформировать команду из 4 человек для участия в математической олимпиаде?

ü Учитывается ли порядок следования элементов в соединении? (нет)

ü Все ли элементы входят в соединение? (на этот вопрос ответ не нужен)

Вывод: сочетания

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

ü Учитывается ли порядок следования элементов в соединении? (да)

ü Все ли элементы входят в соединение? (нет)

Вывод: размещение

Решить задачи:

1. У нас имеется 5 книг. Известно, что у нас всего одна полка, и на ней вмещается лишь 3 книги. Сколькими способами можно расставить на полке 3 книги?

Решение.

ü Учитывается ли порядок следования элементов в соединении? (да)

ü Все ли элементы входят в соединение? (нет)

Вывод: размещение

n =5, m =3