Цикл уроков по теме "Введение в комбинаторику"

Урок 1. Введение в комбинаторику

Цели: дать понятие «Комбинаторика», «Комбинаторные задачи»; познакомить учащихся с историей данной науки; привести примеры нескольких комбинаторных задач с решениями для привития интереса учащихся к данной науке, ВВЕСТИ ПОНЯТИЕ ФАКТОРИАЛА, НАУЧИТЬСЯ ПРИМЕНЯТЬ .

Ход урока

Сообщение темы и целей

Работа по теме

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

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

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

Слово «азар» по-арабски означает «трудный». Арабы называли азартной игрой комбинацию очков, которая при бросании нескольких костей могла появиться лишь единственным образом. Например, при бросании двух костей трудным («азар») считалось появление в сумме двух или двенадцати очков. Первоначально комбинаторные задачи касались в основном азартных игр. Решались вопросы, сколькими способами можно получить некоторый набор карт в карточной игре, как часто выпадает выигрыш в той или иной лотерее. Эти и другие проблемы азартных игр и явились движущей силой в развитии комбинаторики.

Одним из первых занимался подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья (1500-1557).

В XVII веке изучением теоретических вопросов комбинаторики занимались французские ученые Б. Паскаль (1623-1662) и П. Ферма (1601-1665). Исходным пунктом их исследований тоже были проблемы азартных игр.

Дальнейшее развитие комбинаторики связано с именами Я. Бернулли (1654-705), Г. Лейбница (1646-1716) и Л. Эйлера (1707-1783). Однако и в работах этих математиков в основном рассматривались приложения к различным играм (лото, пасьянсы и т.д.). В дальнейшем комбинаторные методы играли значительную роль в развитии алгебры и геометрии.

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

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

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

При решении подобных задач мы каким-либо образом выбираем m элементов из общего числа n элементов некоторого множества E, при этом в постановке задачи четко оговариваем, каким способом составляется выборка.

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

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

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

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

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

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

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

Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н. Тарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б. Паскалю (1623-1662) и П. Ферма.

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

Введение в комбинаторику

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

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

Определение. Комбинаторика – это раздел математики, посвящённый задачам выбора и расположения предметов из различных множеств.

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

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

немецкий учёный

Готфрид Вильгельм Лейбниц.

(1.07.1646 - 14.11.1716)

Основы комбинаторики и теории вероятностей создали и разработали французские математики XVII века

Пьер Ферма и Блез Паскаль.

Пьер Ферма (1601-1665)

Блез Паскаль (1623-1662)

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

П. Лаплас

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор « либо А, либо В» можно осуществить m + n способами.

Пример:

На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

Решение:

По условию задачи яблоко можно выбрать

пятью способами, апельсин – четырьмя.

Так как в задаче речь идет о выборе

«либо яблоко, либо апельсин», то его,

согласно правилу сложения, можно

осуществить 5+4=9 способами.

Ответ: 9 способов.

Задача

Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?

Решение:

1 способ: перебор вариантов.

Для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7:

14, 17, 41, 47, 71, 74.

Ответ: 6 чисел.

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

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

2 способ решения задачи:

Эту задачу можно решить по-другому и намного быстрее. Рассуждать будем так. Первую цифру двузначного числа можно выбрать тремя способами. Так как после выбора первой цифры останутся две, то вторую цифру можно выбрать из оставшихся цифр уже двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 3∙2, т.е. 6.

Ответ: 6 чисел.

Факториал

Определение. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n . Обозначение n !

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

n

n!

0

1

1

2

1

3

2

4

6

5

24

6

120

7

720

8

5 040

9

40 320

10

362 880

3 628 800

4! = 1 • 2 • 3 • 4 = 24

3! = 1 • 2 • 3 = 6

6! = 1 • 2 • 3 • 4 • 5 • 6 = 720

Главное свойство факториала

(n+1)! = (n+1) • n!

Вычислить

Вычислить

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

Размещения

Сочетания

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

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

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

P n = n!

Пример 1.

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

Решение: P 8 = 8! = 40 320

Пример 2 .

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

Решение: Р 4 – Р 3 = 4! – 3! = 18.

Пример 3.

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

Решение:

Размещения

Определение. Размещением

из n элементов

конечного множества по k , где

, называют

упорядоченное множество, состоящее из k

элементов.

Пример 1.

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

Решение:

Пример 2.

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

Решение:

Пример 3.

Сколько существует трёхзначных чисел, составленных из цифр 1, 2, 3, 4, 5, 6 (без повторений), которые НЕ кратны 3?

Решение:

Сочетания

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

Равенство

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

Схема связи

сочетания

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

размещения

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

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

Сочетания

из m элементов

по n элементов

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

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

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

Размещения из

m элементов

по n элементов

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

Сколькими способами могут быть распределены I, II и III премии между 15-ю участниками конкурса?

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

P n

Пример 1.

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

Решение:

Пример 2.

Из вазы с цветами, в которой стоят 10 красных гвоздик и 5 белых, выбирают 2 красные гвоздики и одну белую. Сколькими способами можно сделать такой выбор букета?

Решение:

Пример 3.

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

Решение :

Различие между перестановками, размещениями, сочетаниями

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

отгадай ребусы

1.

2.

отгадай ребусы

3 .

4.

5.

Ответы:

• Вариант
• Сочетания
• Факториал
• Событие
• Исход

Домашнее задание

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

2. Решить уравнение :

Введение в комбинаторику

Основные понятия:

• Комбинаторика
• Правило сложения
• Правило умножения
• Факториал
• Перестановки
• Перестановки с повторениями
• Размещения
• Размещения с повторениями
• Сочетания
• Равенство
• Схема связи между размещениями, перестановками и сочетаниями
• Учимся различать виды соединений
• Бином Ньютона и его свойства
• Треугольник Паскаля
• Различие между перестановками, размещениями, сочетаниями
• Проверь себя

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

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

Определение. Комбинаторика – это раздел математики, посвящённый задачам выбора и расположения предметов из различных множеств.

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

2. Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка).

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

Бином Ньютона.

• «Би»-удвоение, раздвоение …
• «Ном»(фран . nombre) – номер, нумерация.
• «Бином» -»два числа»
• Бином Ньютона – это выражение вида
• Треугольником Паскаля пользуются при возведении бинома в натуральные степени.

Свойства бинома и биномиальных коэффициентов.

2) Число всех членов разложения на единицу больше показателя степени бинома, то есть равно (n+l).

3) Сумма показателей степеней a и b каждого члена разложения равна показателю степени бинома,

то есть n.

4) Биномиальные коэффициенты членов разложения, равноотстоящих от концов разложения, равны между собой:

(правило симметрии) .

Свойства бинома и биномиальных коэффициентов.

5) Сумма биномиальных коэффициентов всех членов разложения равна .

6) Сумма биномиальных коэффициентов, стоящих на нечетных местах, равна сумме биномиальных коэффициентов, стоящих на четных местах и равна

7) Правило Паскаля: .

Свойства бинома и биномиальных коэффициентов.

8)Любой биномиальный коэффициент, начиная со второго, равен произведению предшествующего биномиального коэффициента и дроби .

Пример .

Доказать, что при любом натуральном n число делится на 9.

Доказательство :

Начнем рассматривать бином в общем виде:

Тогда

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

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

…

…

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

столбцы

строки

0

0

1

1

1

2

2

1

3

1

1

3

4

4

2

1

5

5

1

3

1

6

6

4

1

3

…

1

6

5

…

1

6

…

10

4

15

1

10

5

20

1

15

6

1

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

…

Проверь себя

• Что такое комбинаторика?
• В чём состоит правило суммы?
• В чём состоит правило произведения?
• Что такое размещения?
• Запишите формулу для нахождения числа размещений.
• Что такое перестановки?
• Запишите формулу для нахождения числа перестановок.
• Что такое факториал?
• Что такое сочетания?
• Запишите формулу для нахождения числа сочетаний.
• В чём различие между перестановками, размещениями, сочетаниями?

Решение

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

Задача №1.

Сколько существует вариантов покупки одной розы, если продают

3 алые, 2 белые и 4 желтые розы?

Это важно

9

способов

Важно помнить, что выбирается не просто красная, белая или желтая роза, а одна конкретная роза: эта красная или эта белая, или эта желтая роза.

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

Вернуться к решению задачи №3

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

Если некоторый элемент А можно выбрать n способами, а элемент В – m способами, то выбор «либо А, либо В» можно сделать n + m способами.

A – n способов

В – m способов

А или В – (n + m)способов

Задача №2.

В столовой есть 2 первых блюда и 3 вторых. Сколько различных вариантов обеда из 2 блюд можно заказать?

2

Первое блюдо:

3

Второе блюдо:

3 + 3 =

2 ∙ 3 = 6 способов

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

Вернуться к решению задачи №3

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

Если некоторый элемент А можно выбрать n способами, а элемент В – m способами, то пару А и В можно выбрать n ∙ m способами.

A – n способов

В – m способов

А и В – (n ∙ m)способов

Задача №3.

На блюде лежат 8 яблок, 3 груши и 4 апельсина.

а) Сколькими способами можно взять один плод?

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

8 + 3 + 4 = 15 способов

Выбирается 1 плод.

б) Сколькими способами можно взять:

• яблоко с грушей

• яблоко с апельсином

• грушу с апельсином

• яблоко, грушу и апельсин

8 · 3 = 24 способа

Выбирается 2 или 3 плода.

8 · 4 = 32 способа

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

3 · 4 = 12 способов

8 · 3 · 4 = 96 способов

Задача №3.

На блюде лежат 8 яблок, 3 груши и 4 апельсина.

в) Сколькими способами можно взять два фрукта

с разными названиями?

Применяются оба правила.

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

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

Пара рассматривается

как единое целое.

Выбирается пара.

8 · 3 + 8 · 4 + 3 · 4 = 24 + 32 +12 = 68 способов

Задача №4.

Проверка(5)

Самостоятельная работа.

В пакетике драже лежат 9 красных, 10 синих

и 12 зеленых конфет.

а) Сколькими способами можно взять 1 конфету?

а) 9 + 10+ 12 = 31способ

б) Сколькими способами можно взять:

• красную и синюю конфеты

• красную и зеленую конфеты

б) 9 · 10 = 90 способов

• синюю и зеленую конфеты

9 · 12 = 108 способов

10· 12 = 120 способов

в) 9 · 10 + 9 · 12 + 10 · 12 = 318 способов

в) Сколькими способами можно взять две конфеты разного цвета?

Задача №5.

Сколько различных двузначных чисел можно составить, используя цифры 1,4, и 7, если цифры могут повторяться.

1 способ (перебор)

4

1

7

11

71

41

74

44

14

77

17

47

Ответ: 9 чисел

Задача №5.

Сколько различных двузначных чисел можно составить, используя цифры 1,4, и 7, если цифры могут повторяться.

2 способ (построение дерева различных вариантов)

4

1

7

1 цифра

7

1

4

7

1

1

4

7

4

2 цифра

74

11

14

47

71

77

17

41

44

Ответ: 9 чисел

Задача №5.

Сколько различных двузначных чисел можно составить, используя цифры 1,4, и 7, если цифры могут повторяться.

3 способ (использование формулы)

двузначное число

2цифра числа

(три выбора)

1 цифра числа

(три выбора)

3 · 3 = 9 чисел

Ответ: 9 чисел

Задача №6.

Проверка (3)

Самостоятельная работа.

Сколько различных трехзначных чисел можно составить используя цифры

3 и 5, если цифры могут повторяться? (задачу решить 3 способами)

3 способ

(формула)

1 способ

(перебор)

2 способ

(дерево различных вариантов)

3

333

5

555

2 · 2 · 2 = 8 чисел

553

335

5

3

3

5

355

533

353

535

3

5

3

5

5

3

5

3

Ответ: 8 чисел

Задача №7.

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

0, 1, 2, 3, если цифры могут повторяться .

двузначное число

2 цифра числа (четыре выбора : 0,1,2,3)

1 цифра числа

(три выбора: 1,2,3)

3 · 4 = 12 чисел

Ответ: 12 чисел

Задача №8.

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

4, 5, 6?

трехзначное число

2 цифра числа

(два выбора)

3 цифра числа

(один выбор)

1 цифра числа

(три выбора: 4,5,6)

Определение

3 · 2 · 1= 6 чисел

3 · 2 · 1= 3! = 6 чисел

Произведение всех натуральных чисел от 1 до n включительно называется n – факториал и обозначается символом n!

n! = 1 · 2 · 3 · … · n = n!

0! = 1

Ответ: 6 чисел