"Введение в комбинаторику"

Автор: Жилина Надежда Ивановна
Должность: учитель математики
Учебное заведение: Муниципальное автономное общеобразовательное учреждение лицей №12
Населённый пункт: город Екатеринбург
Наименование материала: мультимедийная презентация
Тема: "Введение в комбинаторику"
Дата публикации: 04.08.2016







Вернуться назад       Перейти в раздел





Текстовая часть публикации


Введение в комбинаторику

Жилина Н.И., учитель математики МАОУ лицея №12 г. Екатеринбурга


Формируемые результаты:
Предметные: формировать умение применять правила суммы и произведения при решении задач. Личностные: формировать представление о математи – ческой науке как сфере математической деятельности, о её значимости для развития цивилизации. Межпредметные: формировать умение строить логи – ческие рассуждения и делать выводы. Планируемые результаты: обучающийся научится при - менять правила суммы и произведения при решении задач. Основные понятия: комбинаторика, правило суммы, правило произведения. Тип урока: изучение нового материала.

Задача 1.

Сколько различных

двузначных чисел имеют в своей

записи только цифры 0,1,2,3?

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

любая из данных цифр, кроме нуля.

Запишем все двузначные числа, у которых на первом месте

стоит цифра 1, на втором цифры 0,1,2,3
. 
10, 11, 12, 13.

Если на первом месте записать цифру 2, то получим числа:

20, 21, 22, 23.

Если на первом месте записать цифру 3, то получим числа:

30, 31, 32, 33.

Ответ:

двенадцать чисел


Задача 1. Сколько различных двузначных

чисел имеют в своей записи только цифры

0,1,2,3?

Эту задачу можно решить с помощью

следующего рассуждения:

В записи данного числа, состоящего из данных

цифр, на первом месте может стоять любая из

трех цифр 1, 2, 3, а на втором – любая из четырех

данных цифр. Поэтому с помощью этих цифр

всего можно записать разных двузначных чисел:
. 12 4 3  

Задача 1. Сколько различных танцевальных пар

(юноша, девушка) можно составить из пяти юношей

и восьми девушек?

Решение: Каждый из пяти юношей

может пригласить любую из восьми

девушек. Поэтому разных

танцевальных пар можно составить
40 8 5  

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

Пусть некоторое множество состоит

из m различных элементов одного

вида и n разных элементов другого

вида. Тогда число различных пар,

состоящих из одного элемента

первого вида и одного элемента

другого вида, равно

m n

Задача 3.
На районную олимпиаду школа должна

направить команду из трех участников: одного из

трех лучших надо выбрать для участия в

олимпиаде по химии, одного из четырех – по

физике, одного из семи – по математике. Сколькими

способами можно составить такую команду?

По правилу умножения для участия в олимпиаде

по химии и физике можно составить пару 3*4 = 12

способами. Для каждой такой пары можно

добавить участника по математике семью

способами. По правилу умножения команду из

трех участников можно составить 12*7 = 3*4*7 =

84 способами.

Ответ: 84 способами.

8


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

котором изучаются вопросы о том, сколько

различных комбинаций, подчиненных тем или

иным условиям, можно составить из заданных

объектов.

Выбором объектов и расположением их в том или ином порядке

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

деятельности, например конструктору, разрабатывающему новую

модель механизма, ученому-агроному, планирующему

распределение с/х культур на нескольких полях, химику,

изучающему строение органических молекул, имеющих данный

атомный состав.

9
Из истории комбинаторики

С комбинаторными задачами люди столкнулись в глубокой

древности. В Древнем Китае увлекались составлением магических

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

Комбинаторные задачи возникли и в связи с такими играми,

как шашки, шахматы, домино, карты, кости и т.д. Комбинаторика

становится наукой лишь в 18 в. – в период, когда возникла теория

вероятности.


Перестановки
Основные виды соединений:

Задача. Антон, Борис и Виктор купили

3 билета на футбол на 1-е, 2-е, 3-е места

первого ряда стадиона. Сколькими

способами мальчики могут занять эти

места?

На первое место может сесть любой из

трех мальчиков, на втрое – любой из двух

оставшихся, и на третье место –последний

мальчик. Применяя последовательно

правило умножения, получаем: 3*2*1 = 6.


1-е

место

2-е

место

3-е

место

А

(Антон)

А

Б

В

А

В

Б

Б

(Борис)

Б

А

В

Б

В

А

В

(Виктор)

В

А

Б

В

Б

А
12
P

3

= 3!

Задача.
Сколькими способами можно

поставить на полке рядом пять разных

книг?

Решение: На первое место можно

поставить любую из пяти книг, на второе

место – любую из четырех оставшихся, на

третье место – любую из трех оставшихся,

на четвертое – любую из двух оставшихся,

на пятое место – последнюю книгу. По

правилу умножения, получаем:

5*4*3*2*1 = 20*6 = 120

Ответ: 120.

Определение:
Перестановками из n разных

элементов называют соединения, которые

состоят из n элементов и отличаются друг от

друга только порядком их расположения

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

обозначают:

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

умножения, можно получить формулу

числа перестановок из n элементов
n P     ! 1 2 ... 3 2 1 1 2 3 ... ) 2 )( 1 ( n n n n n n n P n               

Устный счет

Вычислить:
 ! 2 2  ! 3 6  ! 4 24  ! 5 120  ! 6 720

Задача
.
Чему равно:
  8 5 ) 2 ) 1 P P . 6720 56 120 8 7 6 5 4 3 2 1 ! 8 ) 2 ; 120 20 6 5 4 3 2 1 ! 5 ) 1 8 5                      Ð Ð

Вычислите
:  ! 8 ! 10 90  ! 99 ! 100 100  ! 8 ! 11 720  ! 0 ! 5 120

Упростить:
    . ! 2 1 ! ) 5 ) 4 ; ! 8 ! 4 ! 6 ) 3 ; ! 20 ! 22 ) 2 ; ! 18 ! 19 ) 1 2       m m m P P n n
© Богомолова ОМ, учитель математики МОУ СОШ № 6 г.Шарьи 19 ! 3 ! 2 ! 5  ! 6 8 ! 6 ! 8 ! 7   

Упростить форму записи

следующих выражений:
          12 7 ! 2 ) 6 14 13 ! 12 ) 3 1 ! 1 ) 5 ! 15 16 ) 2 1 ! ) 4 8 ! 7 ) 1 2                   k k k k k k k k

Задача 3. Сколькими способами можно

разместить 12 человек за столом, на

котором поставлены 12 приборов?

Решение: по формуле находим
: . 479001600 12 ... 3 2 1 ! 12 12        P
© Богомолова ОМ, учитель математики МОУ СОШ № 6 г.Шарьи 22 )! 1 ( !  а а ! )! 2 ( а а 

Задача.

Сколько слов можно получить,

переставляя буквы в слове «толпа»?

«перепевы»?

Размещения Виды соединений
Задача.
Сколько различных двузначных

чисел можно записать с помощью

цифр 1, 2, 3, 4 при условии, что в

каждой записи нет одинаковых цифр?

Эту задачу можно решить по правилу

умножения: В записи двузначного числа на

первом месте может стоять любая из данных

четырех цифр, а на втором – любая из трех

оставшихся. По правилу умножения таких

двузначных чисел:

4*3=12.

Задача.
Сколько различных трехзначных

чисел можно записать с помощью

цифр 1, 2, 3, 4 при условии, что в

каждой записи нет одинаковых цифр?

Эту задачу можно решить по правилу

умножения: В записи трехзначного числа на

первом месте может стоять любая из данных

четырех цифр, а на втором – любая из трех

оставшихся, на третьем – любая из двух

оставшихся. По правилу умножения таких

трехзначных чисел:

4*3*2=24.

Определение:
Размещениями из т

элементов по n элементов называются

такие соединения, каждое из которых

содержит n элементов, взятых из данных т

разных элементов, и которые отличаются

друг от друга либо самими элементами,

либо порядком их расположения.

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

элементов обозначают
: n m A

Выведем формулу для вычисления числа размещений из

m

элементов по

n

элементов.

Пусть имеется

m

различных элементов. Тогда число

размещений, состоящих одного элемента, выбранного из

имеющихся m элементов, равно

.

Чтобы составить все размещения из m

элементов по 2, к

каждому из ранее образованных размещений из

m

элементов по 1будем последовательно присоединять по

одному из оставшихся

m-1 элементов. Таких соединений

будет:

Для составления всех размещений из m

элементов по 3, к

каждому из ранее образованных размещений из

m

элементов по 2 присоединим по очереди по одному из

оставшихся

m-2 элементов. Таких соединений будет:

Последовательно применяя правило умножения, для

любого

получаем:
m n          1 ... 2 1        n m m m m A n m m A m  1   1 2   m m A m     2 1 3    m m m A m
Определение:
Размещениями из т элементов по n

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

из которых содержит n элементов, взятых из

данных т разных элементов, и которые

отличаются друг от друга либо самими

элементами, либо порядком их расположения.
                ; ! ! . 1 ... 2 1 . 60 3 4 5 ; 24 2 3 4 ; 12 3 4 . 1 ... 2 1 3 5 3 4 2 4 n m m A m m n m n m A A A A n m m m m À n m n m n m                              
Задача.
Сколькими способами можно

обозначить вершины данного треугольника,

используя буквы A,B,C,D,E,F.

Задача сводится к нахождению числа

размещений из шести элементов по три элемента

в каждом. По формуле находим:
      ; 120 6 5 4 ! 3 ! 6 . 120 1 3 6 1 6 6 3 6 3 6             A À
Задача.
В классе изучают 9 предметов.

Сколькими способами можно составить

расписание на понедельник, если в этот

день может быть 6 разных уроков
    . 60480 2880 57600 2880 20 2880 1 20 2 1440 42 1440 72 42 20 9 8 7 6 5 4 ! 3 ! 9 ! 6 9 ! 9 6 9                            A
Сочетания и их свойства Виды соединений
Задача.
Из пяти шахматистов для участия в

турнире нужно послать двух. Сколькими

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

Из пяти шахматистов можно составить



пар. Но из этих пар надо выбрать только

те, которые отличаются составом

участников, но не их порядком. Таких пар

в 2 раза меньше, т.е.10.
  20 5 4 ! 3 ! 5 ! 2 5 ! 5 2 5       A

При решении задачи из пяти человек были

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

только составом пар.
 Определение:
сочетаниями

из т

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

называются такие соединения,

каждое из которых содержит n

элементов, взятых из данных т

разных элементов, и которые

отличаются друг от друга по

крайней мере одним элементом.

Число
сочетаний
из
m
элементов по
n
элементов обозначают: 
Выведем формулу для подсчета числа сочетаний из т различных

элементов по n элементов в каждом.

Образуем все соединения, содержащие n элементов, выбранных

из данных т разных элементов, без учета порядка их

расположения. Число таких соединений равно

Из каждого полученного соединения перестановками его

элементов можно образовать соединений,

отличающихся друг от друга только порядком расположения

элементов. Тем самым получились размещения из т элементов

по n, число которых равно С другой стороны, по правилу

умножения, число таких соединений равно , откуда
n m С n m Ñ ! n Ð n  n m À n m n n m A Ð Ñ     ; ! ! ! n n m m P A С n n m n m    
Задача.
Сколькими способами из колоды в

36 карт можно выбрать 2 карты?

Решение: Выбор двух карт из колоды без

учета порядка их расположения является

сочетанием. По формуле находим:
  ; 630 35 * 18 ! 2 ! 2 36 ! 36 2 2 36 2 36       P A Ñ

Свойства сочетаний
1 1 1 . 2 ; . 1        n m n m n m n m m n m C C C С С

Простейшие комбинации

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

Размещения

Сочетания

n элементов

n клеток

n элементов

k клеток

n элементов

k клеток

Порядок имеет

значение

Порядок имеет

значение

Порядок не имеет

значения
! n Р n    ! ! k n n А k n     ! ! ! k k n n С k n   

В классе 7 человек успешно занимаются

математикой. Сколькими способами можно

выбрать из них двоих для участия в

математической олимпиаде?

Решение:
.) ( 21 2 1 7 6 ! 2 ! 5 ! 7 2 7 сп С      

Задача

В магазине «Филателия» продается 8

различных наборов марок, посвященных

спортивной тематике. Сколькими

способами можно выбрать из них 3

набора?

Решение:
.) ( 56 3 2 1 6 7 8 ! 2 ! 5 ! 8 2 8 сп С        

В классе учатся 16 мальчиков и 12 девочек.

Для уборки территории требуется выделить

четырех мальчиков и трех девочек.

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

Решение:
.) ( 400400 ! 3 ! 9 ! 12 ! 4 ! 7 ! 11 3 12 4 11 ñï Ñ Ñ       

Задача

Сколькими способами могут

разместиться 4 пассажира в 4-

хместной каюте?

24

4

16


Задача.

Четыре человека обменялись

рукопожатиями. Сколько было

всего рукопожатий?

4

6

8


Задача.

Сколько бригад по 3 человек в

каждой можно составить из 7

человек для отправки на особое

задание?

35

210

24


Задача.

Определить число диагоналей

пятиугольника.

10

5

20


Задача 5
.
Сколькими способами могут

быть распределены золотая и

серебряная медали по итогам

олимпиады, если число команд 15?

9

210

105


Задача 6.
 В школьной столовой на обед приготовили в качестве вторых блюд мясо, котлеты и рыбу. На сладкое — мороженое, фрукты и пирог. Можно выбрать одно второе блюдо и одно блюдо на десерт. Сколько существует различных вариантов обеда?
3

6

9

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

1

6


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

1

6


Проверочная работа

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

Рефлексивный экран;

Выберите любое начало фразы и закон-

чите её

Сегодня я узнал…. Я приобрёл….

Было интересно… Я научился…

Было трудно…. У меня получилось…

Я выполнял …..

задания….. Я смог…..

Я понял что… Я попробую…

Теперь я могу… Меня удивило…

Я почувствовал, Урок дал мне

что…. для жизни…




РЕБЯТА!

Спасибо за урок,

Ответы 1 вариант 2 вариант .) ( 12 ! 2 ! 4 2 4 сп А   .) ( 15 ! 2 ! 4 ! 6 2 6 сп С    .) ( 10 ! 2 ! 3 ! 5 2 5 сп С    .) ( 60 ! 2 ! 5 3 5 сп А  