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

Презентация на тему:

«Основы комбинаторики.

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

сочетания. Правило произведения».

Выполнила: учитель высшей квалификационной категории

Барышникова Е.М.

г. Касимов, 2020 г.

Проказница Мартышка

Осёл,

Козёл,

Да косолапый Мишка

Затеяли играть квартет

…

Стой, братцы стой! –

Кричит Мартышка, - погодите!

Как музыке идти?

Ведь вы не так сидите…

И так, и этак пересаживались – опять музыка на лад не идет.

Вот пуще прежнего пошли у них разборы

И споры,

Кому и как сидеть…

знать:

• определения трех важнейших понятий комбинаторики:
• размещения из n элементов по m;
• сочетания из n элементов по m;
• перестановки из n элементов;
• основные комбинаторные формулы

уметь:

• отличать задачи на «перестановки», «сочетания», «размещения» друг от друга;
• применять основные комбинаторные формулы при решении простейших комбинаторных задач.

множество

Множество характеризуется объединением некоторых однородных объектов в одно целое.

Объекты, образующие множество, называются элементами множества.

Множество будем записывать, располагая его элементы в фигурных скобка { a ,  b ,  c , … ,  e ,  f }.

Во множестве порядок элементов роли не играет, так { a ,  b } = { b ,  a }.

Множество, не содержащее ни одного элемента, называется  пустым множеством   и обозначается символом ø.

множество

Если каждый элемент множества А является элементом множества В, то говорят, что множество А является подмножеством множества В.

Обозначается

Пример :

В

А

Множество { a ,  b } является подмножеством множества { a ,  b ,  c , … ,  e ,  f }.

Задача

Перечислите возможные варианты подмножества множества { 3 ,  4 ,  5 , 7,  9 }.

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

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

ПРАВИЛО СУММИРОВАНИЯ

Если два взаимоисключающие действия могут быть выполнены в соответствии   k и m способами, тогда какое-то одно из этих действий можно выполнить   k + m способами.

Пример №1

Из города А в город В можно добраться 12 поездами, 3 самолетами, 23 автобусами. Сколькими способами можно добраться из города А в город В?

Решение

N=12+13+23=38

Пример № 2

В ящике имеется n разноцветных шариков. Произвольным образом вынимаем один шарик. Сколькими способами это можно сделать?

Решение . Конечно,  n  способами.

Теперь эти n шариков распределены по двум ящикам: В первом  m  шариков, во втором  k . Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами это можно сделать?

Решение . 

Из первого ящика шарик можно вытянуть  m  различными способами, из второго  k различными способами, всего   N =  m  +  k  способами.

ПРАВИЛО ПРОИЗВЕДЕНИЯ

Пусть две выполняемые одно за другим действия могут быть осуществлены в соответствии    k и m способами Тогда обе они могут быть выполнены  k ∙ m способами .

Пример № 3

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

Решение

N=8∙7∙6=336

Пример № 4

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

Решение.   Поскольку число двузначное, то число десятков ( m ) может принимать одно из девяти значений: 1,2,3,4,5,6,7,8,9. Число единиц ( k ) может принимать те же значения и может, кроме того быть равным нулю. Отсюда следует, что  m  = 9, а  k = 10. Всего получим двузначных чисел 

N =  m  · k  = 9·10 =90.

Пример № 5

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

Решение.   По правилу умножения двух девушек можно выбрать 14 ·13 = 182 способами, а двух юношей 6·5 = 30 способами. Следует выбрать двух студентов одного пола: двух студентов или студенток. Согласно правилу сложения таких способов выбора будет

N =182 + 30 = 212.

Типы соединений

Множества элементов называются  соединениями .

Различают три типа соединений:

• перестановки из  n  элементов;
• размещения из  n  элементов по  m ;
• сочетания из  n  элементов по  m  ( m  n ).

ПЕРЕСТАНОВКИ

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

Иными словами, это такое множество, для которого указано, какой элемент находится на первом месте, какой – на втором, какой- на третьем, …, какой – на n-м месте.

Перестановки   – это такие соединения по   n   элементам из данных элементов, которые отличаются одно от другого порядком элементов.

Число перестановок из n элементов обозначают Р n .

Р n  =  n  · ( n  - 1) · ( n  – 2) · … · 2 · 1 =  n !

ФАКТОРИАЛ

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

Пусть   n   - натуральное число. Через   n ! (читается "эн факториал") обозначается число, равное произведению всех натуральных чисел 1 от до   n :

n ! = 1 · 2 · 3 · ... ·  n .

В случае, если   n   = 0, по определению полагается: 0! = 1.

Пример № 6

Найдем значения следующих выражений: 1! 2! 3!

7!

Пример № 7

Чему равно

а) Р 5  ;

б)  Р 3.

Пример № 8

Упростите

а) 7! · 8

б) 12! · 13 ·14

в)  κ ! · ( κ  + 1)

Пример № 9

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

Решение.  

n  =8

Р 8 =8! = 8·7·6·5 · 4 · 3 · 2 ·1 =40320

РАЗМЕЩЕНИЯ

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

Число размещений из  m  элементов по  n  обозначают: 

вычисляют по формуле:

Пример № 9

Учащиеся 11-го класса изучают 9 учебных предметов. В расписании учебных занятий на один день можно поставить 4 различных предмета. Сколько существует различных способов составления расписания на один день?

Решение.  

Имеем 9-элементное множество, элементы которого учебные предметы. При составлении расписания мы будем выбирать 4-элементное подмножество (уроков) и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре ( m=9, n=4) то есть  A 9 4 :

Пример № 10

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

Решение.  

Имеем 24-элементное множество, элементы которого ученики класса. При выборах старосты и помощника старосты мы будем выбирать 2-элементное подмножество (ученика) и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре ( m=24 , n=2 ) , то есть  A 24 2 :

СОЧЕТАНИЯ

Определение. Сочетанием без повторений из n элементов по m -называется любое m элементное подмножество n -элементного множества

Число сочетаний из n элементов по m обозначают 

и вычисляют по формуле:

Пример № 11

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

Решение.  

n =24, m =2

Учитывается ли порядок следования элементов в соединении?

Д А

НЕТ

СОЧЕТАНИЯ

Все ли элементы входят в соединение?

Д А

НЕТ

РАЗМЕЩЕНИЯ

ПЕРЕСТАНОВКИ

Р n  =   n !

Определить к какому типу относится соединений относится задача.

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

Учитывается ли порядок следования элементов в соединении?

( да)

Все ли элементы входят в соединение?

( да)

Вывод: перестановка

2. В 9«Б» классе 12 учащихся. Сколькими способами можно сформировать команду из 4 человек для участия в математической олимпиаде?

Учитывается ли порядок следования элементов в соединении?

(нет)

Все ли элементы входят в соединение?

(на этот вопрос ответ не нужен)

Вывод: сочетания

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

Учитывается ли порядок следования элементов в соединении?

( да)

Все ли элементы входят в соединение?

(нет)

Вывод: размещение

Проказница Мартышка

Осёл,

Козёл,

Да косолапый Мишка

Затеяли играть квартет

…

Стой, братцы стой! –

Кричит Мартышка, - погодите!

Как музыке идти?

Ведь вы не так сидите…

И так, и этак пересаживались – опять музыка на лад не идет.

Вот пуще прежнего пошли у них разборы

И споры,

Кому и как сидеть…

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

Решение.  

Учитывается ли порядок следования элементов в соединении?

( да)

Все ли элементы входят в соединение?

(да)

Вывод: перестановка

Р n  =   n ! = n  · ( n  - 1) · ( n  – 2) · … · 2 · 1

n =4

Р 4  =  4! = 4 · 3 · 2 ·1=24

Кто автор высказывания?

«Рано или поздно всякая правильная математическая идея находит применение в том или ином деле»?

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

размещение

Е

12

1

А

Е

5040

720

К

М

Р

В

120

9

Ы

Н

О

132

Л

И

Й

Е

С

Ч

56

сочетание

21

6720

Результаты решения задач

1

2

3

4

5

6

7

Е

Й

С

К

Е

Л

А

8

9

10

11

12

13

14

15

16

17

А

Ч

И

О

И

К

Е

Н

В

Л

18

19

20

21

22

23

О

Л

В

Ы

Р

К

ДОМАШНЕЕ ЗАДАНИЕ

Выучить конспект и формулы.