Элементы комбинаторики
презентация к уроку (алгебра, 9 класс) по теме

Слайд 1

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ Т.И. Размарилова учитель МОБУ « СОШ № 25» Г. Дальнегорск

Слайд 2

Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения. .

Слайд 3

Комбинаторика в доисторическую эпоху

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

О таких играх английский поэт Уордсворт писал: Не нужно нам владеть клинком Не ищем славы громкой. Тот побеждает, кто знаком С искусством мыслить тонким.

Слайд 8

Среди предметов, положенных в пирамиду, где 35 веков тому назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и 10 вертикалями и фигурки для древней игры " сенет ", правила которой мы, вероятно, никогда не узнаем. Позже появились нарды, шашки и шахматы, а также их различные варианты (китайские и японские шахматы, японские облавные шашки "го" и т.д.).В каждой из этих игр приходилось рассматривать различные сочетания передвигаемых фигур и выигрывал тот, кто их лучше заучил.

Слайд 9

Первое упоминание о вопросах, близких к комбинаторным, встречается в китайских рукописях, относящихся к 12-13 вв. до н. э. (точно датировать эти рукописи невозможно, поскольку в 213 г. до н. э. император Цин Ши-Хуан приказал сжечь все книги, так что до нас дошли лишь сделанные позднее копии .

Слайд 10

В этих книгах писалось, что все в мире является сочетанием двух начал - муж-ского и женского, которое авторы обозначали символами --- и -- --.В рукописи "Же Ким" ("Книга перестановок") показаны различные соединения этих знаков по два и по три.

Слайд 12

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

Слайд 13

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

Слайд 15

Если заменить каждую фигуру соответствующим числом, возникнет такая таблица: 4 2 9 3 5 7 8 1 6

Слайд 16

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

Слайд 17

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

Слайд 18

Слово «комбинаторика» происходит от латинского слова соmbinare , которое переводится как «соединять, сочетать».

Слайд 19

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

Слайд 20

Метод рекккурентных соотношений Метод производящих функций Метод включения и исключения Метод траекторий Метод графов

Слайд 21

Простейшие комбинаторные задачи можно решать методом перебора возможных вариантов.

Слайд 22

Пример 1. Четыре ученика класса Миша, Саша, Алёша, Таня углублённо изучают математику. На математическую олимпиаду требуется послать двух учеников. Сколькими способами это можно сделать ?

Слайд 23

Решение. Составим схему возможных вариантов. Миша Саш а Алёша Саша Алёша Таня Алёша Таня Таня Ответ: 6.

Слайд 24

Комбинаторные задачи бывают различных видов. Но большинство задач решаются с помощью двух основных правил - правила суммы и правила произведения .

Слайд 25

Пример: Если на одной полке книжного шкафа стоит 30 различных книг, а на другой - 40 различных книг (и не таких, как на первой полке), то выбрать одну книгу из стоящих на этих полках можно 30 + 40 = 70 способами. Правило суммы

Слайд 26

Если элемент a (а€А) может быть выбран m способами, а элемент b ( b €B) может быть выбран n способами, то число способов, которыми можно выбрать один элемент из множества А или множества В, равно сумме m + n .

Слайд 27

В одном классе 25 учеников, в другом — 27 учеников. Сколькими способами можно выбрать одного ученика из двух классов? Решение. 25 + 27 = 52. Ответ: 52.

Слайд 28

Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами. Правило произведения

Слайд 29

Пример. Пусть требуется составить набор из ручки, карандаша и линейки. Имеется: 5 различных ручек, 7 различных карандашей, 10 различных линеек. Сколькими способами можно составить требуемый набор?

Слайд 30

Решение. Действием в данном случае является составление набора из ручки, карандаша и линейки; действие распадается на три этапа: выбрать ручку, выбрать линейку и выбрать карандаш. Первую часть действия – выбрать ручку – можно выполнить пятью способами, вторую часть действия – выбрать карандаш – можно выполнить семью способами, третью часть действия – выбрать линейку – можно выполнить десятью способами. Тогда все действие можно выполнить : 5•7•10=350

Слайд 31

В одном классе 25 учеников, в другом — 27 учеников. Сколькими способами можно выбрать двух учеников по одному из каждого класса?

Слайд 32

Решение. Одного ученика первого класса можно выбрать 25 способами, а второго класса — 27 способами. Двух учеников по одному из каждого класса (по правилу умножения) можно выбрать 25 · 27 способами; 25 · 27 = 675.

Слайд 33

На книжной полке стоит 6 исторических романов и 4 приключенческих. Сколькими способами можно взять с полки 2 книги разных жанров?

Слайд 34

Решение: По правилу умножения существует 6 · 4 способов взять с полки 2 книги разных жанров. Ответ: 24.

Слайд 35

Пусть имеем n элементов, из которых требуется выбрать один за другим некоторые k элементов. Комбинаторное правило умножения в общем виде

Слайд 36

Если первый элемент можно выбрать n способами, после чего второй элемент можно выбрать n способами, затем третий элемент — n 3 способами и т.д., то число способов, которыми могут быть выбраны все k элементов, равно произведению n 1 · n 2 · n 3 ·... nk . .. 1

Слайд 37

Собрание из 30 человек должно выбрать председателя и секретаря. Сколькими способами это можно сделать?

Слайд 38

Председателем собрания можно выбрать 30 способами, после чего секретаря - 29 способами (из 29 оставшихся членов собрания). По правилу умножения существует 30 · 29 способов выбора председателя и секретаря. 30·29 = 870. Решение:

Слайд 39

Сколькими способами можно рассадить 5 гостей за праздничным столом, если приготовлено 8 мест?

Слайд 40

Для первого гостя имеется 8 возможностей выбрать место. После выбора места первым, для второго гостя остаётся 7 возможностей, аналогично для третьего гостя — 6 возможностей (из 6 свободных мест), для четвёртого — 5 вариантов, для пятого — 4. По правилу умножения получаем 8 · 7 · 6 · 5 · 4 = 6720 способов рассадить гостей.

Слайд 41

Из 10 членов шахматного кружка требуется составить команду из 3 человек для участия в соревнованиях. Сколькими способами это можно сделать?

Слайд 42

Первого члена команды (на первую доску) можно выбрать 10 способами, после чего второго (на вторую доску) — 9 способами, а третьего (на третью доску) — 8 способами. Всего получаем 10·9·8= 720 вариантов выбора трёх шахматистов из десяти. Решение:

Слайд 43

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

Слайд 44

Число перестановок из n элементов обозначают символом Р n (от французского слова permutation — «перестановка»).

Слайд 45

Если n = 3, то возможны шесть перестановок: а b с, ас b , b ас, b са , cab , cba ; P 3 = 6.

Слайд 46

Число перестановок из n элементов находится по формуле Р n = 1·2·3· ... ·( n ·1)· n .

Слайд 47

Число перестановок из n элементов равно произведению всех натуральных чисел от 1 до n ; Р n = n !

Слайд 48

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

Слайд 49

Р 5 =1·2·3·4·5 = 120. Ответ: 120.

Слайд 50

Каким числом способов 8 человек могут находиться в очереди?

Слайд 51

Ρ 8 =1·2·3·4·5·6·7·8 Ответ: 40 320 .

Слайд 52

Сколько различных четырёхзначных чисел можно составить из цифр 9, 7, 5, 0, если в каждом числе все цифры должны быть разными?

Слайд 53

Р 4 = 1 · 2 · 3 · 4 = 24. Р 3 = 1 · 2 · 3 = 6. Значит, Р 4 - Р 3 = 24-6 = 18. Ответ: 18.

Слайд 54

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

Слайд 55

Символ А n k обозначает число всевозможных размещений, которые можно составить из n элементов по k (А — первая буква французского слова arrangement , что означает «размещение», «приведение в порядок»).

Слайд 56

Число размещений из n по k равно произведению k последовательных натуральных чисел, наибольшее из которых равно n .

Слайд 58

Пример1: Сколько различных перестановок можно составить из букв слова АБАКАН. Решение. Требуется найти число перестановок на множестве из 6 элементов, среди которых три элемента одинаковы: Р 6 (3)=6!:3!=(6·5·4·3·2·1):(3·2·1)=120

Слайд 59

Пример 2: Сколько перестановок можно получить из букв слова КОЛОКОЛА? Решение. Требуется найти число перестановок с повторениями на множестве из 8 букв, среди которых: буква К повторяется 2 раза; буква О повторяется 3 раза; буква Л повторяется 2 раза буква А повторяется 1 раз. Таким образом,

Слайд 60

Пример3: Учащиеся класса изучают 11 различных предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 5 различных предметов?

Слайд 61

Решение. Различные варианты расписания могут отличаться либо самими предметами, либо их порядком. Количество вариантов равно числу размещений из 11 элементов по 5:

Слайд 62

Пример 4: В одиннадцатом классе 25 учащихся. На выпускном вечере ребята обменялись друг с другом фотокарточками. Сколько всего было роздано фотокарточек?

Слайд 63

Решение: 25 человек на упорядоченные пары можно разбить :

Слайд 64

Сочетания Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов.

Слайд 65

Число сочетаний, составленных из n элементов по k , вычисляется по формуле :

Слайд 66

Пример1: Сколько различных сигналов можно составить из четырех флажков различных цветов, если каждый сигнал должен состоять не менее чем из двух флажков?

Слайд 67

Пример 2: В вазе стоят 10 красных и 5 белых роз. а) Сколькими способами можно составить букет из 3 роз? 96 б) Сколькими способами можно составить букет из 1 красной и 2 белых роз? [ 455, 100]

Слайд 68

Из 9 мальчиков и 11 девочек спортивного класса для участия в соревнованиях надо составить команду, в которую должны входить 3 мальчика и 3 девочки. Сколькими способами это можно сделать? [ 13860]