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

«Комбинаторные задачи и способы их решения»

ДОСТУПНО ВНЕСЕНИЕ ОТВЕТОВ

Описание презентации по отдельным слайдам:

Комбинаторные задачи и способы их решения Выполнил учащийся 6 класса средней школы при Посольстве России в Израиле Мидхатов Казим учитель математики Акишина Л.В.

Оглавление. Введение. Что такое комбинаторика и комбинаторные задачи. Из истории комбинаторики. Способы решения комбинаторных задач. Комбинаторные задачи. Используемая литература.

1. Введение. Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Начальнику цеха надо распределить несколько видов работ между имеющимися станками, агроному – разместить посевы сельскохозяйственных культур на нескольких полях, заместителю директора школы – составить расписание уроков, ученому- химику – рассмотреть возможные связи между атомами и молекулами, лингвисту- учесть различные варианты значений букв незнакомого языка и т.д. Очень часто и нам в жизни приходится делать выбор, принимать решение. Это сделать очень трудно, потому что приходится выбирать из множества возможных вариантов, различных способов, комбинаций. И нам всегда хочется, чтобы этот выбор был правильным. В этом нам помогают комбинаторные задачи, решая которые мы учимся думать необычно, оригинально, смело.

2. Что такое комбинаторика и комбинаторные задачи. Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой. Слово «комбинаторика» происходит от латинского слова combinate, которое означает «соединять», «сочетать». Комбинаторные задачи – это задачи, требующие осуществления перебора всех возможных вариантов или подсчета их числа.

Древний период. Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты. Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.). Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона. Во II веке до н. э. индийцы знали, что сумма всех биноминальных коэффициен- тов степени n равна. Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000. Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах. Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).

Средневековье. В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний. Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

Новое время Как наука комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры. В карты и кости выигрывались и проигрывались золото и бриллианты, дворцы и имения, породистые кони и дорогие украшения. Широко были распространены всевозможные лотереи. Понятно, что первоначально комбинаторные задачи касались в основном азартных игр – вопросов, сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей в данной карточной игре. Эти и другие проблемы азартных игр явились движущей силой в развитии комбинаторики и развивающейся одновременно с ней теории вероятностей.

Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывающую, сколькими способами могут выпасть r костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена различными способами (например, 1+3+4 = 4+2 +2). Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские ученые Паскаль и Ферма. Исходным пунктом их исследований тоже были проблемы азартных игр. Дальнейшее развитие комбинаторики связано с именами Якова Бернулли, Лейбница и Эйлера. Однако и у них основную роль играли приложения к различным играм (лото, солитер и др.).

4. Способы решения комбинаторных задач. Перебор различных вариантов. Дерево возможных вариантов. Составление таблиц. Правило умножения.

Дерево возможных вариантов. Самые разные комбинаторные задачи решаются с помощью составления специальных схем. Внешне такая схема напоминает дерево, отсюда и название метода – дерево возможных вариантов. Задача. Задача. Какие трехзначные числа можно составить из цифр 0, 3, 5? Решение. Построим дерево возможных вариантов, учитывая, что 0 не может быть первой цифрой в числе. Далее.

Задача № 7. В нашем классе 8 человек. Нам нужно выбрать старосту класса и его заместителя. Сколько возможно вариантов выбора старосты и его заместителя. Задача № 8. У Васи есть 2 пары обуви, 2-е брюк и три рубашки. Сколько у него вариантов одеться по-разному? Задача № 9. Имеется батон, черный хлеб, сыр, колбаса и джем. Сколько видов бутербродов можно приготовить? Задача № 10. На тарелке лежат 5 груш и 4 яблока. Сколькими способами можно выбрать один плод? Задача № 11. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать пару плодов, состоящую из яблока и апельсина? Задача № 12. Учащиеся 6 класса решили обменяться фотографиями. Сколько фотографий для этого потребуется, если в классе 8 человек?

6. Используемая литература. Вероятность и статистика. 5-9 кл.: пособие для общеобразоват. учеб. заведений / Е. А. Бунимович, В. А. Булычев. – 2-е изд. стереотип. – М.: Дрофа, 2004. Виленкин Н.Я. Комбинаторика, М., 1969 г. Виленкин Н.Я. «Индукция. Комбинаторика», М. «Просвещение», 1976 г. Ткачёва М. В. «Домашняя математика», М. Просвещение, 1993 г. Интернет-ресурсы.

Источник

Урок комбинаторики для 7-го класса по теме «Перестановки»

Разделы: Математика

Оборудование: учебник (1), дидактические материалы (2), Рисунок 1, Рисунок 2. Продолжительность занятия: 2 академических часа

Ход урока

I. Организационный момент

Проверка готовности класса к уроку. Постановка целей урока.

II. Повторение

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

Задание 1

Антон, Борис и Василий купили три билета на 1-е, 2-е и 3-е места первого ряда на футбольный матч. Сколькими способами они могут занять имеющиеся места?

Решение (с помощью правила умножения). На 1-е место может сесть любой из трёх друзей, на 2-е – любой из двух оставшихся, а на 3-е – последний. По правилу умножения у троих ребят существует 3*2*1 = 6 способов занять имеющиеся места.

Учитель. Перед введением понятия перестановки нам необходимо узнать ещё один новый термин. Название нового термина вы узнаете, если решите примеры.

Задание 2

Ответы замените буквами (смотрите на циферблат часов). Приложение 2

36 : 18 = 72 : 6 = 80 : 10 = 4,6 + 0,4 = 2,7 + 7,3 = 121 : 11 = 56 : 8 = 60 : 5 = 60 : 15 =

2 ф 12 а 8 к 5 т 10 о 11 р 7 и 12 а 4 л

III. Новый материал

Учитель. Итак, новый термин – факториал. Что же это такое?

Определение Для сокращения записи произведения первых n натуральных чисел в математике используется символ n! (читается как “эн факториал”), т.е.

n!=1*2*3*…*(n-1)*n (записать формулу в тетрадь).

(Перед тем, как вводить понятие и формулу перестановок, желательно, чтобы учащиеся освоились с понятием факториала. Для этого выполнить следующее задание 3).

Задание 3

а) 4! = 1*2*3*4 = 24;
б) 5! = 1*2*3*4*5* = 120;
в) 4! + 5! = 1*2*3*4 + 1*2*3*4*5 = 24+120 = 144;
г) 5*4! =5* 1*2*3*4 = 5! = 120;
(письменно): д) 4! * 5! = 1*2*3*4 *1*2*3*4*5 = 24 * 120 = 2880;

е) ;

ж)==;

з) ;

и) ; к) .

Учитель. Принято считать: 1!=1, 0!=1.

Факториалы растут удивительно быстро. Вы можете понаблюдать за их изменением, рассмотрев таблицу в учебнике, в которой приведены факториалы чисел от 1 до 10:

В задании 1 были подсчитаны всевозможные комбинации из четырех элементов. Чем отличаются полученные комбинации? (Ответ: полученные комбинации отличаются только порядком элементов). Такие комбинации называют перестановками из четырех элементов.

Если элементов будет 5, то, рассуждая аналогично (попросить кого-либо из семиклассников провести эти рассуждения), получаем, что число перестановок из 5 элементов равно 5*4*3*2*1=60, из 10 элементов число перестановок равно 10*9*8*7*6*5*4*3*2*1

Определение: Комбинации из n элементов, отличающиеся друг от друга только порядком расположения в них элементов, называют перестановками из n элементов. (иначе: “Каждое расположение элементов множества в определенном порядке называют перестановкой”.)

(Учащимся: определение “перестановок из n элементов” записать в тетрадь, выучить, рассказать соседу по парте/)

Учитель. Классической задачей комбинаторики является задача о числе перестановок, которую можно сформулировать так: сколькими способами можно переставить n различных предметов, расположенных на n разных местах?

Решение этой задачи выглядит так.

Возьмем n местных корзинок, в которые будем укладывать n разных предметов. В первую корзину можно положить один из n предметов, во вторую – один из n-1 оставшихся и т.д., вплоть до последней корзинки, в которую можно единственным образом уложить оставшийся предмет. По правилу произведения (умножения) получаем n*(n-1)*…*1= n! способов, т.е. число перестановок из n элементов равно n!

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

P_n (P – первая буква французского слова permutation – перестановка). Читается: “Число перестановок из эн элементов” или “Пэ из эн”.

В задании 1 было показано P₄ = 4*3*2*1 = 1*2*3*4 (по переместительному свойству умножения).

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

При использовании символа n! формула (1) принимает вид P_n= n!

(Учащимся: правило нахождения перестановок из n элементов записать в тетрадь словами и формулой, выучить, рассказать соседу по парте).

Примеры 1, 2, 3 учащиеся изучают самостоятельно [1]:

Пример 1. В расписании 7 класса на четверг должно быть 6 предметов: русский язык, литература, алгебра, география, физика, физкультура. Сколькими способами можно составить расписание на этот день?

Решение. Число способов, которыми можно составить расписание, равно числу перестановок из шести элементов: P₆=6!=1*2*3*4*5*6=720.

Пример 2. Сколькими способами можно составить расписание из тех же 6 предметов, если требуется, чтобы урок физкультуры был последним?

Решение. У урока физкультуры фиксированное место, поэтому расписания отличаются порядком остальных 5 предметов. Значит, число таких расписаний равно числу перестановок из 5 элементов: P₅=5!= 120.

Пример 3. Сколькими способами из тех же 6 предметов можно составить такое расписание, в котором русский язык и литература стоят рядом?

Решение. Будем рассматривать русский язык и литературу как один предмет, тогда всего предметов будет пять. Число способов, которыми можно составить расписание из 5 предметов, равно P₅=5!. Но в каждой из этих перестановок русский язык и литература могут меняться местами. Поэтому искомое число расписаний вдвое больше. Оно равно 5!*2=240.

IV. Закрепление

(Задачи на нахождение перестановок решали раньше, но без использования термина и формулы (см. задачу 1/)

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

Обращать внимание учащихся при решении задач на следующие факты:

1) в задачах на перестановки используются все элементы данного набора элементов;

2) две перестановки одного набора элементов отличаются друг от друга только порядком элементов).

Задание 4

Сколькими способами можно выписать в колонку фамилии 30 учеников? Решение. P₃₀ = 30!

Задание 5

Сколько различных 5-значных чисел, все цифры которых различны можно записать с помощью цифр 4, 5, 6, 7, 8?

Решение. Задача сводится к подсчету числа перестановок из 5 элементов. P₅ = 1*2*3*4*5 = 120. Ответ: 120 различных чисел.

Задание 6

Сколькими способами можно расставить на полке 8 книг, если среди них 2 книги одного автора, которые при любых перестановках должны стоять рядом?

Задание 7

Задание 8. Четыре лектора должны прочитать по одной лекции. Сколько имеется вариантов составления расписания?

Решение. P₄ = 4! = = 24

Задание 9. Капитан Жеглов рассматривает фотографии. Всего их у него 25. Сколько существует различных последовательностей их рассматривания?

Задание 10 У мамы есть один апельсин, одна груша, одно яблоко и один банан. Она хочет раздать их четверым детям так, чтобы каждому достался какой-нибудь фрукт. Сколько имеется вариантов это сделать?

Задание 11. Напомним, что анаграмма – это слово, полученное из данного слова перестановкой его букв (но не обязательно имеющее смысл). Сколько существует различных анаграмм слова а) график; б) интеграл; в) факториал; г) перестановка; д) комбинаторика?

Решение. а) 6! = 720; б) 8! = 40 320; в) указание: временно считайте две буквы “а” различными буквами (обозначьте их “а₁” и “а₂”) и сосчитайте все возможные анаграммы; далее учтите, что те анаграммы, которые получаются перестановкой букв “а₁” и “а₂”, на самом деле одинаковы; ;

г) 12!:2:2 (по две “е”, “а”);

д) 13!:2:2:2:2 (по две “к”, “и”, “о”, “а”).

IV. Повторение основных понятий темы “Перестановки”

V. Проверочная работа по теме “Перестановки” [2]

50 депутатов парламента рассаживаются в зале заседаний, в котором 50 мест. Сколько у них есть вариантов это сделать? (Решение. 50!)

Упростите выражение (Решение. 14).

(Решение. Первоначально объединим “Грильяж” и “Белочку” в одну конфету и распределим две конфеты (“Грильяж-Белочка” и “Мишка”) между старшим и средним ребенком. Число способов, которыми можно разделить конфеты между двумя детьми, равно P₂=2!=2. А далее ребенок, которому досталось две конфеты, отдаст одну из двух младшему. Таким образом, получим, что разделить конфеты между детьми можно 2!*2=4 способами.

200 солдат строятся в шеренгу. Сколько имеется вариантов это сделать? (Решение. 200!)

Упростите выражение (Решение. 1).

(Решение. Первоначально объединим “Сникерс” и “Баунти” в одну шоколадку и распределим две шоколадки (“Марс” и “Сникерс-Баунти”) между средним и младшим ребенком. Число способов, которыми можно разделить шоколадки между двумя детьми, равно P₂=2!=2. А далее ребенок, которому досталось две шоколадки, отдаст одну из двух старшему. Таким образом, получим, что разделить шоколадки между детьми можно 2!*2=4 способами.

* – задание повышенной сложности, можно оценить отдельной отметкой.

VI. Подведение итогов урока

(Повторение основных понятий, см п. V.)

Домашнее задание: п. 6.4 (записи в тетради), № 612 (обратить внимание при решении задачи: все ли элементы набора используются и чем отличаются наборы элементов друг от друга),

а) В конкурсе участвуют 8 школьников. Сколькими способами могут быть распределены места между ними? (Решение. 8! = 40 320).

б) Сколькими способами можно составить маршрут путешествия, проходящего через 7 городов? (Решение. 7! = 5 040).

в) Сколькими способами можно расставить на полке 10 различных книг? (Решение. 10! = 3 628 800).

доп. № 619 ( представить, что всего 4 книги одного автора; подумать,сколькими способами можно их расставить; затем считать эти 4 книги одной книгой и добавить к ним оставшиеся книги; продолжить аналогичные рассуждения).

Сколькими способами можно расставить на полке 10 книг, из которых 4 книги одного автора, а остальные – разных авторов, так, чобы книги одного автора стояли рядом? (Решение. 7! * 4!).

Источник