🗊Презентация Элементы комбинаторики

…Человек, не знающий математики, не способен ни к каким другим наукам. Более того, он даже не способен оценить уровень своего невежества, а потому не ищет от него лекарства. Роджер Бэкон (1214–1292)

Правило суммы Правило суммы Если элемент a из конечного множества можно выбрать m способами, а элемент b – n способами, причем любой выбор элемента a не совпадает с каким-нибудь способом выбора элемента b, то выбор «a или b» можно осуществить m + n способами. Правило суммы можно распространить на выбор любого конечного числа элементов.

Пример: Сколько различных «слов» (последовательностей букв) не менее чем из пяти различных букв, можно образовать из слова «рисунок»? Пример: Сколько различных «слов» (последовательностей букв) не менее чем из пяти различных букв, можно образовать из слова «рисунок»? Решение: «Рисунок» состоит из семи различных букв. Применяем правило произведения: N1 = 7 × 6 × 5 × 4 × 3 = 2520 «слов» из пяти букв (выбираемых из букв слова «рисунок»), N2 = 7 × 6 × 5 × 4 × 3 × 2 = 5040 «слов» из шести, N3 = 7 × 6 × 5 × 4× 3 × 2 × 1 = 5040 «слов» из семи. Тогда N = N1 + N2 +N3 = 2520 + 5040 + 5040 = 12 600 «слов», состоящих не менее чем из пяти букв слова «рисунок».

Пример. В чемпионате страны по шахматам принимает участие 16 человек. Сколькими способами могут быть распределены золотая и серебряная медали? Пример. В чемпионате страны по шахматам принимает участие 16 человек. Сколькими способами могут быть распределены золотая и серебряная медали? Решение. Золотую медаль может получить один из 16 шахматистов. После того, как определен победитель, серебряную медаль может иметь один из 15-ти человек. Общее количество способов, которыми могут быть распределены золотая и серебряная медали 16 ⋅15 = 240.

Обозначим символом: n! («эн факториал») – число, равное произведению натуральных чисел от 1 до n. Обозначим символом: n! («эн факториал») – число, равное произведению натуральных чисел от 1 до n. 1! = 1; 2! = 1 × 2 = 2; 3! = 1 × 2 × 3 = 6; 4! = 1 × 2 × 3 × 4 = 24; По определению 0! = 1. Рассмотрим некоторое множество, состоящее из n различных элементов. Если в множестве введено отношение порядка, т.е. определено какой элемент множества за каким следует или какому предшествует, то множество называют упорядоченным.

Перестановки Перестановки Пример. Пусть даны три буквы: A, B, C. Составим все возможные упорядоченные множества из этих букв: ABC; BCA; CBA; АCB; BAC; CAB. Этих множеств получилось 6 штук и они отличаются только порядком расположения букв (т.е. упорядоченные).

Упорядоченные множества из n элементов наз. перестановками из n элементов. Упорядоченные множества из n элементов наз. перестановками из n элементов. Таким образом, перестановки из n элементов отличаются только порядком следования элементов. Число перестановок из n элементов обозначается: Рn. (P – от английского слова «permutation» – перестановка) Общее число различных перестановок из n объектов равно:

Упорядоченные подмножества из n элементов по k элементов каждое наз. размещениями из n элементов по k элементов . Упорядоченные подмножества из n элементов по k элементов каждое наз. размещениями из n элементов по k элементов . Таким образом, размещения отличаются либо составом элементов, либо их порядком. Число таких размещений обозначим . A – от англ. «arrangement» – размещение. Число размещений равно:

Пример. В пятом классе изучают 8 учебных предметов. Сколькими способами можно составить расписание занятий на пятницу, если в этот день недели должно быть 5 различных уроков? Пример. В пятом классе изучают 8 учебных предметов. Сколькими способами можно составить расписание занятий на пятницу, если в этот день недели должно быть 5 различных уроков? Решение. Различных способов составления расписания столько, сколько существует пятиэлементных упорядоченных подмножеств у восьмиэлементного множества - число способов равно числу размещений из 8 элементов по 5, т.е. (n=8; k=5):

Пример. Сколькими способами можно рассадить 4-х студентов на 25-ти местах? Пример. Сколькими способами можно рассадить 4-х студентов на 25-ти местах? Решение.

Сочетания Сочетания Пример. Пусть даны три буквы: А, B, C. Составим подмножества из двух элементов: AB; AC; BC. Изменение порядка букв внутри этих подмножеств не приводит к новому подмножеству. Этих подмножеств получилось 3 штуки.

Подмножества из n элементов по k элементов каждое, отличающиеся хотя бы одним элементом, наз. сочетаниями из n элементов по k элементов. Подмножества из n элементов по k элементов каждое, отличающиеся хотя бы одним элементом, наз. сочетаниями из n элементов по k элементов. Таким образом, сочетания отличаются только составом элементов. Число сочетаний из n по k обозначается: C – от англ. «combination» – сочетание. Этот вид комбинаций дал название всему разделу математики. Общее число сочетаний равно:

Пример. Сколько экзаменационных комиссий, состоящих из 3-х человек, можно образовать из 7-ми преподавателей? Пример. Сколько экзаменационных комиссий, состоящих из 3-х человек, можно образовать из 7-ми преподавателей? Решение. Количество трехэлементных подмножеств у семиэлементного множества (n=7; k=3):

Задание №6. (Выбрать вариант ответа) Задание №6. (Выбрать вариант ответа) Количество разных способов выбора (порядок не имеет значения) 2 томов из 12 томного собрания сочинений Л. Толстого, равно … Варианты ответов: 1) 24 2) 132 3) 66 4) 2 Ответ: пункт № 3, т.е. количество сочетаний

Задание №8 (Выбрать один вариант ответа) Задание №8 (Выбрать один вариант ответа) Количество различных двузначных чисел, которые можно составить из цифр 1, 2, 3, 4 (все цифры различны) равно … Варианты ответов: 6 2) 24 3) 4 4) 12 Ответ: пункт №4., т.е. количество размещений

Ответ на домашнее задание Ответ на домашнее задание Р4 = 4! = 1 × 2 × 3 × 4 = 24