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

Основные понятия комбинаторики: размещения, сочетания, перестановки – и формулы для их вычисления

Задачи:

1. Изучить основные понятия комбинаторики;

2. Рассмотреть задачи на применение формул комбинаторики;

3. Изучить историю возникновения комбинаторики;

4. Рассмотреть применение комбинаторики в различных областях жизни человека;

5. Заполнить оценочный лист.

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

Комбинаторика – это раздел

математики, в котором изучаются

вопросы выбора или расположения

элементов множества в соответствии

с заданными правилами.

«Комбинаторика» происходит от латинского

слова « combina », что в переводе на русский

означает – «сочетать», «соединять».

ИСТОРИЧЕСКАЯ СПРАВКА

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

Г.В.Лейбниц

В XVIII веке к решению комбинаторных задач обращались и другие выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

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

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

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

Со временем появились различные игры

(нарды, карты, шашки, шахматы и т. д.)

Готфрид Вильгельм Лейбниц (1.07.1646 - 14.11.1716)

Леонард Эйлер(1707-1783)

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

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

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

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

Если первое действие можно выполнить n 1 способами, второе действие – n 2 – способами и так до к-того действия, которое можно выполнить n k - способами, то выполнить одно из этих к - действий можно n 1 + n 2 +…+ n k способами

Правила комбинаторики

Пример

• Пусть в одном ящике есть 5 шаров, а во втором – 7 шаров. Сколькими способами можно вытащить 1 шар из одного из этих ящиков?
• Ответ: 5+7=12 способами

• Правило произведения: Пусть требуется выполнить одно за другим какие-то к действий. Если первое действие можно выполнить n 1 способами, второе действие – n 2 – способами и так до к-го действия, которое можно выполнить n k - способами, то все к - действий вместе могут быть выполнены n 1 n 2 … n k способами.

Правила комбинаторики

• Сколько чисел можно составить из цифр 0,1,2,3,4,5,6,7,8,9, если число должно быть двузначным?

• Ответ: первую цифру можно выбрать – 9 способами (нет числа начинающегося с нуля). Вторую цифру – 10 способами, по правилу произведения – 90 способов.

Пример

Проверь себя

В вазе 6 яблок, 5 груш и 4 сливы. Сколько вариантов выбора одного плода?

• В вазе 6 яблок, 5 груш и 4 сливы. Сколько вариантов выбора одного плода?

РЕШЕНИЕ

Проверь себя

В вазе 6 яблок, 5 груш и 4 сливы. Сколько вариантов выбора одного плода?

• В вазе 6 яблок, 5 груш и 4 сливы. Сколько вариантов выбора одного плода?

Решение.

По правилу сложения: 6+5+4=15 способов.

Ответ: 15 способов

Проверь себя

Сколькими способами можно составить пару из одной гласной и одной согласной букв слова «платок»?

• Сколькими способами можно составить пару из одной гласной и одной согласной букв слова «платок»?

РЕШЕНИЕ

Проверь себя

Сколькими способами можно составить пару из одной гласной и одной согласной букв слова «платок»?

• Сколькими способами можно составить пару из одной гласной и одной согласной букв слова «платок»?

Решение.

Гласных: 2 шт (а,о)

Согласных – 4 шт (п,л,т,к)

По правилу произведения 2∙4=8 способов

Ответ: 8 способов

Проверь себя

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

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

РЕШЕНИЕ

Проверь себя

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

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

Решение.

Четных цифр: 5 шт (0,2,4,6,8)

1 цифра – 4 способа

2 цифра – 5 способов

3 цифра – 5 способов

по правилу произведения 4∙5∙5=100 способов

Ответ: 100 способов

Проверь себя

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

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

РЕШЕНИЕ

Проверь себя

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

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

Решение.

1 цифра – 9 способов (кроме 0)

2 цифра – 10 способов

3 цифра – 1 способ (только 7)

4 цифра – 10 способов

5 цифра- 5 способов (0,2,4,6,8)

По правилу произведения: 9∙10∙1∙10∙5=4500 способов

Ответ: 4500 способов

Комбинаторные соединения

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

• Перестановки без повторений
• Перестановки с повторениями

• Размещения

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

• Сочетания

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

« Эн факториал»- n! .

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

Произведение подряд идущих первых n

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

«эн факториал» : n! =1•2•3•…•( n-1)•n .

2!=

1•2=

2

Удобная формула!!!

3!=

1•2•3=

6

1•2•3•4=

24

4!=

n!=(n-1)!•n

5!=

1•2•3•4•5=

120

720

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

6!=

7!=

1•2•3•4•5•6•7=

5040

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

Формула:

Историческая справка

В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. "Искусство предположений" не было завершено автором и появилось после его смерти. Сочинение состояло из 4 частей, комбинаторике была посвящена вторая часть, в которой содержится формула для числа перестановок из n элементов.

Пример

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

Решение задачи:

Существует 8 мест, которые должны занять 8 человек.

На первое место может встать любой из 8 человек, т.е. способов занять первое место – 8.

После того, как один человек встал на первое место, осталось 7 мест и 7 человек, которые могут быть на них размещены, т.е. способов занять второе место – 7. Аналогично для третьего, четвертого и т.д. места.

Используя принцип умножения, получаем произведение . Такое произведение обозначается как 8! (читается 8 факториал) и называется перестановкой P 8.

Ответ : P 8 = 8!

Из чисел 1, 5, 9 составить трёхзначное

число без повторяющихся цифр.

Всего 2•3=6 комбинаций.

9

1

5

519

591

915

951

195

159

2 комбинации

2 комбинации

2 комбинации

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

На первое место можно поставить одну из четырех книг, на вторую – любую из трех, на третье – любую из двух и на четвертое – последнюю оставшуюся книгу. Применяя последовательно правило произведения, получим Р(4) = 4х3х2х1=24.

Ответ: 24 способа

Проверь себя

2) Сколькими способами можно положить 10 различных открыток в 10 имеющихся конвертов (по одной открытке в конверт)?

РЕШЕНИЕ

Проверь себя

2) Сколькими способами можно положить 10 различных открыток в 10 имеющихся конвертов (по одной открытке в конверт)?

Решение.

По формуле перестановки находим:

Р (10)= 10! = 1х2х3х…х9х10=3628800

Ответ: 3628800 способа

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

По формуле перестановки находим:

Р(8)= 8! = 1х2х3х…х7х8=40320

Ответ: 40320 способа

Проверь себя

4) Сколько различных слов можно составить, переставляя местами буквы в слове «треугольник» (считая и само это слово)?

РЕШЕНИЕ

Проверь себя

4) Сколько различных слов можно составить, переставляя местами буквы в слове «треугольник» (считая и само это слово)?

Решение.

По формуле перестановки находим:

Р (11)= 11! = 1х2х3х…х10х11= 39916800

Ответ: 39916800 с лов.

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

По формуле перестановки находим:

Р(7)= 7! = 1х2х3х…х6х7= 5040

Ответ: 5040 способа .

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

Всякое размещение с повторениями, в котором элемент а 1 повторяется k 1 раз, элемент a 2 повторяется k 2 раз и т.д. элемент a n повторяется k n раз, где k 1 , k 2 , ..., k n — данные числа, называется перестановкой с повторениями порядка

m = k 1 + k 2 + … + k n , в которой данные элементы a 1 , a 2 , …, a n повторяются соответственно k 1 , k 2 , .., k n раз.

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

Теорема. Число различных перестановок с повторениями из элементов {a 1 , …, an} , в которых элементы a 1 , …, an повторяются соответственно k 1 , ..., kn раз, равно

m!

k1! k2! … kn!

P

Пример

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

Решение.

Всего в слове «МАКАКА» 6 букв (m=6) .

Определим сколько раз в слове используется каждая буква:

«М» - 1 раз ( k 1 =1)

«А» - 3 раза (k 2 =3)

«К» - 2 раза (k 3 =2)

m!

6 !

4*5*6

Р =

Р 1,3,2 =

60 .

=

=

2

1 ! 3 ! 2 !

k 1 ! k 2 ! … k n !

Проверь себя

1) Сколько различных слов можно получить, переставляя буквы слова "математика" ?

РЕШЕНИЕ

РЕШЕНИЕ

Проверь себя

1) Сколько различных слов можно получить, переставляя буквы слова "математика" ?

Решение.

Всего в слове «МАТЕМАТИКА» 10 букв (m=10) .

Определим, сколько раз в слове используется каждая буква: «М» - 2; «А» - 3; «Т» - 2; «Е» - 1; «И» - 1; «К» -1. (k 1 , k 2 , … , k n )

10 !

4*5*6*7*8*9*10

Р 2,3,2,1,1,1 =

=

=

151200.

2! 3! 2! 1! 1! 1!

2*2

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

Комплект белых шахматных фигур состоит из 8 фигур:

1 король, 1 ферзь, 2 ладьи, 2 слона и 2 коня

(m= 8; k1, k2, … , kn)

8 !

3*4*5*6*7*8

Р 2,3,2,1,1,1 =

=

5040.

=

1! 1! 2! 2! 2!

2*2

Проверь себя

3) У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение девяти дней подряд она дает сыну один из оставшихся фруктов. Сколькими способами это может быть сделано?

РЕШЕНИЕ

Проверь себя

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

Решение.

У мамы всего 9 фруктов: два яблока, три груши и четыре апельсина. (k 1 , k 2 , … , k n )

9 !

5*6*7*8*9

Р 2,3,4 =

=

=

1260.

2! 3! 4!

2*2*3

Историческая справка

Комбинаторные мотивы можно заметить еще в символике китайской «Книги перемен»  (V век до н. э.).

В  XII в.  индийский математик  Бхаскара  в своём основном труде «Лилавати» подробно исследовал задачи с перестановками и сочетаниями, включая перестановки с повторениями.

Размещения

Размещением из n элементов по m

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

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

Пример

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

Решение:

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

40!

A = =38*39*40=59280

3

37!

40

Даны числа 1,2,3,4. Сколько можно составить двузначных чисел?

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

7!

А = =840

4

3!

7

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

10!

А = =720

3

7!

10

Проверь себя

3. В классе изучаются 7 предметов . В среду 4 урока , причем все разные. Сколькими способами можно составить расписание на среду?

РЕШЕНИЕ

Проверь себя

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

Решение.

7!

А = =840

4

3!

7

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

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

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

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

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

Так как учебники по каждому предмету одинаковые, и библиотекарь записывает лишь название (без номера),то список – размещение с повторением , число элементов исходного множества равно 10, а количество позиций – 5.

Тогда количество разных списков равно

= 100000.

Ответ : 100000

Проверь себя!

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

РЕШЕНИЕ

РЕШЕНИЕ

РЕШЕНИЕ

Проверь себя!

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

Решение.

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

разных номеров.

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

Ответ : 10000000 .

Проверь себя!

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

РЕШЕНИЕ

РЕШЕНИЕ

Проверь себя!

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

Решение.

В английском алфавите 26 букв, буквы могут повторяться, значит, количество слов равно

(26 элементов и 4 позиции)

Ответ:

Проверь себя!

3. В магазине, где есть 4 вида мячей , решили поставить в ряд 8 мячей . Сколькими способами можно это сделать, если их расположение имеет значение?

РЕШЕНИЕ

Проверь себя!

3. В магазине, где есть 4 вида мячей , решили поставить в ряд 8 мячей . Сколькими способами можно это сделать, если их расположение имеет значение?

Решение.

Разных видов мячей 4, позиций 8, т.е. количество различных размещений будет равно = 65536.

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

Проверь себя!

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

РЕШЕНИЕ

Проверь себя!

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

Решение.

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

Оно равно = 1296 (6 позиций и 4 вида).

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

Сочетания

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

Сочетания – конечные множества, в которых порядок не имеет значения.

Сочетания

Формула нахождения количества сочетаний без  повторений:

Историческая справка

В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними, находит все k -сочетания из n элементов, выводит свойства сочетаний:

,

,

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

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

Решение:

m = 2 ( необходимое количество дежурных )

n = 25 (всего учеников в классе)

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

Из 20 учащихся надо выбрать двух дежурных.

Сколькими способами это можно сделать?

Решение:

Надо выбрать двух человек из 20.

Ясно, что от порядка выбора ничего не зависит, то есть

Иванов - Петров или Петров - Иванов - это одна

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

Проверь себя!

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

РЕШЕНИЕ

Проверь себя!

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

Решение:

Проверь себя!

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

РЕШЕНИЕ

Проверь себя!

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

Решение:

Проверь себя!

3) В школьном хоре 6 девочек и 4 мальчика. Сколькими способами можно выбрать из состава школьного хора 2 девочек и 1 мальчика для участия в выступлении окружного хора?

РЕШЕНИЕ

Проверь себя!

3) В школьном хоре 6 девочек и 4 мальчика. Сколькими способами можно выбрать из состава школьного хора 2 девочек и 1 мальчика для участия в выступлении окружного хора?

Решение:

Проверь себя!

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

РЕШЕНИЕ

Проверь себя!

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

Решение:

Проверь себя!

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

РЕШЕНИЕ

Проверь себя!

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

Решение:

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

Определение

• Сочетаниями с повторениями из m по n называют соединения, состоящие из n элементов, выбранных из элементов m разных видов, и отличающиеся одно от другого хотя бы одним элементом.

Число сочетаний из m по n

обозначают

79

79

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

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

Историческая справка

Крупнейший индийский математик Бхаскара Акария (1114–1185) также изучал различные виды комбинаторных соединений. Ему принадлежит трактат "Сидханта–Широмани" ("Венец учения"), переписанный в XIII в. на полосках пальмовых листьев. В нём автор дал словесные правила для нахождения и ,указав их применения и поместив многочисленные примеры

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

Задача №1

Сколько наборов из 7 пирожных можно составить, если в распоряжении имеются 4 сорта пирожных?

Решение:

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

Задача №2

Сколько костей находится в обычной игре "домино"?

Решение : Кости домино можно рассматривать как сочетания с повторениями по две из семи цифр множества (0,1,2,3,4,5,6).  Число всех таких сочетаний равно

Проверь себя

  Задача 1.

В буфете Гимназии продаются 5 сортов пирожков : с яблоками, с капустой, картошкой, мясом и грибами. Скольким числом способов можно сделать покупку из 10 пирожков?

РЕШЕНИЕ

86

86

ЗАДАЧА №1

Решение:

Ответ: 1001

Проверь себя

Задача 2.

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

РЕШЕНИЕ

88

88

ЗАДАЧА №2

Решение:

Ответ: 6

Проверь себя

  Задача 3.

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

РЕШЕНИЕ

90

90

ЗАДАЧА №3

Решение: порядок выбора монет неважен, и примерами соединений могут являться {5,5,5,5}, {2,2,2,2}, {5,2,5,5} и т.д. Это задача о числе сочетаний из двух видов монет по четыре с повторениями .

Ответ: 5

Проверь себя

  Задача 4.

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

РЕШЕНИЕ

92

92

ЗАДАЧА №4

Решение: число костей домино можно рассматривать как число сочетаний из 10 чисел по 2 с повторениями.

Ответ: 55

Проверь себя

Задача 5.

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

РЕШЕНИЕ

94

94

ЗАДАЧА №5

Решение:

Ответ: 1716

Используемая литература

• Алгебра и начала математического анализа.11 класс/ Ю.М.Колягин, М.В.Ткачева, Н.Е.Федорова, М.И.Шабунин. – М.:Просвещение, 2011.
• Виленкин Н.Я. Комбинаторика. – М., 1969
• Виленкин Н.Я. Комбинаторика. – МЦМНО, 2010
• ru.wikipedia.org›wiki/ История комбинаторики