Элементы комбинаторики в основной школе
Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности, например конструктору, разрабатывающему новую модель механизма, ученому – агроному, планирующему распределение сельскохозяйственных культур на нескольких полях, химику, изучающему строение органических молекул, имеющих данный атомный состав, поэтому каждому приходится решать задачи, которые относятся к разделу дискретной математики- комбинаторики.
Комбинаторные задачи физики, химии, биологии, экономики и других наук, которые не поддавались ранее решению из – за трудоёмких вычислений, стали успешно решаться. В результате комбинаторные методы исследования всё глубже проникают во многие разделы науки и техники.
Комбинаторика – раздел математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.
С аналогичными задачами, получившими назначение комбинаторных, люди столкнулись в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлекались составлением магических квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же.
В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата.
Комбинаторные задачи возникали и в связи с такими играми, как шашки, шахматы, домино, кости.
Комбинаторика становится наукой лишь в XVIII веке – в период, когда возникла теория вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчинённых тем или иным условиям. После первых работ, выполненных в XVI веке итальянскими учёными Дж. Кардано, Н. Тартальей и Г. Галилеем, также задачи изучали французские математики Б. Паскаль и П. Ферма.
Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ Г. Лейбниц, опубликовавший в 1666 году работу «Об искусстве комбинаторики», в которой впервые появляется сам термин «комбинаторный». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру.
Комбинаторными задачами интересовались и математики, заним вши
- ся составлением и разгадыванием шифров, изучением древних письменностей.
Теперь комбинаторика находит приложения во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений.
Комбинаторика – один из разделов дискретной математики, который приобрёл большое значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике.
По мере развития комбинаторики выяснилось, что несмотря на внешнее различие изучаемых ею вопросов, многие из них имеют одно и тоже математическое содержание и сводятся к задачам о конечных множествах и их подмножествах.
Важную область комбинаторики составляет теория перечислений. С её помощью можно подсчитать число решений различных комбинаторных задач, в основе этой теории лежат «правило суммы» и «правило произведения».
Целый ряд комбинаторных задач возникает при разбиении множеств на части. Обычно задачи теории разбиений и раскладок сводятся к формуле перекрытий. Такими же способами решаются комбинаторные задачи с ограничениями, например, подсчет числа размещений с повторениями, в которых ни один элемент не стоит два раза подряд и т. д.
В решении комбинаторных задач часто используют графические методы – разбиению числа на слагаемые в виде точечных диаграмм, так называемые графы. Теория графов стала в наши дни одной из наиболее развивающихся частей комбинаторики. Многие общие теоремы этого раздела математически формируются на языке графов.
Комбинаторика не сводится только к подсчету количества тех или иных подмножеств или последовательностей. При решении комбинаторных проблем иногда нужно лишь доказать, что данная проблема имеет решение, или убедиться в отсутствии его.
Если заданным условиям удовлетворяют несколько конфигураций, т. е. если комбинаторная задача имеет несколько решений, то может возникнуть вопрос о выборе из них решения, оптимального по тем или иным параметрам.
Итак, основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие:
1. образование упорядоченных множеств, состоящее в установлении определенного порядка следования элементов множеств друг за другом, составление перестановок;
2. образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов, - составление сочетаний;
3. образование упорядоченных подмножеств – составление размещений.
Исследование учебников математики для 5-6 классов и алгебры 7-8 классов
Магический квадрат.
Представляет собой такую квадратную таблицу (n * n) целых чисел от 1 до nk, что суммы чисел вдоль любого столбца любой строки и двух диагоналей таблицы равны одному и тому же числу s = n(nk +1)/2. Число n называют порядком магического квадрата. Доказано, что магический квадрат можно построить для любого n > 3. Уже в средние века был известен алгоритм построения магических квадратов нечётного порядка. Существуют магические квадраты, удовлетворяющие ряду дополнительных условий. Например, магический квадрат с = 8, который можно разделить на четыре меньших магических квадрата n * 4.
В Индии и некоторых других странах магические квадраты употреблялись как талисманы. Однако, общей теории магических квадратов не существует.
Перестановки.
Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки.
Например, нужно расставить 3 книги на полке разными способами. Обозначим книги буквами a, b, c.
Эти книги можно расставить на полке по-разному.
Если первой книгой aa, b, c;a, c, b
Если первой книгой b b, a , c;b, c, a
Если первой книгой c c, a , b;c, b , a
Каждое из этих расположений называют перестановкой из трёх элементов.
То есть перестановкой из n элементов называется каждое расположение этих элементов в определённом порядке.
Число перестановок из n элементов обозначают символом Рn. В рассмотренном примере установили, что Рn = 6. для того, чтобы найти число перестановок, можно не выписывать эти перестановки, а воспользоваться правилом умножения. В результате получим
= n (n – 1)* (n – 2) *. *3 *2 * 1
Расположив множители в порядке возрастания, получим:
Рn = 1*2*3*. (n – 2)* (n – 1) * n
Р3 = 3! = 1*2*3 = 6
Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки
Пример 1: В магазине продают кепки трёх цветов: белые (б), красные (к) и синие (с). Кира и Лена покупают себе по одной кепке. Сколько существует различных вариантов покупок для этих девочек? Перечислить их.
Решение:
В магазине продаются не 3 кепки, а кепки трёх видов, т. е. Кира и Лена могут купить кепки одинаковых цветов; возможен выбор с повторением.
белые (б) красные (к) синие (с) бб кб сб бк кк ск бс кс сс.
Всего 9 вариантов.
Ответ: всего 9 вариантов.
Пример 2: С помощью цифр 8 и 9 записать все возможные двузначные числа, в которых цифры: а) должны быть разными; б) могут повторяться.
Решение а) Если цифры должны быть разными, то можно записать 2 разных числа:89 и 98; б) Если цифры могут повторяться, то можно записать 4 разных числа: 88, 89, 98 и 99.
Ответ: а)2 числа; б)4 числа.
Пример 3: Ашот (А), Марат (М) и Сергей (С) могут занять 1-е, 2-е и 3-е призовые места в соревнованиях. Перечислить все возможные последовательности из имён мальчиков, где порядковый номер в последовательности соответствует занятому мальчиком месту в соревнованиях. Подсчитать их количество.
Решение:
Нужно подсчитать количество способов расположения трёх юношей на трёх призовых местах; эти способы будут отличаться лишь порядком расположения юношей.
Сначала выбираем одного на первое место, а двух других меняем местами, потом берём на первое место другого, и т. д. :
АМС МАС САМ
АСМ МСА СМА
Всего 6 вариантов расположения.
Ответ: 6 вариантов.
Также для таких типов задач используется формула:
Пример 4: Сколькими способами 4 человека могут разместиться на четырёхместной скамейке?
Решение:
Количество человек равно количеству мест на скамейке, поэтому количество способов размещения равно числу перестановок из 4-х элементов:
Ответ:24 способами.
Размещения.
Одна из классических комбинаторных задач, в которой требуется определить число способов размещения различных предметов в n различных ячеек с заданным числом Ґ пустых ячеек.
Например: 4 шара a b c d необходимо по-разному разместить в 3 – х пустых ячейках. Выбирая по-разному первый, второй, третий шары будем получать различные упорядоченные тройки шаров.
Каждую упорядоченную тройку, которую можно составить из четырёх элементов, называют размещением из четырёх элементов по три.
Размещением из n элементов по k (k < n) называется любое множество, состоящее из любых элементов, взятых в определённом порядке их данных n элементов.
Число размещений из n элементов по k обозначается А kn (А из по k). Число размещений можно тоже находить пор формуле
Размещение из n элементов по n отличаются друг от друга только порядком элементов, то есть представляют собой перестановки из n элементов. Получаем формулу:
И приходим к известной формуле
Значит, в нашей задаче можно составить 24 размещения.
Р4=1* 2 * 3 * 4 = 24
Пример 5:Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать?
Решение: из 30 элементов выбираем 2, причём порядок выбора имеет значение. Количество способов равно способов.
Ответ: 870 способов.
Пример 6:Сколькими способами могут быть распределены первая, вторая и третья премии между 15 участниками конкурса?
Решение
Выбираем 3 призёров из 15 участников конкурса с учётом порядка (кому какая премия):
способов.
Ответ: 2730 способов.
Сочетания.
Это задачи, которые сводятся к организации полного перебора вариантов.
Например, имеются пять гвоздик разного цвета a, b, c, d, e. Требуется составить букет из трёх гвоздик.
Если в букет входит гвоздика a, то можно составить такие букеты a b c, a b d,a d e, a c d, a c e, a d e
Если в букет не входит гвоздика a, но входит b, то можно получить такие букеты: b c d, b c e,b d e
Наконец, если в букет не входят ни гвоздика a, ни гвоздика b, то возможен только один вариант составления букета: c d e
Мы указали все возможные способы составления букетов, в которых по-разному сочетаются три гвоздики из данных пяти. Говорят, что мы составили все возможные сочетания из 5 элементов по 3.
Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов.
В отличие от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по k отличаются друг от друга хотя бы одним элементом.
Число сочетаний можно найти по формуле:
Число сочетаний можно найти по формуле:
Если дробь домножить на(n-k), где , получим:
Очевидно, что числитель дроби равен п!, поэтому получаем формулу
Подводя итог, его можно оформить в 3 теоремы:
Теорема 1(о выборке 2 элементов). Если множество состоит n из элементов, то у него имеется подмножеств, состоящих из 2 элементов.
Теорема 2(о выборке 3элементов). Если множество состоит из n элементов, то у него имеется подмножеств, состоящих из 3 элементов
Теорема 3. Для числа сочетаний из n элементов по k справедлива формула
Пример 7: Учащимся дали список из 10 книг, которые рекомендуется прочитать во время каникул. Сколькими способами ученик может выбрать из них 6 книг?
Решение:
Выбор 6 из 10 без учёта порядка:
способов.
Ответ:210 способов.
Пример 8:Выпишите все пятизначные числа, записанные тремя четвёрками и двумя единицами.
Решение.
Сформировать число можно, выбрав два места из пяти для единиц, а остальные заполнить четвёрками. Порядок выбираемых мест значения не имеет (единицы не различимы, поэтому 1 -2 и 2 – 1 - одна и та же пара).
Будем выбирать места для единиц согласно алгоритму (указаны номера мест в пятизначном числе):
1-2 2-3 3-4 4-5
1-3 2-4 3-5
1-4 2-5
Сами числа будут иметь вид:
11444 41144 44114 44411
14144 41414 44141
14414 41441
Количество различных чисел равно:
Ответ:10 чисел
Заключительная часть
Итак, я привела несколько типов комбинаторных задач. На мой взгляд, эти задачи не просто интересные, но и развивающие логическое мышление учащихся. Изучив учебники по математике для 5-7 классов, я обнаружила, что в учебниках В. Г. Дорофеева присутствуют задачи комбинаторного типа и не являются задачами повышенной сложности, в учебниках других авторов такие задачи либо отсутствуют, либо присутствуют в маленьком количестве.
Существуют разработанные приложения по комбинаторике для учебников (под редакцией С. А. Теляковского, А. Г. Мордковича, Ш. А. Алимова), но к нам в лицей приходят учащиеся из разных школ города, где обучаются по разным учебникам, и поэтому я составила своё тематическое планирование для факультативных курсов по комбинаторике для 8 класса, где подобрала и решила задачи, на мой взгляд, наиболее интересные.
Мой проект был рассмотрен на заседании МО учителей математики лицея и было принято решение о проведении в 2007 – 2008 учебном году факультативного курса в восьмых классах.
Примерное тематическое планирование для факультатива
Тема Кол-во часовЗадания в классе Домашнее задание
Примеры комбинаторных 2 1. Укажите все способы, какими можно разложить 3 яблока в 21. У Ирины 5 подруг: Вера, Зоя, Даша, Юля и задач вазы (решения см. в приложении) Катя. 2 из них она пригласила в кино. Укажите
2. Подсчитать число однобуквенных слов в языке. все возможные варианты выбора. Сколько их?
3. (Устно) Сколькими способами Петя и Вова могут сесть за 2. Используя цифры 0, 2, 4, 6, составьте все
2-х местную парту? возможные трёхзначные числа, (цифры не
4. Стадион имеет 4 входа: А, Б, В, Г. Указать все способы, повторяются).
как можно войти через один, а выйти через другой. Сколько 3. Используя буквы Н, о, а, составить их? двухбуквенные слова
4. Придумайте 4ситуации, в 2 – порядок важен, а в остальных - нет
Правило умножения 1 1. Перечислить все трёхзначные числа, в записи встречаются 1. Из села A в село B ведут 3 дороги, а из B в только цифры 8 и 9. село C - 4 дороги. Сколько способов попасть
2. В соревнованиях по футболу участвовало 12 команд. Каждаяиз A в C через B?
команда провела с каждой из остальных по одной игре на 2. 8 человек обменялись рукопожатиями? Сколько своём поле и по одной на поле соперника. Сколько всего игрвсего рукопожатий было сделано?
было сыграно?
Дерево вариантов 1 1. В кафе предлагают 2 первых блюда: борщ, рассольник, а 1. Вова точно помнит, что в формуле азотной также 4 вторых блюда: гуляш, котлеты, сосиски, пельмени. кислоты подряд идут буквы H, N, O и что есть
Укажите все обеды из 2-х блюд, которые может заказать один нижний индекс – то ли 2, то ли 3.
посетитель, в виде дерева возможных вариантов. Нарисуйте дерево возможных вариантов.
2. Из 4-х тузов поочерёдно выбирают 2. Нарисуйте дерево 2. В клетки квадратной таблицы ставят возможных вариантов. произвольно крестики и нолики. Сколькими способами можно заполнить таблицу?
Перестановки 1 1. Сколькими способами могут встать в очередь в билетную 1. Сколькими способами можно обозначить кассу 3 человека? вершины куба A, B, C, D, E, F, G, K?
2. Сколько существует вариантов рассаживания вокруг стола 62. Вычислите а)7!; б)8!; в)6!-5!; г);
гостей на 6 стульях?
Размещение 2 1. На станции 7 запасных путей. Сколькими способами можно 1. Сколькими способами 6 студентов, сдающих расставить на них 4 поезда? экзамен, могут занять места в аудитории, в
2. Сколькими способами могут быть распределены 1, 2 и 3 которой стоит 20 одноместных столов?
премии между 15 участниками конкурса? 2. Сколько четырёхзначных чисел , в которых нет
3. Сколькими способами могут занять 1, 2 и 3 места 8 одинаковых цифр, можно составить из цифр 1, 3, участниц финального забега на дистанции 100 м? 5, 7.
4. Из 30 участников собрания надо выбрать председателя и 3. Высказать гипотезу о числе всевозможных секретаря. Сколькими способами это можно сделать? разбиений n элементов на 3 группы.
4. Сколькими способами может семья из 3 человек разместиться в 4-хместном купе, если других пассажиров в купе нет?
Самостоятельная работа1 1. На дверях 4 одинаковых кабинетов надо повесить таблички нет с фамилиями 4 заместителей директора. Сколькими способами можно это сделать?
2. В 9 «а» в среду 5 уроков: алгебра, геометрия, физика, русский язык и английский язык. Сколько есть вариантов составления расписания?
3. Сколькими способами 4 вора могут разбежаться по одному на все 4 стороны?
Повторение 1 1. Сколькими способами можно записать в виде произведения 1. Сколькими способами можно записать в виде число 12 и 120. произведения число 24?
2. Пешеход должен пройти 1 квартал на С и 3 квартала на З 2. В шахматном кружке занимаются 16 человек.
Сколькими способами тренер может выбрать из них для предстоящего турнира команду из 4
человек. указав кто будет на 1, 2 и 3 досках?
Контрольная работа 1 1. Вычислите: нет
1 вариант а); б);
2 вариант а); б);
2. Найдите сумму цифр всех четырёхзначных чисел, которые можно составить из:
1 вариант
1, 3, 5, 7
2 вариант
2, 4, 6. 8.
3. Что больше 6! * 5 или 5! * 6.
Работа над ошибками 1 Нет (учитель объясняет решение задач) нет
(резервный урок)
Сочетания. 4 1. В классе 7 человек успешно занимаются математикой. 1. В правильном 17-угольнике провели все
Сколькими способами можно выбрать из них двоих для участиядиагонали. Сколько имеется сторон?
в математической олимпиаде? 2. В правильном 17-угольнике провели все
2. Сколько существует способов выбрать 3 ребят из четверых диагонали. Сколько провели диагоналей?
желающих дежурить по столовой? 3. В правильном 17-угольнике провели все
3. Учащимся дали список из 10 книг, которые рекомендуется диагонали. Сколько всего диагоналей в выпуклом прочитать во время каникул. Сколькими способами ученик n-угольнике?
может выбрать из них 6 книг? 4. На плоскости отметили точку. Из неё провели
4. Выпишите все пятизначные числа, записанные тремя 9 лучей. Сколько при этом получилось углов?
четвёрками и двумя единицами. 5. Из группы туристов 4 дежурных можно выбрать
5. Сколькими способами 4 различные монеты можно разложить в 13 раз большим числом способов, чем 2
по двум карманам? дежурных. Сколько туристов в группе?
6. Учащимся дали список из 10 книг, которые рекомендуется 6. Из 12 солдат, в число которых входят Иванов прочитать во время каникул. Сколькими способами ученик и Петров, надо отправить в может выбрать из них 6 книг?
7. В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется выделить 4 мальчика 3 девочек. наряд из 3 человек. Сколькими способами это
Сколькими способами это можно сделать? можно сделать, если Иванов и Петров должны
8. В правильном 17-угольнике провели все диагонали. Сколькопойти?
всего отрезков? 7. Из 12 солдат, в число которых входят Иванов
9. Сократите дробь: и Петров, надо отправить в наряд из 3 человек.
. Сколькими способами это можно сделать, если
Иванов и Петров должны остаться?
8. Из 12 солдат, в число которых входят Иванов и Петров, надо отправить в наряд из 3 человек.
Сколькими способами это можно сделать, если
Иванов пойдёт, а Петров останется?
Самостоятельная работа1 1. Сократите дробь: нет а); б).
2. Вычислить:
1); 2).
3. Найдите значение выражения:
1); 2).
Закрепление 1 1. Решить уравнение: 1. Число размещений из п элементов по 4 в 14
2. Сколько надо взять элементов, чтобы число размещений из раз больше числа размещений из п-2 элементов них по 4 было в 12 раз больше, чем число размещений из нихпо 3. Найдите п.
Итоговая контрольная 1 1 вариант нет работа (если резервный 1. Шесть граней игрального кубика помечены цифрами 1, 2, 3, урок не использован, 4, 5, 6. Кубик бросают дважды и записывают выпавшие очки.
то необходимо Найдите число всех возможных результатов.
использовать его в 2. Вычислите.
качестве работы над 3. В магазине «Филателия» продается 8 различных наборов ошибками после марок. Сколькими способами можно выбрать из них 3 набора?
итоговой контрольной 2 вариант работы) 1. 3 вершины правильного 10-
угольника покрасили в рыжий цвет, а остальные – в чёрный.
Найдите число всех возможных вариантов.
2. Вычислите
3. На полке стоит 12 книг: англо-русский словарь и 11
произведений на английском языке. Сколькими способами читатель может выбрать 3 книги, если ему нужен словарь?
Комментарии