Учеба  ->  Среднее образование  | Автор: | Добавлено: 2015-03-23

Элементы комбинаторики в основной школе

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

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

Комбинаторика – раздел математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.

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

В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата.

Комбинаторные задачи возникали и в связи с такими играми, как шашки, шахматы, домино, кости.

Комбинаторика становится наукой лишь в 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 книги, если ему нужен словарь?

Комментарии


Войти или Зарегистрироваться (чтобы оставлять отзывы)