Слайд 1Элементы комбинаторики
Ахмеджанова Т.Д.
Слайд 2Комбинаторика
- раздел математики, посвященный решению задач выбора и расположения элементов
некоторого, как правило, конечного множества в соответствии с заданными правилами.
Слайд 3Множество
Всякая совокупность элементов произвольного рода, обладающая некоторым общим свойством, образует
множество (соединение).
Слайд 4Примеры множеств:
множество всех действительных чисел,
множество натуральных чисел,
множество всех студентов
данного университета,
множество парт в данном классе.
Слайд 5Множество считается определенным, если указаны все его элементы или указано
их общее свойство.
Множества, содержащие конечное число элементов, называются конечными.
Характеристикой конечного множества является число его элементов.
Слайд 6Множество, состоящее из n элементов, называется упорядоченным, если каждому элементу
этого множества поставлено в соответствие натуральное число от 1 до
n таким образом, что различным элементам соответствуют различные натуральные числа.
Всякое конечное множество можно упорядочить.
Слайд 7Правило суммы
Пусть некоторый предмет А может быть выбран m способами,
а другой предмет В может быть выбран n способами. Тогда
имеется m + n возможностей выбрать либо предмет А, либо предмет В.
Слайд 9Задача 1
От сквера Кирова до академгородка можно проехать через Ангарский
мост, плотину и новый мост. В первом случае количество дорог
равно 2, во втором — 2, в третьем — 3. Сколькими способами можно добраться от сквера Кирова до академгородка ?
Слайд 11Правило произведения
Пусть некоторый предмет А может быть выбран m способами,
а другой предмет В может быть выбран n способами. Тогда
имеется mn возможностей выбрать предмет А и предмет В.
Слайд 13Задача 2
В киоске продают 5 видов конвертов и 4 вида
открыток. Сколькими способами можно купить конверт и открытку?
Слайд 15Задача 3
Сколькими способами можно выбрать гласную и согласную буквы из
слова КОНВЕРТ?
Слайд 16Решение
Гласную можно выбрать двумя способами.
Согласную — пятью способами.
Ответ.
2 · 5 = 10.
к
о
Н
В
Е
Р
Т
Слайд 17Задача 4
Сколькими способами можно поставить на шахматную доску белую и
чёрную ладьи так, чтобы они не били друг друга?
Слайд 19Задача 5
«Тёмное , чистое небо торжественно и необъятно высоко стояло
над нами со всем своим таинственным великолепием».
Сколько осмысленных предложений
можно составить, вычёркивая некоторые слова этого предложения? (Во все предложения обязательно должны входить подлежащее небо и сказуемое стояло.)
Слайд 20Решение
небо
стояло
тёмное
чистое
торжественно
и высоко
над нами
со всем
великолепием
таинственным
своим
необъятно
Слайд 21Задача 6
От Братска до Иркутска можно добраться поездом, самолётом, автобусом,
теплоходом. Из Иркутска до Листвянки можно доехать на автобусе, либо
на теплоходе. Сколькими способами можно проехать от Братска до Листвянки?
Слайд 23Задача 7
У двух начинающих коллекционеров по 20 марок и по
10 значков. Честным обменом называется обмен одной марки на одну
марку или одного значка на один значок. Сколькими способами коллекционеры могут осуществить честный обмен?
Слайд 25Задача 8
На глобусе проведены 17 параллелей и 24 меридиана. На
сколько частей разделена поверхность глобуса? Меридиан — это дуга, соединяющая Северный
полюс с Южным. Параллель — это окружность, параллельная экватору (экватор тоже является параллелью).
Слайд 26Решение
Меридианы делят глобус на 24 части, а параллели делят каждую
часть ещё на 17 + 1 = 18 частей.
Слайд 27Задача 9
Сколькими способами из колоды (36 карт) можно выбрать 4
карты разных мастей и достоинств?
Слайд 28Решение
В каждой масти по 9 карт.
Из каждой масти выбираем по
1 карте, учитывая достоинство уже выбранной ранее карты.
Слайд 29Факториал
произведение всех натуральных чисел от 1 до n включительно (читается
n–факториал).
n! = 1•2•3•…•n
Замечание: 0! = 1! =1.
n!
Слайд 30Перестановки
Число различных способов, которыми может быть упорядочено данное множество, состоящее
из n элементов, называется числом перестановок множества и обозначается Pn.
Слайд 32Задача 10
Сколько существует четырехзначных чисел, в записи которых цифры 2,
3, 4, 5 встречаются ровно по одному разу?
Слайд 33
Решение
2
3
4
5
2
4
5
2
5
5
4
3
2
1
Слайд 34Задача 11
Сколько трёхзначных чисел можно получить из цифр 1,2,3, если
цифры в числе не повторяются?
Слайд 36Перестановки с повторениями
Пусть имеются предметы k различных типов.
Сколько перестановок
можно сделать из n1 элементов первого типа, n2 элементов второго
типа,..., nk элементов k-го типа?
Слайд 38Задача 12
Сколькими способами можно переставить буквы слова «ананас», так, чтобы
получались разные «слова»? Смысл «слов» значения не имеет.
Слайд 39Решение
«Ананас» - 6:
а – 3; н – 2; с
– 1.
А
А
А
Н
Н
С
Слайд 40Задача 13
К Маше пришли 7 подружек. Сколькими способами можно рассадить
8 человек за столом?
Слайд 42Задача 14
8 девушек водят хоровод. Сколькими способами они могут встать
в круг?
Слайд 43Решение
Девушки могут перемещаться по кругу.
Число перестановок уменьшается в 8 раз.
Ответ: 7!
Слайд 44Задача 15
Сколько ожерелий можно составить из 8 различных бусин?
Слайд 45Решение
Ожерелье можно вращать.
Его можно и перевернуть.
Число перестановок уменьшается ещё вдвое.
Ответ:
7!/2
Слайд 46Размещения
Число упорядоченных k элементных подмножеств множества из n элементов называется
числом размещений из n элементов по k и обозначается
Слайд 48Задача
В машине 7 мест, включая водительское. Поедут 7 человек. Сколько
существует способов распределения пассажиров по местам, если права есть лишь
у троих?
Слайд 50Задача
У людоеда в подвале томятся 25 пленников.
Сколькими способами он
может выбрать трех из них себе на завтрак, обед и
ужин?
Слайд 52Задача
Сколько существует 4-значных чисел, в записи которых встречаются только нечетные
цифры?
Слайд 53Решение
Однозначных нечётных чисел ровно 5.
К каждому однозначному нечётному числу
вторая нечетная цифра может быть дописана 5 различными способами.
Далее –
по аналогии:
1
3
5
7
9
1
3
5
7
9
1
3
5
7
9
1
3
5
7
9
Слайд 54Задача
Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и
В. Словом является любая последовательность, состоящая не более, чем из
4 букв. Сколько слов в языке племени Мумбо-Юмбо? Указание. Сосчитайте отдельно количества одно-, двух-, трех- и четырехбуквенных слов.
Слайд 55Решение
3 + 32 + 33 + 34 = 120
А
В
Б
Слайд 56Сочетания
Если из n элементов составлять группы по m элементов
в каждой, не обращая внимания на порядок элементов в группе,
то получившиеся при этом комбинации называются сочетаниями без повторений из n элементов по m.
Слайд 58Задача.
В городе проводится первенство по футболу. Сколько в нем состоится
матчей, если участвуют 12 команд?
Слайд 60Задача.
В группе 10 стрелков, из них 6 снайперов. Для выполнения
боевой задачи нужно отобрать 5 стрелков, причем снайперов должно быть
не меньше 4. Сколькими способами это можно сделать?
Слайд 61Решение
Не меньше 4 – это значит, что снайперов должно быть
либо 4, либо 5.4 снайпера из 6 можно выбрать способами,
остальных стрелков выбираем из оставшихся 4 стрелков (10-6) способами. Проводим аналогичные рассуждения, когда в группе снайперов 5.
Слайд 62Задача.
В классе 24 ученика, из них 8 отличников. Нужно выбрать
12 человек так, чтобы среди них было хотя бы 5
отличников. Сколькими способами можно это сделать?
Ответ: 901628
Слайд 66Треугольник Паскаля
Треугольник Паскаля является одной из наиболее известных и изящных
числовых схем во всей математике.
Блез Паскаль, французский математик и
философ, посвятил ей специальный "Трактат об арифметическом треугольнике".
Слайд 67Треугольник Паскаля
Эта треугольная таблица была известна задолго до 1665 года
- даты выхода в свет трактата.
В 1529 году треугольник
Паскаля был воспроизведен на титульном листе учебника арифметики, написанного астрономом Петром Апианом.
Слайд 68Изображен треугольник на иллюстрации книги "Яшмовое зеркало четырех элементов" китайского
математика Чжу Шицзе, выпущенной в 1303 году.
Омар Хайям, бывший
философом, поэтом, математиком, знал о существовании треугольника в 1110 году, в свою очередь заимствовав его из более ранних китайских или индийских источников.
Слайд 69Построение треугольника Паскаля
Треугольник Паскаля - это бесконечная числовая таблица "треугольной
формы", в которой на вершине и по боковым сторонам стоят
единицы, каждое из остальных чисел равно сумме двух чисел, стоящих над ним слева и справа в предшествующей строке.
Таблица обладает симметрией относительно оси, проходящей через его вершину.
Слайд 70Свойства строк
Сумма чисел n-й строки Паскаля равна (потому что при
переходе от каждой строки к следующей сумма членов удваивается, а
для нулевой строки она равна =1)
Слайд 71Свойства строк
Все строки треугольника Паскаля симметричны (потому что при переходе
от каждой строки к следующей свойство симметричности сохраняется, а нулевая
строка симметрична).
Слайд 72Свойства строк
Каждый член строки треугольника Паскаля с номером n тогда
и только тогда делится на т, когда т- простое число,
а n - степень этого простого числа
Слайд 73Нахождение элемента треугольника
Каждое число в треугольнике Паскаля можно определить тремя
способами:
где n - номер строки, k- номер элемента в
строке;
оно равно сумме чисел предыдущей диагонали, начиная со стороны треугольника и кончая числом, стоящим над данным.
Слайд 74Каждое число треугольника Паскаля, уменьшенное на единицу, равно сумме всех
чисел, заполняющих параллелограмм, ограниченный теми правой и левой диагоналями, на
пересечении которых стоит данное число, причем сами эти диагонали в рассматриваемый параллелограмм не включаются.