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

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

Преподаватель: Перминова Е.В.

ГБПОУ СО «Свердловский педагогический коллеж»

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

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

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

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

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

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

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

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

известный немецкий учёный Готфрид Вильгельм Лейбниц.

(1.07.1646 - 14.11.1716)

• Основы комбинаторики и теории вероятностей создали и разработали французские математики XVII века Пьер Ферма и Блез Паскаль.

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

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

После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала.

Абрахам де Муавр, английский математик (1667-1754)

Джеймс Стирлинг, шотландский математик (1692-1770)

Комбинаторика и ее применение в реальной жизни.

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

П. Лаплас

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

Решение:

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

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

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

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

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

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

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

Задача:

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

Решение:

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

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

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

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

Задача:

2 способ: дерево возможных вариантов.

Для этой задачи построена специальная схема.

Ставим звездочку. Далее отводим от звездочки 3 отрезка. Так как в условии задачи даны 3 цифры – 1, 4, 7, то на концах отрезков ставим цифры 1, 4, 7.

Далее от каждой цифры проводим по 2 отрезка. На концах этих отрезков записываем также цифры 1, 4, 7. Получились числа: 14, 17, 41 47, 71, 74. То есть всего получилось 6 чисел. Эта схема действительно похожа на дерево, правда «вверх ногами» и без ствола

**

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

15

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

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

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

m-количество цифр стоящих на первом месте

n-количество цифр стоящих на втором месте

m∙n=3∙2=6

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

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

15

Л и л и и

Задача 1

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

m = 3, n = 4; m • n = 12

Решение:

Ответ: 12

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

Задача 2

Решение:

m=3, n=4, k=4; mnk=3 • 4 • 4 =48

Ответ: 48

Задача 3

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

Решение:

a = 2, b = 2, c = 2, d = 2, f=2;

= 32

2 • 2 • 2 • 2 • 2 =

abcdf =

Ответ: 32

Упражнения:

№ 1

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

1вариант: 1) 1, 2 и 3; 3) 5, 6, 7 и 8; 5) 0, 2, 4 и 6;

2 вариант: 2) 4, 5, и 6; 4) 6, 7, 8 и 9; 6) 0, 3, 5 и 7?

Ответ: 1), 2) 6 ; 3), 4) 12 ; 5), 6) 9 .

№ 2

Сколько различных трехзначных чисел можно записать с помощью цифр:

1 вариант: 1) 2 и 3; 3) 0 и 2;

2 вариант: 2) 8 и 9; 4) 0 и 5?

№ 1 в учебнике - № 1043; № 2 в учебнике - № 1044. Знак вопроса в квадрате – гиперссылка на решение упражнения №1. Буква i в круге и квадрате – гиперссылка на информацию о подобном решении задачи № 3 (о лилиях)

Ответ: 1), 2) 8 ; 3),4) 4 .

15

Решение упражнения № 1:

3

2

=

6

1), 2)

Х

3

=

4

12

3), 4)

Х

3

3

=

9

5), 6)

Х

15

С.Р.

№ 3

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

1 вариант: 1) 3, 4 и 5; 3) 5, 6, 7 и 8;

2 вариант: 2) 7, 8, и 9; 4) 1, 2, 3 и 4?

Ответ: 1),2) 6 ; 3),4) 24 .

№ 4

Сколько различных четырехбуквенных «слов» можно записать с помощью букв:

1 вариант: 1) «м» и «а»; 3) «к», «а» и «о»;

2 вариант: 2) «п» и «а»; 4) «ш», «а» и «л».

№ 3 в учебнике - № 1045; № 4 в учебнике - № 1046. С.Р.(на полях) – самостоятельная работа.

Ответ: 1), 2) 16 ; 3), 4) 81 .

15

№ 5

Путешественник может попасть из пункта А в пункт С, проехав через пункт В. Между пунктами А и В имеются три различные дороги, а между пунктами В и С - четыре различные дороги. Сколько существует различных маршрутов между пунктами А и С?

Решение:

№ 5 в учебнике - № 1047

С

В

А

m = 3, n = 4; mn = 3•4 = 12

Ответ: 12

21

№ 6

Чтобы попасть из города М в город К, нужно проехать через город N. Между городами М и N имеются четыре автодороги, а из города N в город К можно попасть либо поездом, либо самолетом. Сколько существует различных способов добраться из города М в город К?

С.Р.

№ 6 в учебнике - № 1048. «Дополнительно» – гиперссылка к дополнительным задачам к уроку. Треугольник в квадрате на полях – гиперссылка на новую тему: «Перестановки».

Ответ: 8

Дополнительно

21

7.

Сколькими способами могут распределиться золотая и серебряная медали на чемпионате по футболу, если в нем принимают участие:

1) 32 команды; 2) 16 команд?

1) 992 2) 240

8.

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

120

9.

Сколькими способами могут занять очередь в школьный буфет:

1) 6 учащихся; 2) 5 учащихся?

В учебнике: 7. - № 1049; 8. – № 1050; 9. - № 1052 – дополнительные задачи к уроку

1) 720 2) 120

Дополнительно

21

11.

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

4896

12.

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

6840

В учебнике: 11. - № 1053; 12. - № 1054; 13. - № 1056 – дополнительные задачи

13.

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

64800

21

Факториал.

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

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

n

n!

0

1

1

2

1

3

2

4

6

5

24

6

120

7

720

5 040

8

9

40 320

10

362 880

3 628 800

4) 1)             2)       3)          " width="640"

№ 1

Упростить формулу записи выражений (полагая, что k-натуральное число, k4)

1)

2)

3)

6) № 1 Ответ: 11! ; 18! .     № 2 Ответ: 22! ; 27! .     Ответ: (k+1)! ; k! . № 3    " width="640"

Упражнения:

Упростить формулу записи выражений (полагая, что k-натуральное число, k6)

№ 1

Ответ:

11! ;

18! .

№ 2

Ответ:

22! ;

27! .

Ответ:

(k+1)! ;

k! .

№ 3

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

Размещения

Сочетания

26

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

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

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

Задача 1:

1

24

=

3

2

4

Решение:

Х

Х

Х

24

Ответ:

30

Число перестановок:

P n = n(n –1)(n – 2)  3  2  1

(1)

Произведение первых n натуральных чисел обозначают

n ! (читается «эн факториал»)

n ! = 1  2  3  (n –2)(n–1)n

(2)

P n = n !

(3)

№ 1059 Найти значение:

1) P 5 = 5! = 5  4  3  2  1 = 120 ;

2) P 7 ;

3) P 9 ;

4) P 8 .

№ 1060 Сколькими способами можно рассадить четверых детей на четырех стульях в столовой?

№ 1063 Сколько различных чисел, не содержащих одинаковых цифр, можно записать с помощью цифр 1,2,3,4,5 так, чтобы:

1) последней была цифра 3;

3) первой была цифра 5, а второй – цифра 1;

5) первыми были цифры 3 и 4, расположенные в любом порядке?

Решение:

2

1

1

1)

3

4

= 24

32

Решение:

2

1

3

1

1

= 6

3)

3

1

2

5)

1

2

= 12

Упражнения:

№№ 1064 - 1071

Пример 1.

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

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

Пример 2 .

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

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

33

Пример 3.

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

Решение:

33

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

Определение .

Число перестановок n – элементов, в котором элементов i –того типа ( ) вычисляется по формуле

Задача : Сколько слов можно составить, переставив буквы в слове «экзамен», а в слове «математика»?

Решение: экзамен – 7 букв ( без повт.) ,

Математика - 10 букв ( с повт. м=2,а=3,т=2,е=и=к=1) ,

33

Размещения

повторение

Задача 1 .

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

12, 13, 14,

21, 23, 24,

31, 32, 34,

41, 42, 43.

1 способ – решение перебором :

Решение:

2 способ – по правилу произведения: m = 4, n = 3; mn = 12

Ответ: 12

Из задачи видно, что любые два соединения отличаются либо составом элементов (12 и 24), либо порядком их расположения (12 и 21). Такие соединения называют размещениями.

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

Обозначение:

 читают «А из эм по эн»:

= 12.

Примеры:

= m(m – 1)(m – 2) • … • (m – (n – 1))

(1)

= 4 • 3 = 12;

= 4 • 3 • 2 = 24;

= 5 • 4 • 3 = 60

=

(2)

Задача 2.

Сколькими способами можно обозначить данный вектор, используя буквы A, B, C, D, E, F?

Решение:

= 6 • 5 = 30

30 способами

Ответ:

З а д а ч а 3

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

= 56

Решение: n ≥ 2 и n

N. По формуле (1)

– n = 56,

= n(n – 1) =

– n, т. е.

– n – 56 = 0,

= 1

= – 7

+

т. е.

= 8

= – 56

•

n = – 7 – посторонний корень

n = 8

Ответ:

Задача 4

Вычислить:

Ответ: 225

№ 1073 – № 1075

Упражнения :

Д/З: § 62, № 1072, 1076

Пример 1.

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

Решение:

41

Пример 2.

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

Решение:

Пример 3.

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

Решение:

41

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

Определение.

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

Пример.

2- размещения с повторениями:

Число k – размещений с повторениями вычисляется по формуле:

Задача : Сколько существует номеров машин?

41

Сочетание

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

41

Равенство:

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

41

Схема связи:

порядок важен

порядок неважен

сочетания

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

размещения

41

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

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

Сочетания

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

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

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

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

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

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

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

m элементов

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

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

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

P n

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

• «Би»-удвоение, раздвоение …
• «Ном»(фран. 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

1

2

3

3

1

1

4

1

4

2

5

1

5

1

3

6

3

4

1

6

…

1

6

…

5

1

4

10

…

6

10

15

1

20

5

15

1

6

1

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

…

Пример 1.

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

Решение:

Пример 2.

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

Решение:

Пример 3.

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

Решение :

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

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

Проверь себя

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

О пользе комбинаторики или лишних знаний не бывает

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

1.

2.

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

3 .

4.

5.

Ответы:

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

Спасибо за внимание!

Д/З:

§ 60, №№ 1051, 1055.

Д/З: § 61, № 1063 (четные)

Электронные ресурсы:

кубики : http://free-math.ru/load/prezentacii_egeh_po_matematike/verojatnost_i_kombinatornoe/38-1-0-173 лилии:

http://ru.gde-fon.com/cvety?offset[0]=648

http://ru.gde-fon.com/cvety?offset[0]=666

http://ru.gde-fon.com/cvety?offset[0]=4590

шаблон:

http://www.myshared.ru/slide/56405/

Санкт-Петербург, 2014