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

Элементы комбинаторики

• Ахмеджанова Т.Д.

Комбинаторика

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

Множество

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

Примеры множеств:

• множество всех действительных чисел,
• множество натуральных чисел,
• множество всех студентов данного университета,
• множество парт в данном классе.

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

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

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

• Множество, состоящее из n элементов, называется упорядоченным, если каждому элементу этого множества поставлено в соответствие натуральное число от 1 до n таким образом, что различным элементам соответствуют различные натуральные числа.
• Всякое конечное множество можно упорядочить.

Правило суммы

• Пусть некоторый предмет А может быть выбран m способами, а другой предмет В может быть выбран n способами. Тогда имеется m + n возможностей выбрать либо предмет А, либо предмет В.

Правило суммы

• А

• В

Задача 1

• От сквера Кирова до академгородка можно проехать через Ангарский мост, плотину и новый мост. В первом случае количество дорог равно 2, во втором — 2, в третьем — 3. Сколькими способами можно добраться от сквера Кирова до академгородка ?

Решение

• 2+2+3=7

• сквер

• академгородок

Правило произведения

• Пусть некоторый предмет А может быть выбран m способами, а другой предмет В может быть выбран n способами. Тогда имеется mn возможностей выбрать предмет А и предмет В.

Правило произведения

• В

• А

• В

• А

• В

• А

• В

• и

• А

• 

• 

• 

Задача 2

• В киоске продают 5 видов конвертов и 4 вида открыток. Сколькими способами можно купить конверт и открытку?

Решение

• 5 · 4 = 20

Задача 3

• Сколькими способами можно выбрать гласную и согласную буквы из слова КОНВЕРТ?

Решение

• Гласную можно выбрать двумя способами.
• Согласную — пятью способами.
• Ответ. 2 · 5 = 10.

• к

• о

• Н

• В

• Е

• Р

• Т

Задача 4

• Сколькими способами можно поставить на шахматную доску белую и чёрную ладьи так, чтобы они не били друг друга?

Решение

• 64 · 49 = 3136

Задача 5

• «Тёмное , чистое небо торжественно и необъятно высоко стояло над нами со всем своим таинственным великолепием».
• Сколько осмысленных предложений можно составить, вычёркивая некоторые слова этого предложения? (Во все предложения обязательно должны входить подлежащее небо и сказуемое стояло.)

Решение

• небо

• стояло

• тёмное

• чистое

• торжественно

• и высоко

• над нами

• со всем
• великолепием

• таинственным

• своим

• необъятно

Задача 6

• От Братска до Иркутска можно добраться поездом, самолётом, автобусом, теплоходом. Из Иркутска до Листвянки можно доехать на автобусе, либо на теплоходе. Сколькими способами можно проехать от Братска до Листвянки?

Решение

• Б

• И

• Л

Задача 7

• У двух начинающих коллекционеров по 20 марок и по 10 значков. Честным обменом называется обмен одной марки на одну марку или одного значка на один значок. Сколькими способами коллекционеры могут осуществить честный обмен?

Решение Задача 8

• На глобусе проведены 17 параллелей и 24 меридиана. На сколько частей разделена поверхность глобуса? Меридиан — это дуга, соединяющая Северный полюс с Южным. Параллель — это окружность, параллельная экватору (экватор тоже является параллелью).

Решение

• Меридианы делят глобус на 24 части, а параллели делят каждую часть ещё на 17 + 1 = 18 частей.

Задача 9

• Сколькими способами из колоды (36 карт) можно выбрать 4 карты разных мастей и достоинств?

Решение

• В каждой масти по 9 карт.
• Из каждой масти выбираем по 1 карте, учитывая достоинство уже выбранной ранее карты.

Факториал

• произведение всех натуральных чисел от 1 до n включительно (читается n–факториал).
• n! = 1•2•3•…•n
• Замечание: 0! = 1! =1.

• n!

Перестановки

• Число различных способов, которыми может быть упорядочено данное множество, состоящее из n элементов, называется числом перестановок множества и обозначается Pn.

Перестановки без повторений Задача 10

• Сколько существует четырехзначных чисел, в записи которых цифры 2, 3, 4, 5 встречаются ровно по одному разу?

Решение

• 2

• 3

• 4

• 5

• 2

• 4

• 5

• 2

• 5

• 5

• 4

• 3

• 2

• 1

Задача 11

• Сколько трёхзначных чисел можно получить из цифр 1,2,3, если цифры в числе не повторяются?

Решение

Сотни	1		2		3
Десятки	2	3	1	3	1	2
Единицы	3	2	3	1	2	1

Перестановки с повторениями

• Пусть имеются предметы k различных типов.
• Сколько перестановок можно сделать из n1 элементов первого типа, n2 элементов второго типа,..., nk элементов k-го типа?

Перестановки с повторениями Задача 12

• Сколькими способами можно переставить буквы слова «ананас», так, чтобы получались разные «слова»? Смысл «слов» значения не имеет.

Решение

• «Ананас» - 6:
• а – 3; н – 2; с – 1.

• А

• А

• А

• Н

• Н

• С

Задача 13

• К Маше пришли 7 подружек. Сколькими способами можно рассадить 8 человек за столом?

Решение Задача 14

• 8 девушек водят хоровод. Сколькими способами они могут встать в круг?

Решение

• Девушки могут перемещаться по кругу.
• Число перестановок уменьшается в 8 раз.
• Ответ: 7!

Задача 15

• Сколько ожерелий можно составить из 8 различных бусин?

Решение

• Ожерелье можно вращать.
• Его можно и перевернуть.
• Число перестановок уменьшается ещё вдвое.
• Ответ: 7!/2

Размещения

• Число упорядоченных k элементных подмножеств множества из n элементов называется числом размещений из n элементов по k и обозначается

Размещения

• Размещения с повторениями

• Размещения без повторений

Задача

• В машине 7 мест, включая водительское. Поедут 7 человек. Сколько существует способов распределения пассажиров по местам, если права есть лишь у троих?

Решение

• (3*6!=2160)

• 1

• 2

• 3

Задача

• У людоеда в подвале томятся 25 пленников. Сколькими способами он может выбрать трех из них себе на завтрак, обед и ужин?

Решение Задача

• Сколько существует 4-значных чисел, в записи которых встречаются только нечетные цифры?

Решение

• Однозначных нечётных чисел ровно 5.
• К каждому однозначному нечётному числу вторая нечетная цифра может быть дописана 5 различными способами.
• Далее – по аналогии:

• 1

• 3

• 5

• 7

• 9

• 1

• 3

• 5

• 7

• 9

• 1

• 3

• 5

• 7

• 9

• 1

• 3

• 5

• 7

• 9

Задача

• Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и В. Словом является любая последовательность, состоящая не более, чем из 4 букв. Сколько слов в языке племени Мумбо-Юмбо? Указание. Сосчитайте отдельно количества одно-, двух-, трех- и четырехбуквенных слов.

Решение

• 3 + 32 + 33 + 34 = 120

• А

• В

• Б

Сочетания

• Если из n элементов составлять группы по m элементов в каждой, не обращая внимания на порядок элементов в группе, то получившиеся при этом комбинации называются сочетаниями без повторений из n элементов по m.

Сочетания

• Сочетания без повторений

• Сочетания с повторениями

Задача.

• В городе проводится первенство по футболу. Сколько в нем состоится матчей, если участвуют 12 команд?

Решение. Задача.

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

Решение

• Не меньше 4 – это значит, что снайперов должно быть либо 4, либо 5.4 снайпера из 6 можно выбрать способами, остальных стрелков выбираем из оставшихся 4 стрелков (10-6) способами. Проводим аналогичные рассуждения, когда в группе снайперов 5.

Задача.

• В классе 24 ученика, из них 8 отличников. Нужно выбрать 12 человек так, чтобы среди них было хотя бы 5 отличников. Сколькими способами можно это сделать?
• Ответ: 901628

Свойства сочетаний Решить систему уравнений: Решение Треугольник Паскаля

• Треугольник Паскаля является одной из наиболее известных и изящных числовых схем во всей математике.
• Блез Паскаль, французский математик и философ, посвятил ей специальный "Трактат об арифметическом треугольнике".

Треугольник Паскаля

• Эта треугольная таблица была известна задолго до 1665 года - даты выхода в свет трактата.
• В 1529 году треугольник Паскаля был воспроизведен на титульном листе учебника арифметики, написанного астрономом Петром Апианом.

Изображен треугольник на иллюстрации книги "Яшмовое зеркало четырех элементов" китайского математика Чжу Шицзе, выпущенной в 1303 году.

• Изображен треугольник на иллюстрации книги "Яшмовое зеркало четырех элементов" китайского математика Чжу Шицзе, выпущенной в 1303 году.
• Омар Хайям, бывший философом, поэтом, математиком, знал о существовании треугольника в 1110 году, в свою очередь заимствовав его из более ранних китайских или индийских источников.

Построение треугольника Паскаля

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

Свойства строк

• Сумма чисел n-й строки Паскаля равна (потому что при переходе от каждой строки к следующей сумма членов удваивается, а для нулевой строки она равна =1)

Свойства строк

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

Свойства строк

• Каждый член строки треугольника Паскаля с номером n тогда и только тогда делится на т, когда т- простое число, а n - степень этого простого числа

Нахождение элемента треугольника

• Каждое число в треугольнике Паскаля можно определить тремя способами:
• где n - номер строки, k- номер элемента в строке;
• оно равно сумме чисел предыдущей диагонали, начиная со стороны треугольника и кончая числом, стоящим над данным.

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

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