География

Урок по теме перестановки сочетания презентация. Презентация "Дискретный анализ. Комбинаторика. Перестановки" по информатике – проект, доклад. Расставляем предметы по порядку

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

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

Цели урока

1. Дать определение понятия «перестановки»

2. Вывести формулу перестановок

3. Познакомиться с понятием «факториал»

4. Научиться применять формулу перестановок в простейших случаях

5. Использовать полученные знания в новых ситуациях

План урока

1. Библиографическая справка

2. Введение понятия перестановки и вывод формулы

3. Решение задач на применение формулы перестановок

4. Самостоятельная работа

5. Итог урока

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

Библиографическая справка

Термин « перестановки »

впервые употребил

швейцарский математик,

о дин из основателей

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

математического анализа Якоб Бернулли

(27.12.1654 - 16.8.1705)

в книге «Искусство предположений»

Определение

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

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

Формула перестановок

4∙3∙2∙1 = 24

1∙2∙3∙4∙5=120

1∙2∙3∙4∙5 ∙ …∙ n

Произведение подряд идущих первых n натуральных чисел обозначают n ! и читают «эн факториал»

« factor » - множитель

«эн факториал» - состоящий из n множителей

Факториал

Формула n ! = 1∙2∙3∙4∙ … ∙ ( n-1 )∙ n

Например

3! = 1∙2∙3 = 6

Запомни 0! = 1 и 1! = 1

Удобная формула n ! = ( n-1 )!∙ n

Например: 6! = 5!∙6 = 120 ∙ 6 = 720

Правильно ли записано формула для вычисления перестановок

Р 3 = 3! = 3∙2∙1
Р 4 = 4! = 1∙2∙4∙5
Р 5 = 5! = 1∙2∙3∙4∙5
Р n = n ! = 1∙2∙3∙…∙ n
Р 4 = 4! = 7∙8∙9∙10

Мозговой штурм

1. Вычислите:

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

Р 3 = 3! = 1∙2∙3 = 6

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

Государственная символика некоторых стран

Флаг России

Флаг Нидерландов Флаг Югославии

Применение полученных знаний в новой ситуации

1. Вычислить:

7 = 9!∙6! 7!∙8! Ответ: 9!∙6! 7!∙8! " width="640"

Что больше: 9!∙6! или 7!∙8! ?

Так как 9! = 8!∙ 9, то 9!∙6! = 8!∙ 9 ∙ 6!

Так как 7! = 6! ∙ 7, то 7!∙8! = 6! ∙ 7 ∙ 8!

9 7 = 9!∙6! 7!∙8!

Ответ: 9!∙6! 7!∙8!

Самостоятельная работа

I вариант

Сколькими способами можно составить расписание одного учебного дня из 5 различных уроков?
2. Аня, Вера и Таня купили билеты в кинотеатр на 1, 2 и 3-е места первого ряда. Сколькими способами девочки могут занять эти три места?

II вариант

1. Сколькими способами можно расставить 4 различные книги на книжной полке?

2. Сколькими способами могут стать в очередь в билетную кассу 3 человека?

Проверка

I вариант

II вариант

Ответ: 120 вариантов
Ответ: 6 способов

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

Синквейн

1 строка – одно существительное, выражающее главную тему.

2 строка – два прилагательных, выражающих главную мысль.

3 строка – три глагола, описывающие действия в рамках темы.

4 строка – фраза, несущая определенный смысл.

5 строка – заключение в форме существительного (ассоциация с первым словом).

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

Пункт 6.4 , учить формулу перестановок

I уровень: №611, №612,

II уровень: №616, №621.

КОМБИНАТОРИКА

Цели урока:

Узнать, что изучает комбинаторика
Узнать,как возникла комбинаторика
Изучить формулы комбинаторики и научиться применять их при решении задач

Рождение комбинаторики как раздела математики связано с трудами Блеза Паскаля и Пьера Ферма по теории азартных игр.

Блез Паскаль

Пьер Ферма

Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

Г.В. Лейбниц

Л. Эйлер.

Я. Бернулли

Лемма. Пусть в множестве A m элементов, а в множестве B - n элементов. Тогда число всех различных пар (a,b), где a\in A,b\in B будет равно mn. Доказательство. Действительно, с одним элементом из множества A мы можем составить n таких различных пар, а всего в множестве A m элементов.

Размещения, перестановки, сочетания Пусть у нас есть множество из трех элементов a,b,c. Какими способами мы можем выбрать из этих элементов два? ab,ac,bc,ba,ca,cb.

Перестановки Будем переставлять их всеми возможными способами (число объектов остается неизменными, меняется только их порядок). Получившиеся комбинации называются перестановками, а их число равно Pn = n! =1 · 2 · 3 · ... · ( n-1)·n

Символ n! называется факториалом и обозначает произведение всех целых чисел от 1 до n. По определению, считают, что 0!=1 1!=1 Пример всех перестановок из n=3 объектов (различных фигур) - на картинке. Согласно формуле, их должно быть ровно P3=3!=1⋅2⋅3=6 , так и получается.

С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно. Например, число перестановок из 10 предметов - уже 3628800 (больше 3 миллионов!).

Размещения Пусть имеется n различных объектов. Будем выбирать из них m объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из n объектов по m, а их число равно Aⁿm =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

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

Сочетания Пусть имеется n различных объектов. Будем выбирать из них m объектов всевозможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из n объектов по m, а их число равно Cmn=n!(n−m)!⋅m!

Пример всех сочетаний из n=3объектов (различных фигур) по m=2- на картинке снизу. Согласно формуле, их должно быть ровно C23=3!(3−2)!⋅2!:3!=3. Ясно, что сочетаний всегда меньше чем размещений (так как при размещениях порядок важен, а для сочетаний - нет), причем именно в m! раз, то есть верна формула связи: Amn=Cmn⋅Pm.

Способ 1 . В одной игре участвуют 2 человека, следовательно, нужно вычислить, сколькими способами можно отобрать 2-х человек из 15, причем порядок в таких парах не важен. Воспользуемся формулой для нахождения числа сочетаний (выборок, отличающихся только составом) из n различных элементов по m элементов

n!= 1⋅ 2 ⋅3⋅...⋅ n , при n=2, m=13.

Способ 2. Первый игрок сыграл 14 партий (с2-м, 3-м, 4-м, и так до 15-го), 2- ой игрок сыграл 13 партий (3-м, 4-м, и т.д. до 15-го, исключаем то, что с первым партия уже была), 3-ий игрок − 12 партий, 4-ый − 11 партий, 5 – 10 партий, 6 – 9 партий, 7 – 8 партий, 8 – 7 партий,

а 15-ый уже играл со всеми.

Итого: 14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 партий

ОТВЕТ. 105 партий.

Учитель математики Аксёнова Светлана Валерьевна

Бугровская СОШ Всеволожского района Ленинградской области

Презентация «Перестановки» представляет учебный материал для школьного урока по данной теме. Презентация содержит определение перестановок, наглядные примеры для понимания смысла данной операции, описание математического аппарата для решения задач с перестановками, примеры решения задач. Задача презентации - в удобной, понятной форме донести до учеников учебный материал, способствовать лучшему его пониманию и запоминанию.

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

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

Далее демонстрируется пример перестановок на цветных карандашах, которые можно разместить в различном порядке. Для этого карандаши подписываются первой буквой названия их цвета: С, К, Ж. При помощи анимированного представления наглядно демонстрируются варианты размещения данных карандашей по порядку. На одном слайде первыми размещаются синие карандаши, а рядом с ними два варианта размещения - красный и желтый, желтый и красный. На следующем слайде продемонстрированы варианты размещения карандашей после красного - синий и желтый, желтый и синий. Последние возможные варианты - после желтого красный и синий, синий и красный. После наглядной демонстрации выполненные операции подписываются как перестановки из трех элементов. Более точное определение перестановки из трех элементов дается на отдельном слайде 7. В рамке для запоминания выделен текст, что каждое расположение данных элементов в определенном порядке будет называться перестановкой из трех элементов.

На слайде 8 продемонстрировано обозначение перестановок из n элементов - P n . Указано, что перестановки из трех элементов были подробно рассмотрены на примере карандашей, при этом очевидно, что таких перестановок будет 6. На слайде отмечена математическая запись количества перестановок: P 3 =6. Далее на экране отмечается, что для нахождения количества перестановок из трех элементов существует комбинаторное правило умножения.

На следующем слайде процедура перестановок раскладывается на этапы, чтобы получить правило для нахождения количества перестановок. Указано, что для подсчета необходимо на первое место ставить любой из трех элементов. Для него есть две возможности выбрать второй элемент. Для выбора третьего элемента остается единственная возможность. Это означает, что количество перестановок из 3 элементов будет находиться перемножением 3.2.1=6. Получаем общее число возможных вариантов перестановок. Аналогично процессу поиска вариантов перестановок рассматривается вариативность для n элементов.

Пусть есть некоторое множество n элементов. Для него на второе место помещается один из n-1 элементов, на третье место соответственно помещается один из n-2 элементов и т.д. Таким образом, можно вывести общее правило для поиска числа перестановок из n элементов: P n =n(n-1)(n-2).….3.2.1.

На слайде 11 на экран выведена формула P n в виде P n =1.2.3.….(n-2)(n-1)n. Таким образом вводится понятие факториала, обозначение которого продемонстрировано ниже формулы: n!. Рассмотрены примеры нахождения факториала от некоторого числа: 3!=1.2.3=6, а также 6!=1.2.3.4.5.6=720. Также указано, что 1!=1. Текст общего правила нахождение количества перестановок как n факториала расположен внизу слайда.

Далее предлагается рассмотреть несколько задач на нахождение числа перестановок. На слайде 12 предлагается к решению задача на нахождение количества способов разложения семи шаров по семи ячейкам. Указано, что способом решения является вычисление числа перестановок из 7 элементов: P 7 =7!=5040.

На слайде 13 рассматривается решение задачи на нахождение количества четырехзначных чисел, которые составлены из 0,1,2,3, при этом цифры в одном числе не повторяются. Решение предусмотрено в два этапа - сначала находится число всех перестановок из 4 элементов, а затем из них вычитается число перестановок, в которых числа с 0 впереди, так числа, начинающиеся с нуля, не будут четырехзначными. Таким образом, решение сводится к вычислению P 4 -P 3 =4!-3!=18. То есть вариантов образования таких чисел - 18.

На последнем слайде рассматривается решение задачи, в которой предлагается найти количество способов, которыми можно расставить 9 тарелок, 4 из которых - красные, так, чтобы красные располагались рядом. Основная трудность в решении данной задачи - понять, что красные тарелки в данных перестановках необходимо принимать за одну. Таким образом, решение сводится к нахождению произведения P 6 .P 4 =6!.4!=17280.

Презентация «Перестановки» предназначена для наглядного сопровождения объяснения учителя по теме «Перестановки». Подробное понятное представление учебного материала может быть также полезно при дистанционном обучении, а рассмотренные при этом задачи помогут ученику разобраться с решением самостоятельно.

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

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

сочетания.

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

Осёл,

Козёл,

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

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

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

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

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

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

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

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

И споры,

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

знать:

определения трех важнейших понятий комбинаторики:
размещения из 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 автобусами. Сколькими способами можно добраться из города А в город В?

Решение

Пример № 2

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

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

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

Решение .

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

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

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

Пример № 3

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

Решение

Пример № 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

Чему равно

а)Р 5 ;

б) Р 3.

Пример № 8

Упростите

б) 12! · 13 ·14

в) κ ! · (κ + 1)

Пример № 9

Сколькими способами можно расставить 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 94:

Пример № 10

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

Решение.

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

СОЧЕТАНИЯ

Определение. Сочетанием без повторений из 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, если цифры в числе должны быть различными?

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

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

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

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

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

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

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

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

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

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

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

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