Алгебра: Перестановки и факториалы

Вид урока: Бинарный (алгебра – информатика)

Учителя: ,

Тема:

Алгебра: Перестановки и факториалы.

Информатика и ИКТ: Способы  вычисления факториалов в среде программирования Турбо Паскаль.

Оборудование:

Компьютерная сеть из 14 компьютеров, мультимедийный проектор, экран, маркерная доска

Цели и задачи:

Повторить понятие перестановки и правила вычисления числа перестановок Повторить понятие факториала и рассмотреть способы его вычисления Рассмотреть типичные задачи и способы их решения

Ход урока.

История возникновения комбинаторики Понятие факториала и перестановки.

Рассмотрим задачу, которая хорошо известна Вам как гуманитарному классу, хотя возможно Вы и не догадывались, что перед Вами именно задача:  (Иллюстрируем презентацией)

«Проказница Мартышка, Осел, Козел, Да косолапый Мишка Затеяли сыграть Квартет. Достали нот, баса, альта, две скрипки И сели на лужок под липки, - Пленять своим свет. Ударили в смычки, дерут, а толку нет. "Стой, братцы, стой! - кричит Мартышка. - Погодите! Как музыке идти? Ведь вы не так сидите. Ты с басом, Мишенька, садись против альта, Я, прима, сяду против вторы; Тогда пойдет уж музыка не та: У нас запляшут лес и горы!" Расселись, начали Квартет; Он все-таки на лад нейдет. "Постойте ж, я сыскал секрет! - Кричит Осел, - мы, верно, уж поладим, Коль рядом сядем". Послушались Осла: уселись чинно в ряд; А все-таки Квартет нейдет на лад. Вот пуще прежнего пошли у них разборы И споры, Кому и как сидеть. Случилось Соловью на шум их прилететь. Тут с просьбой все к нему, чтоб их решить сомненье. "Пожалуй, - говорят, - возьми на час терпенье, Чтобы Квартет в порядок наш привесть: И ноты есть у нас, и инструменты есть, Скажи лишь, как нам сесть!" "Чтоб музыкантом быть, так надобно уменье И уши ваших понежней, - Им отвечает Соловей, - А вы, друзья, как ни садитесь, Всё в музыканты не годитесь".

».

Итак, данной группе пришлось решать не такой уж простой вопрос: «Как расположить 4 объекта по 4 местам?». Баснописец Крылов предложил только 2 способа рассадки участников квартета. А сколько их было на самом деле?

У нас 4 объекта: 

Проказница мартышка; Осёл; Козёл; Косолапый мишка.

И мест тоже 4: первое, второе, третье, четвертое.

Допустим мартышка, как дама выбирает место первой. Сколько у неё возможностей?  Ведь она может занять любое из 4 мест, следовательно – 4.

Мишка по старшинству будет выбирать вторым, но уже только из 3 мест, так как одно занято, следовательно, у него 3 возможности.

Допустим, следующим будет козел, как имеющий неоспоримое преимущество в виде рогов. У него всего 2 возможности выбора, так как незанятых мест всего 2.

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

Напоминаю правило умножения для конечного числа испытаний: «Число всех возможных исходов независимого проведения n испытаний равно произведению количества исходов этих испытаний».

Значит, число возможных вариантов рассадки членов квартета составит: 4∙3∙2∙1=24.

И если бы баснописец Крылов описал все возможные способы, то мы получили бы не басню, а поэму.

А как называется полученное нами произведение идущих подряд n натуральных чисел? Факториалом!

Определение. Произведение идущих подряд n натуральных чисел обозначают n! и называют «эн факториал»: n!=1∙2∙3∙ … ∙ (n – 1)∙ n.

Фактически мы с Вами решали задачу о количестве перестановок некоторого n – элементного множества (в нашем случае 4 – х элементного множества).

Теорема. Число всех перестановок n – элементного множества равно n!.

n	1	2	3	4	5	6	7	8
n!	1	2	6	24	120	720	5040	40320

Обратим внимание, что приведённые числа – натуральные. Значит, при программировании следует учесть тип числа n при описании. Какой он?

Рассмотрим ещё несколько задач.  (Тексты перед Вами)

№1. У мамы и папы – один сын. К ним в гости пришла другая семья – мама, папа и дочь. За круглым обеденным столом есть 6 мест. Сколькими способами можно рассадить людей за столом, если:

а) место хозяина в доме неприкосновенно;

б) первыми садятся дети, и они садятся рядом;

в) первыми садятся дети, но не рядом друг с другом;

г) жены садятся рядом со своими мужьями?

Ответы:

№1 а) 120; б) 288; в) 432; г) 72.

Обратите внимание, какие числовые выражения, значения которых надо найти, получены в ответах. Что же может помочь нам в этом?

Алгоритм вычисления факториала Задания для самостоятельной работы

№2. а) В каждом из двух заплывов по шести дорожкам участвует 6 пловцов. Дорожки между пловцами в каждом заплыве разыгрываются по жребию. Найдите число всех возможных распределений пловцов по дорожкам.

б) То же, но если в каждом заплыве один из пловцов – победитель отборочных соревнований – плывет по четвертой дорожке.

в) То же, но если во втором заплыве участвуют 5 пловцов.

г) То же, но если в обоих заплывах участвует 4 пловца.

№3. Две команды по 5 шахматистов проводят матч из пяти одновременно проходящих партий, в каждой из которых встречаются  по одному из шахматистов каждой команды.

а) Найдите число всех возможных распределений встреч в матче.

б) То же, но для двух, независимо проводимых матчей.

в)  То же, но если во втором матче участвует только по три лучших шахматиста из каждой команды.

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

№4. Одинаковый текст приглашений напечатан на семи разных открытках. Их надо разослать директорам семи разных школ.

а) Найдите число всех возможных рассылок приглашений.

б) То же, что и в пункте а), но если самую красивую открытку послать директору школы №1.

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

г) то же, что и в пункте в), но если надо пригласить еще трех завучей по воспитательной работе из трех других школ.

Ответы:

№2  а) (6!)2; б) (5!)2; в) (6!)2; г) (6∙5∙4∙3)2.

№3 а) 120; б) 14400; в) 720; г) 2880.

№4 а) 7!; б) 6!; в) 7!∙; г) 7!∙.

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

№5. В зоопарке 5 львов надо распределить по одному по пяти клеткам, четырех тигров – по четырем другим клеткам и трех слонов – по трем вольерам.

а) Найдите число всех возможных распределений львов, тигров и слонов в зоопарке.

б) То же, но если есть четыре льва и львица и одного льва (известно какого именно) вместе с львицей надо посадить в одну клетку.

в)  То же, что и в пункте а), но если у львов есть две семейные пары.

г) то же, что и в пункте а), но если между клетками для тигров и клетками для львов нет разницы.

Ответ: а) 5!∙4!∙3!=17280; б) 17280; в)( 5∙4∙3)∙4!∙3!=8640; г) 2177280.

Итоги.