Понятие науки « Комбинаторика»

1.

2. Понятие науки « Комбинаторика»

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

3. Практическая значимость науки

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

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

• Правило
• Решение задач
• Подбор задач по теме

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

Пусть имеется n элементов и
требуется выбрать один за другим
некоторые k элементов. Если
первый элемент можно выбрать n1
способами, после чего второй
элемент можно выбрать из
оставшихся элементов n2
способами, затем третий элемент –
n3 способами и т.д., то число
способов, которыми могут быть
выбраны все k элементов, равно
произведению n1*n2*n3*…*nk.

6. Задачи на правило умножения

1. Имеется 6 перчаток различных размеров. Сколькими
способами можно выбрать из них одну перчатку на
левую руку и одну на правую руку так, чтобы эти
перчатки были различных размеров?
2. Сколькими способами могут быть распределены
золотая и серебряная медали по итогам олимпиады,
если число команд 15?
3. Гера, Арина и Афродита попросили
Париса не только назвать самую красивую
из них, но и указать, кто на втором и
третьем местах. Сколько есть
вариантов ответов? (показать решение)

7. Решение задач на комбинаторное правило умножения.

1. Перчатка на левую руку может быть выбрана 6
способами. После того, как она выбрана, перчатку на
правую руку можно выбрать лишь 5 способами
(размеры перчаток должны быть разными), поэтому
всего имеется 6*5=30 способов.
2. На золотую медаль претендует 15 команд, на
серебряную- 14 команд (одна уже получит золотую
медаль). По правилу имеем : 15*14=210 способов.
3. На первое место Парис может выбрать тремя
способами, на второе – двумя (одна претендентка
уже находится на первом месте ), на третье – одним
способом. Поэтому имеем : 3*2*1=6 способов.

8. Задачи по теме «Комбинаторное правило умножения»

1.
2.
3.
4.
5.
6.
7.
У Иры пять подруг :Вера, Зоя, Марина, Полина и Света. Она решила
двух из них пригласить в кино. Сколько таких вариантов?
В шахматном турнире участвуют 9 человек. Каждый из них сыграл с
каждым по одной партии. Сколько всего партий сыграно?
В соревнованиях по футболу участвовало 12 команд. Каждая
команда провела с каждой из остальных по одной игре на своём
поле и на поле соперника. Сколько всего игр было сыграно?
При встрече 8 человек обменялись рукопожатиями. Сколько всего
было сделано рукопожатий?
Из села Дятлово в село Матвеевское ведут три дороги, а из села
Матвеевское в село Першино –четыре дороги. Сколькими способами
можно попасть из Дятлова в Першино через Матвеевское?
В кафе имеется три первых блюда, пять вторых и два третьих.
Сколькими способами посетитель кафе может выбрать обед,
состоящий из первого, второго и третьего блюд?
Петр решил пойти на новогодний карнавал в костюме мушкетёра. В
ателье проката ему предложили на выбор различные по фасону и
цвету предметы: пять видов брюк, шесть комзолов, три шляпы, две
пары сапог. Сколько различных карнавальных костюмов можно
составить их этих предметов?

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

Комбинации из n-элементов, отличающихся друг от
друга только порядком расположения в них
элементов, называются перестановками из n
элементов.
Перестановки из n элементов обозначают Pn и
вычисляют по формуле: Pn=n!
n!=1*2*3*4*…*n (n факториал)
Свойство: 0!=1
Задача: Сколькими способами могут разместиться 5
пассажиров в пятиместной каюте?
Решение: P5=5!=1*2*3*4*5=120

10. Решение задач по теме «Перестановки»

1.Курьер должен разнести пакеты в 7 различных
учреждений. Сколько маршрутов он может выбрать?
2.Сколькими способами 9 человек могут встать в очередь в
театральную кассу?
3.Ольга помнит, что телефон подруги оканчивается цифрами
5,7,8, но забыла, в каком порядке эти цифры следуют.
Укажите наибольшее число вариантов, которые ей
придётся перебрать, чтобы дозвониться подруге.
4.Сколько шестизначных чисел, в записи которых каждая
цифра используется только один раз, можно составить из
цифр: а)1,2,5,6,7,8; б)0,2,5,6,7,8?
5.Сколькими способами можно расставить на полке 12 книг,
из которых 5 книг – это сборники стихов, так чтобы
сборники стихов стояли рядом в произвольном порядке?

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

• Размещением из n элементов по m (m<=n)
называется любое множество, состоящее
из m элементов, взятых в определённом
порядке из данных n элементов.
• Число размещений из n элементов по m
обозначаются Аnm(читается: «А из n по m»)

12.

Anm =n(n-1)(n-2)*…*(n-(m-1)),
где n-число всех имеющихся элементов, m- число
элементов в каждой комбинации, т.е. число всех
возможных размещений из n по m равно
произведению m последних целых чисел, из
которых большее n.
Например: в звене 12 человек, требуется выбрать
звеньевого, санитара и командира. Сколькими
способами это можно сделать?
Решение: A123 = 12х11х10 = 1320
Или Anm = n!/ ( n – m )!
A123 =12!/(12-3)!=12!/9!= 12х11х10 = 1320

13. Подбор задач по теме «Размещения»

1
2
3
4
5
6
7*
Из 30 участников собрания надо выбрать председателя и секретаря.
Сколькими способами это можно сделать?
На станции 7 запасных путей. Сколькими способами можно расставить на
них 4 поезда?
На странице альбома 6 свободных мест для фотографий. Сколькими
способами можно вложить в свободные места: а) 2 фотографии; б) 4
фотографии; в) 6 фотографий?
Сколько четырёхзначных чисел, в которых нет одинаковых цифр, можно
составить из цифр: а) 1, 3, 5, 7, 9,; б) 0, 2. 4, 6, 8?
Сколько существует семизначных телефонных номеров, в которых все
цифры различные и первая цифра отлична от нуля?
Сколько можно составить из цифр 1, 2, 3, 4, 5, (без их повторения)
различных трёхзначных чисел, которые являются: а) чётными б) кратными
5?
На плоскости отметили несколько точек, никакие три из них не лежат на
одной прямой. Через каждые две точки провели прямую. Сколько точек
было отмечено, если всего было проведено 28 прямых?

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

Сочетанием из n элементов по m
называется любое множество,
составленное из m элементов,
выбранных из данных n элементов (не
имеет значения, в каком порядке
указаны элементы).
Число сочетаний из n элементов по m
обозначают Cmn (читается: «С из n по
m»).

15.

Пусть имеется множество, содержащее n элементов, и из его
элементов составлены все возможные сочетания по m
элементов. Число таких сочетаний равно Cmn В каждом
сочетании можно выполнить Pm перестановок. В результате мы
получим все размещения, которые можно составить из n
элементов по m. Их число равно Anm .
Значит Cmn = (Anm)/Pm
Пользуясь тем, что Anm =n!/(n-m)!, а Pm =m!
Находим, что Cmn =n!/(m!*(n-m)!)
Мы получили формулу для вычисления числа сочетаний.
Задача: На тренировке занимаются 10 баскетболистов.
Сколько различных стартовых пятёрок может
образовать тренер?
Решение : т.к. при составлении стартовой пятёрки,
тренера интересует только состав, то достаточно
определить число сочетаний из 10 по 5 элементов.
С10 5 = ( 10х9х8х7х6)/(1х2х3х4х5) = 252

16. Подбор задач по теме «Сочетания»

1
2
3
4
5
6*
7*
В классе 7 человек успешно занимаются математикой. Сколькими
способами можно выбрать из них двоих для участия в олимпиаде?
Учащимся дали список из 10 книг, которые рекомендуется прочитать
во время каникул. Сколькими способами ученик может выбрать из
них 6 книг?
На плоскости отмечено 8 точек, никакие три из них не лежат на одной
прямой. Сколько прямых можно провести через эти точки?
Из лаборатории, в которой работают заведующий и 10 сотрудников,
надо отправить 5 человек в командировку. Сколькими способами это
можно сделать, если а)заведующий лабораторией должен ехать в
командировку; б) заведующий лабораторией должен остаться?
Номер машины в некотором городе составляют из двух различных
букв, взятых из набора М, Н, К, Т, С, и трёх различных цифр. Сколько
машин можно обеспечить такими номерами?
Максим подсчитал, что существует 378 способов выбора из их класса
двух дежурных. Сколько учащихся в этом классе?
На полке стоит 12 книг: англо-русский словарь и 11художественных
произведений на английском языке. Сколькими способами читатель
может выбрать 3 книги, если: а) словарь нужен ему обязательно;
б)словарь ему не нужен?

17. Урок №5-6 : Практикум по решению комбинаторных задач

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

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

Что такое комбинаторика?
В чем состоит комбинаторное правило
умножения?
3 Что такое перестановки?
4 Записать формулу для нахождения числа
перестановок?
5 Что такое факториал?
6 Что такое размещения?
7 Записать формулу для нахождения числа
размещений?
8 Что такое сочетания?
9 Записать формулу для нахождения числа
сочетаний?
10 В чём различие между перестановками,
размещениями и сочетаниями?
1
2

19. Подбор комбинаторных задач

А№1 Восьмиклассники Анна, Борис, Виктор и Галина
побежали на перемене к теннисному столу, за
которым уже шла игра. Сколькими способами
подбежавшие к столу восьмиклассники могут занять
очередь для игры в настольный теннис? (решение)
№2 Сколькими способами можно расставить 8
участниц финального забега на восьми беговых
дорожках? (решение)
№3 Учащиеся 2 класса изучают 9 предметов.
Сколькими способами можно составить расписание
на один день, чтобы в нём было 4 различных
предмета? (решение)
№4 Из набора, состоящего из 15 красок, надо выбрать 3
краски для окрашивания шкатулки. Сколькими
способами можно сделать этот выбор? (решение)
Далее
Устал - отдохни

20. Решение:

№1 Первым в очередь мог встать любой из четырёх
ребят, вторым – любой из оставшихся трёх, третьим
– любой из оставшихся двух и четвёртым последний. По правилу произведения :4*3*2*1=24
способа.
№2 Число способов равно числу перестановок из 8
элементов : Р8=8!=1*2*3*4*5*6*7*8=40 320
№3 Любое расписание на один день, составленное из 4
различных предметов, отличается от другого либо
набором предметов, либо порядком их следования.
Имеем размещения из 9 по 4: А94=9!/5!=6*7*8*9=3024
№4 Каждый набор трёх красок отличается от другого
хотя бы одной краской. Имеем сочетания из 15 по 3 :
С153=15!/3!/12!=13*14*15/(1*2*3)=455.

21. В №1 В шахматном кружке занимаются 16 человек. Сколькими способами тренер может выбрать из них для предстоящего турнира : а)

команду из
четырёх человек;
б) команду из четырёх человек, указав при этом, кто из членов команды
будет играть на первой, второй, третьей и четвёртой досках?
№2 У Антона 6 друзей. Он может пригласить в гости одного или несколько из
них. Определите общее число возможных вариантов.
№3 В 9 «а» классе учатся 25 учащихся, в 9 «б» - 20 учащихся, а в 9 «в» - 18
учащихся. Для работы на пришкольном участке надо выделить трёх
учащихся из 9 «а», двух -из 9 «б» и одного – из 9 «в». Сколько существует
способов выбора учащихся для работы на пришкольном участке?
С №1 Пять мальчиков и четыре девочки хотят сесть на девятиместную
скамейку так, чтобы каждая девочка сидела между двумя мальчиками.
Сколькими способами они могут это сделать?
№2 Из 12 солдат, в число которых входят Иванов и Петров, надо отправить в
наряд трёх человек. Сколькими способами это можно сделать, если: а)
Иванов и Петров должны пойти в наряд обязательно; б) Иванов и Петров
должны остаться; в)Иванов
должен пойти в наряд, а Петров –остаться?
(Ответы)
Устал - отдохни

22. Ответы:

В №1 а) 1820 способов;
б) 43 680 способов.
№2 63 способа,
указание:С61+С62+С63+С64+С65+С66.
№3 7 866 000 способов,указание:С253*С202*С181
.
С №1 2880 способов, указание:Р5*Р4 .
№2 а)10 способов; б)120 способов; в)45
способов.