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

Министерство образования Нижегородской области

ГБПОУ «Уренский индустриально – энергетический техникум»

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

Вычислите:

Правильный ответ:

Вычислите:

60

Правильный ответ:

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

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

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

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

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

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

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

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

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

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

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

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

Г.В.Лейбниц

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

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

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

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

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

• Размещения

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

• Сочетания

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

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

Формула:

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

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

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

Размещения

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

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

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

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

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

Сочетания

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

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

Пример

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

Ответ : P 8 = 8! =40320

Проверь себя

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 способа .

Пример

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

Сколько анаграмм можно составить из слова «макака»?

Решение.

Всего в слове «МАКАКА» 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

k 1 ! k 2 ! … k n !

1 ! 3 ! 2 !

Проверь себя

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 в.  индийский математик  Бхаскара  в своём основном труде «Лилавати» подробно исследовал задачи с перестановками и сочетаниями, включая перестановки с повторениями.

Пример

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

Решение:

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

40!

A = =38*39*40=59280

3

37!

40

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

7!

А = =840

4

3!

7

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

10!

А = =720

3

7!

10

Проверь себя

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

РЕШЕНИЕ

Проверь себя

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

Решение.

7!

А = =840

4

3!

7

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

В библиотеку, в которой есть много одинаковых учебников по десяти предметам , пришло 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 способов.

Задача 5

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

І способ

Переберем все возможные варианты

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

І І способ

Воспользуемся правилом умножения

Для каждой лампочки возможны два исхода, а лампочек три, значит:

Ответ:8.

Выберите правило

№ 1. Из города А а город В ведут 5 дорог, а из города В в город С – 3 дороги. Сколькими способами можно проехать из города А в город С?

№ 2. На книжной полке стоят 3 книги по алгебре, 4 по геометрии и 5 по литературе. Сколькими способами можно взять с полки одну книгу по математике?

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

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

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

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

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