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

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

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

Цели урока

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.

Перестановки это комбинации, составленные из одних и тех же элементов и отличающиеся порядком их следования. Число всех возможных перестановок элементов обозначается P n, и может быть вычислено по формуле: Формула перестановки: Р n =n! При перестановке число объектов остается неизменными, меняется только их порядок С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно.

Задача 1. В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно? Р 7 =7!=1*2*3*4*5*6*7=5040 Ответ: 5040 Задача 2. Сколькими способами могут разместиться за круглым столом 10 человек? Р 10 =10! = = 1*2*3*4*5*6*7*8*9*10 = Ответ:

Пусть имеется n различных объектов. Будем выбирать из них m объектов и переставлять всеми возможными способами между собой. Получившиеся комбинации называются размещениями из n объектов по m, а их число равно: При размещениях меняется и состав выбранных объектов, и их порядок. Формула размещения:

Задача: Сколькими способами можно распределить три путевки в один санаторий между пятью желающими? Так как путевки предоставлены в один санаторий, то варианты распределения отличаются друг от друга хотя бы одним желающим. Поэтому число способов распределения Ответ: 10 способов.

Задача: В цехе работают 12 человек: 5 женщин и 7 мужчин. Сколькими способами можно сформировать бригаду из 7 человек, чтобы в ней было 3 женщины? Из пяти женщин необходимо выбирать по три, поэтому число способов отбора. Так как требуется отобрать четырех мужчин из семи, то число способов отбора мужчин Ответ: 350

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

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

сочетания.

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

Осёл,

Козёл,

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

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

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

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

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

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

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

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

И споры,

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

знать:

• определения трех важнейших понятий комбинаторики:
• размещения из 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, если цифры в числе должны быть различными?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение.

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

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

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

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

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

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

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

размещение

сочетание

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

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

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

С. 321 № 1062

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

МБОУ «Янишевская основная школа»

Учитель: Зверева Т.И.

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

Антон, Борис и Виктор купили

3 билета на футбол на 1-е, 2-е, 3-е места первого ряда стадиона. Сколькими способами мальчики могут занять эти места?

Решение задачи:

• Может быть такая последовательность:

А Б В А В Б

Может быть и так:

Б В А Б А В

А может быть и так:

В А Б В Б А

Ответ: 6 вариантов

Запомните!!!

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

• Теорема о перестановках элементов конечного множества:

n различных элементов можно расставить по одному на n различных мест ровно n! способами.

Число способов равно числу перестановок

из 3 элементов. По формуле числа перестановок находим, что

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

Пять друзей решили сфотографироваться. Сколькими способами это можно сделать?

Задача:

В 9 классе в среду 6 уроков: математика, литература,

русский язык, английский язык, биология и физкультура. Сколько вариантов расписания можно составить?

Расставляем предметы по порядку:

Всего вариантов

расписания:

1 ∙ 2∙ 3 ∙ 4 ∙5 ∙ 6 = 720

Предмет

Математика

Число вариантов

Литература

Русский язык

Английский язык

Биология

Физкультура

Задача:

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

1) учебники = книга

2) Р6 перестановок книг

3) Р6=6!

4) Р4 перестановки учебников

5) Р4=4!

6) Р 6 ∙ Р4

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

1. Весной мама покупает ребенку много фруктов. Она купила банан, яблоко, апельсин, лимон, грушу и киви. Найдите число возможных вариантов съедания фруктов.

2 . Одиннадцать футболистов строятся перед началом матча. Первым становится капитан, вторым –

вратарь, а остальные – случайным образом.

Сколько существует способов построения?

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

До новых встреч

с комбинаторными задачами