Презентация к уроку "Основы комбинаторики"

Васильева
Галина Павловна

КГКП «Восточно-Казахстанский технологический колледж», г. Семей

Тема урока

Забытый pin-код: Сколько существует всевозможных вариантов pin-кода, состоящего из 4 цифр

А

В

С

D

А

В

С

D

Задача. Дан четырехугольник ABCD

Сколько можно выбрать вариантов, чтобы из пункта А попасть в пункт С?

А

В

С

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

Цели урока:

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

знать основные понятия, теоремы и формулы, относящиеся к разделу «Комбинаторика»
иметь чёткое представление о месте комбинаторики в теории вероятностей и математической статистике, о решении прикладных задач комбинаторными методами;

Задачи урока:

Комбинаторика – раздел математики, в котором изучается, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.

.

Задачей комбинаторики можно считать задачу размещения, сочетания или перестановки объектов по специальным правилам и нахождение числа способов таких действий

Особая примета комбинаторных задач – это вопрос, который всегда можно сформулировать так, чтобы он начинался словами «Сколькими способами…»

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

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

Как всё начиналось…

ЗАДАЧИ ДРЕВНЕГО КИТАЯ

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

В Древней Греции

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

Со временем появились различные игры (нарды, карты, шашки, шахматы)

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

Первоначально комбинаторика возникла в XVI в. в связи с распространением различных азартных игр.

Долгие века комбинаторика развивалась в недрах арифметики, геометрии, алгебры. Древнегреческие ученые большое внимание уделяли и комбинаторике чисел и геометрической комбинаторике - разрезанию фигур и т. д .

Комбинаторика как наука стала развиваться в XIII в. параллельно с возникновением теории вероятностей.
Первые научные исследования по этой теме принадлежат итальянским ученым Джероламо Кардано, Галилео Галилею

Комбинаторику, как самостоятельный раздел математики, первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666г. Он также впервые ввел термин «Комбинаторика».

Игра Кубик Рубика

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

Области применения комбинаторики:

лингвистика (рассмотрение вариантов комбинаций букв).

учебные заведения (составление расписаний);

сфера общественного питания (составление меню);

география (раскраска карт);

производство (распределение нескольких видов работ между рабочими);

спортивные соревнования (расчёт количества игр между участниками);

агротехника (размещение посевов на нескольких полях);

химия (анализ возможных связей между химическими элементами);

азартные игры (подсчёт частоты выигрышей);

биология (расшифровка кода ДНК);

доставка почты (рассмотрение вариантов пересылки).

экономика (анализ вариантов купли-продажи акций);

криптография (разработка методов шифрования);

астрология (анализ расположения планет и созвездий).

военное дело (расположение подразделений);

В настоящее время комбинаторика используется в кибернетике, дискретной математике, теории планирования и теории информации, архитектуре, дизайне интерьера

Задача: Составить из предложенных геометрических фигур образно-фигуративные композиции (животные, птицы, люди)

Основные задачи комбинаторики

Основными задачами комбинаторики считаются следующие:
составление упорядоченных множеств (образование перестановок);
составление подмножеств данного множества (образование сочетаний)
составление упорядоченных подмножеств данного множества (образование размещений)

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

Правило сложения:

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

4*3=12

Решение

5 · 4 = 20

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

#:
2! =
3! =
4! =
5! =

12 = 2

123 = 6

123 4 = 24

123 4 5 = 120

Больший факториал можно представить через меньший:

6!= 1  2  3  4  5 6= 5!6 = 1206= 720

#1. Вычислить:

№2.

Таблица факториалов

16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000
26! = 403291461126605635584000000
27! = 10888869450418352160768000000
28! = 304888344611713860501504000000
29! = 8841761993739701954543616000000
30! = 265252859812191058636308480000000

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000

100! ≈ 9,33×10157
1000! ≈ 4,02×102567
10000! ≈ 2,85×1035 659

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

Задача «Квартет»

P(4) = 4! = 1 * 2 * 3 * 4 = 24

Задача. Сколькими способами можно установить дежурство по одному человеку в день среди семи учащихся группы в течение 7 дней (каждый должен отдежурить один раз)?

Р(7)= 7! = 1•2•3•4•5•6•7= 5040

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

P = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 =
= 3 628 800 (дней) ≈ 9 942 (года).
Если кушать 3 раза в день,
то можно потратить 3 314 лет.

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

Всякое размещение с повторениями, в котором элемент а1 повторяется k1 раз, элемент a2 повторяется k2 раз и т.д. элемент an повторяется kn раз, где k1, k2, ..., kn — данные числа, называется перестановкой с повторениями порядка m = k1 + k2 + … + kn, в которой данные элементы a1, a2, …, an повторяются соответственно k1, k2, .., kn раз.

Пример

Слова и фразы с переставленными буквами называют анаграммами. Сколько анаграмм можно составить из слова «макака»?
Решение.

Всего в слове «МАКАКА» 6 букв (m=6).
Определим сколько раз в слове используется каждая буква:
«М» - 1 раз (k1=1)
«А» - 3 раза (k2=3)
«К» - 2 раза (k3=2)

Подмножества, составленные из n элементов данного множества и содержащие k элементов в каждом подмножестве, называют сочетаниями из n элементов по k. (Сочетания различаются только элементами, порядок их не важен: ab и ba – это одно и тоже сочетание).

Свойства сочетаний

Задача. Из 20 учащихся надо выбрать двух дежурных. Сколькими способами это можно сделать?

Решение. Надо выбрать двух человек из 20.
Ясно, что от порядка выбора ничего не зависит, то есть

Иванов - Петров или Петров - Иванов - это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2.

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

Пример использования

Задача №1
Сколько наборов из 7 пирожных можно составить, если в распоряжении имеются 4 сорта пирожных?
Решение:

Размещением

Задача
Из 12 учащихся нужно отобрать по одному человеку для участия в городских олимпиадах по математике, физике, истории и географии. Каждый из учащихся участвует только в одной олимпиаде. Сколькими способами это можно сделать?

Решение:

Задача
Сколько существует семизначных телефонных номеров, в которых все цифры различны и первая цифра отлична от нуля?

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

Задача. Телефонный номер состоит из 7 цифр. Какое наибольшее число звонков неудачник-Петя может совершить прежде, чем угадает правильный номер.

Решение. Т.к. цифры могут повторяться, то всего возможнразных номеров.

Если Петя невезучий, он должен будет звонить 10 миллионов раз.
Ответ: 10000000.

Забытый pin-код: Сколько существует всевозможных вариантов pin-кода?
Решение: 1) pin-код состоит из 4 цифр, всего цифр 10, они могут повторяться, порядок расположения цифр в числе важен. Значит это задача на подсчет количества размещений с повторениями.
2) Воспользуемся формулой
Получим

Число размещений, перестановок и сочетаний связаны равенством:

Схема связи:

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

Учимся различать виды соединений.

Сколькими способами можно с помощью букв A,B,C,D обозначить вершины четырехугольника?

Меняется только порядок расположения выбранных элементов

Перестановки из n элементов

У лесника три собаки: Астра, Вега и Граф. На охоту лесник решил пойти с двумя собаками. Перечислите все варианты выбора лесником пары собак.

Меняется только состав входящих в комбинацию элементов, порядок их расположения не важен

Меняется состав входящих в комбинацию элементов и важен порядок их расположения

В коробке лежат 5 синих, 4 красных, 3 зеленых карандаша. Наудачу вынимают 3 карандаша. Найти вероятность того, что это будут карандаши разного цвета.
Решение: Пусть А – все 3 карандаша будут разного цвета. Тогда число всевозможных исходов
Число благоприятных исходов
Вероятность события А равна

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

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

С комбинаторными величинами приходится иметь дело представителям многих специальностей: ученому – химику, биологу, конструктору, диспетчеру и т.п.

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

Заключение:

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