Комбинаторика для школьников любого возраста.
методическая разработка (алгебра, 7 класс) по теме

Элективный курс по математике (разработка + презентация)

на тему:

«Комбинаторика для школьников любого возраста»

Выполнили:

Лапина Любовь Михайловна,

Леухина Татьяна Николаевна,

учителя математики высшей категории

МОУ «Средняя общеобразовательная

школа №1 п.Советский с углубленным изучением отдельных предметов» Республики Марий Эл.

Бывает, что вовремя урока математики, когда даже воздух стынет от скуки, в класс со двора влетает бабочка…

А.П.Чехов.

Пояснительная записка.

Элективный курс рассчитан для учащихся 4-6 классов с различным уровнем обучаемости и подготовки. Представленный материал по теме «Комбинаторика» доступен учащимся даже начальной школы; он учит не готовым формулам, определениям, а некоторым простейшим навыкам.

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

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

Элективный курс рассчитан на 18 часов.

Задачи курса:

1. Дать основные рекомендации по усвоению набора правил и научить определять учащихся, соответствует ли данная последовательность данному правилу.
2. Научить учащихся строить различные комбинации при решении задач.

Цели курса:

Образовательные: 

1. cформировать у учащихся основы элементарных знаний по комбинаторике;
2. определить содержание знаний и умений учащихся по данной теме;
3. конкретизировать полученные сведения в системе уроков по изучаемой теме;
4. подготовить учащихся к постепенному изучению темы «Теории вероятностей».

Воспитательные:

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

Развивающие:

2. развитие памяти учащихся;
3. развитие умений преодолевать трудности при решении математических задач;
4. развитие любознательности учащихся;
5. развитие познавательного интереса учащихся;
6. развитие умений искать ответы на возникшие вопросы по данной теме с помощью схем;
7. развитее логического мышления.

Содержание курса(18 часов):

1. Комбинаторные задачи. 2 часа. Приложение 1.
2. Дерево возможных вариантов. 3 часа. Приложение 2.
3. Основные понятия комбинаторики. 13 часов:

а) Понятие факториала. 1 час. Приложение 3.

б) Размещения ( без повторений). 4 часа. Приложение 4.

в) Перестановки (без повторений). 3 часа. Приложение 5.

г) Сочетания (без повторений). 3 часа. Приложение 6.

 д) Основное свойство сочетаний. 2 часа. Приложение 7.

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

Оборудование: интерактивная доска, проектор, компьютер, принтер.

Список литературы

1. М.В.Ткачева «Домашняя математика», М.,Просвещение,1994.
2. О.Оре «Теория графов», перевод с английского. М., Наука, 1980.
3. А.Плоцки «Вероятность в задачах для школьников». Книга для учащихся. М., Просвещение, 1996.
4. Газета «Математика». Приложение к газете «Первое сентября», 2003.
5. Б.А.Кордемский «Математическая смекалка», М., Просвещение, 2001.
6. М.Гарднер Математические головоломки и развлечения». М., Мир, 1971.
7. К.А.Рыбников «История математики», М., МГУ, 1994 

Дополнительная литература.

1. Виленкин Н.Я. "Индукция. Комбинаторика", М. "Просвещение", 1976 г.
2. Глейзер Г.И. "История математики в средней школе", М., "Просвещение", 1970 г.
3. Материалы учителя Тарасовой А.М., сош № 46, г.Белгород
4. Шарафутдинова Р.Ю., учитель математики, МОУ "Лицей г. Вольска", элективный курс "Секреты комбинаторики"
5. Айгнер М. Комбинаторная теория. М.: Мир, 1982.
6. Рыбников К.А. История математики. М.: МГУ, 1994.
7. http://combinatorica.narod.ru/ 
8. http://mmmf.math.msu.su/ 
9. http://portfolio.1september.ru/ 

1.Комбинаторные задачи.

Комбинаторика (от лат.  combinatio - «соединения») - раздел математики, занимающийся изучением соединений.

Соединениями называются группы, составленные из каких-либо предметов(например из букв, цифр, флажков, шаров и т.д.) Сами предметы, из которых составляются соединения, называются элементами.

 Некоторые комбинаторные задачи:

Задача 1.1.  Дано четыре шара: два синих(с) и два красных(к). Какие последовательности(соединения) можно составить из этих шаров?

Решение:  ССКК;  СКСК;  СККС; ККСС;  КСКС;  КССК.

Предлагается несколько задач такого же типа:

-Из одного К и одного С жетонов можно построить 2 последовательности;

- Из одного К и двух С жетонов можно построить 3 последовательности;

-Из одного К и трех С жетонов можно построить 4 последовательности;

- Из двух К и трех С жетонов можно построить  10 последовательностей?

Сколько существует последовательностей из:

-Одного Красного, одного Синего и двух Зеленых жетонов;

- Одного Красного, одного Синего и трех Зеленых жетонов;

- Одного Красного, одного Синего , одного Зеленого и одного Желтого  жетонов?

Задача 1.2. Даны жетоны трех цветов (красный, желтый, синий). Построить последовательности, состоящие из двух жетонов, с повторением цветов или без повторения.

 Решение: а) с повторением и учетом порядка: КК; КЖ; КС; ЖК; ЖЖ; ЖС; СК; СЖ; СС;

                     б) без повторения с учетом порядка: КЖ; КС; ЖК; ЖС; СК; СЖ;

                     в) с повторением и без учета порядка: КК; КЖ; КС; ЖЖ; ЖС; СС;

                     г) без повторения и без учета порядка: КЖ; КС; ЖС.

Задача 1.3. Из цифр 1, 2, 3, 4 составить возможные двузначные числа.

Решение: а) без повторения цифр:  12,   13,  14,

                                                              21,  23,  24,

                                                              31,  32,  34,

                                                              41,  42,  43.

                    б) с повторением цифр:  11,  12,  13,  14,

                                                               21,  22,  23,  24,

                                                               31,  32,  33,  34,

                                                               41,  42,  43,  44.

Задача 1.4. Сколько трехзначных чисел можно составить, используя цифры 5 и 7?

Задача 1.5. В школе проводятся соревнования по хоккею. В качестве призов решили использовать мячи(М), ракетки(Р), клюшки(К), шайбы(Ш). Сколько различных призов можно составить из этих предметов, если каждый победитель получит по два разных предмета?

Решение:  МР; МК; МШ; РК; РШ; КШ.

Задача 1.6. Служитель зоопарка должен дать зайцу два различных овоща.  Сколькими различными способами он может это сделать, если у него есть морковь(М), свекла(С) и капуста(К)?

Решение: МС; МК; СК.

Задача 1.7.  Наташа, Данила, Андрей и Маша – лучшие знатоки математики в классе. На школьную олимпиаду нужно выставить команду из  двух человек. Можно ли составить пять различных команд?  Сколько различных команд,  составленных из одной девочки и одного мальчика, может выставить данный класс?

Решение:  а) НД; НА; НМ; ДА; ДМ; АМ;

                   б) НД; НА; МД; М

2. Дерево возможных вариантов.

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

Задача 2.1. Составим двузначные числа из цифр 2, 5 и 9.

Решение: (Слайд 2).

Полученные числа:  22, 25, 29, 52, 55, 59, 92, 95, 99.

Задача 2.2. Школьники из Волгограда во время каникул собирались поехать в Москву, посетив по дороге Нижний Новгород. Путь их передвижения: из Волгограда в Нижний Новгород можно отправиться на теплоходе(Т) или на поезде(П), а из Нижнего Новгорода в Москву – на самолете(С), теплоходе, поезде или на автобусе(А). Какими различными способами учащиеся могут осуществить свое путешествие?

Решение: (Слайд 3)

Варианты путешествия:  ТС, ТТ, ТП, ТА, ПС, ПТ, ПП, ПА.

Задача 2.3. В магазине имеется три сорта мороженого: рожок(Р), брикет(Б) и эскимо(Э). Наташа и Данила решили купить по одной порции. Сколько вариантов такой покупки существует?

Решение: (Слайд 4)

Варианты покупки: ББ, БР, БЭ, РБ, РР, РЭ, ЭБ, ЭР, ЭЭ.

Задача 2.4. Данила, Андрей и Наташа тренировались в бросании мяча в баскетбольную корзину. У них только один мяч, и им надо договориться, кто за кем будет бросать мяч. Сколькими способами они могут занять очередь друг за другом?

Решение: (Слайд 5)

Варианты очереди:  НДА, НАД, ДНА, ДАН, АНД, АДН.

Задача 2.5. Наташа сшила кукле 10 разных платьев, а Даша сшила своему мишке 3 штанишек и 4 футболки. Как вы думаете, у кого больше разных нарядов – у куклы или у мишки?

1. Понятие факториала.

Произведение всех натуральных чисел от 1 до n включительно называют n-факториалом и пишут:

Задача 3.1.  Вычислить:

                   а) 3!          б) 7! – 5!                 в) (7! -5!)/6!

                   г)       д) 5!/(3!+4!)            е) /6!

2) Размещения (без повторений).

Решим следующие задачи:

Задача 3.2.1. Даны три элемента: А,Б,В, Составим из них соединения по одному элементу – это А,Б,В, Такие соединения называются размещениями из трех элементов по одному, их количество равно 3.

Составим теперь из этих элементов такие соединения по два элемента, которые отличаются друг от друга либо порядком, либо самими элементами (хотя бы одним). Получим соединения: АБ, АВ, БВ, БА, ВА, ВБ. Такие соединения называются размещениями из трех элементов по два, их количество равно 6.

Составим из этих элементов соединения по три в каждом, отличающиеся либо порядком элементов, либо самими элементами. Это АБВ, АВБ, БАВ, БВА, ВАБ, ВБА – размещения из трех элементов по три, их количество равно 6.

 Задача 3.2.2. Даны четыре элемента: А, Б, В, Г, Составим из них соединения по одному – это  А, Б, В, Г.  Такие соединения называются размещениями их четырех элементов по одному, их количество равно 4.

Составим из этих четырех элементов такие соединения по два элемента, которые отличаются друг от друга либо порядком, либо самими элементами (хотя бы одним).  Получим соединения АБ, АВ, АГ, БВ, БГ, ВГ, БА, ВА, ГА, ВБ, ГБ, ГВ. Они называются размещениями из четырех элементов по два: их 12. Соединения АБ и БА отличаются порядком элементов, АБ, АГ – одним элементом, АБ, ВГ – самими элементами.

Определение. Размещениями называются соединения, содержащие по n элементов из числа данных m элементов (где mn) и различающиеся либо порядком элементов, либо самими элементами.

Число размещения из m элементов по n обозначается символом .

Решим задачу «Четверо вокруг стола» с привлечением дерева возможных вариантов.

Задача 3.2.3. Сколькими способами можно разместить четырех человек (А, Б, В, Г) вокруг стола, на котором стоят четыре прибора – золотой (з), серебряный (с), мельхиоровый (м), фарфоровый (ф)?

Существует четыре способа занять место самым почетным золотым прибором, т.е. (см. дерево вариантов). В каждом из этих четырех случаев имеются три способа занять место за серебряным прибором.

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

Полное дерево возможных вариантов выглядит так: (Слайд 6).

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

У рассмотренного нами дерева 4 основных ветви, каждая из которых делится на 3, каждая из вновь полученных делится на две ветви, а затем от каждой следующей идет одна ветвь. Число решений – это количество кольцевых ветвей, которое определяется как .

Рассуждая аналогично, получим

; ;

; ;

Анализируя полученные равенства, можно сказать, что при определении надо записать произведение трех множителей, первый из которых 7, а остальные на 1 меньше предыдущего, т.е.

Существует формула числа размещений из m элементов по n элементов в таком виде:

.

Найти: , , , , , , , , , , , , .

Задача 3.2.4. Сколькими способами можно выбрать три лица различные должности из 10 кандидатов?

Решение:  

Задача 3.2.5. В пятом классе изучают 11 предметов. Сколькими способами можно составить расписание занятий на понедельник, если в этот день недели должно быть 5 уроков по разным предметам?

Решение:  

Задача 3.2.6. В соревнованиях высшей лиги по футболу участвуют 18 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали между командами?

Решение:  

Задача 3.2.7. Сколько трехзначных чисел можно составить из цифр 2, 4, 6, 7, 9?

Решение:  

Задача 3.2.8. Сколько трехзначных чисел можно составить из цифр 0, 2, 4, 6, 7?

Решение:  

Задача 3.2.9. В профком избрано 9 человек. Из них надо выбрать представителя, его заместителя, секретаря и культорга. Сколькими способами это можно сделать?

Решение:  

Задача 3.2.10. Сколькими способами можно опустить 5 писем в 11 почтовых ящиков, если в каждый ящик опускают не более одного письма?

Решение:  

          3) Перестановки (без повторений).

Рассмотрим размещение АБ, БА, составленные из двух элементов А и Б и содержащие по два элемента. Они отличаются друг от друга только порядком данных элементов. Такие размещения называются перестановками из двух элементов. Их число обозначают символом . Оно рано , т.е.

Рассмотрим размещения АБВ, АВБ, БАВ, БВА, ВАБ, ВБА, составленные из трех данных элементов А, Б и В и содержащие по три элемента. Они отличаются друг от друга только порядком элементов. Такие размещения называются перестановками из трех элементов. Их число

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

Определение. Размещение из m элементов по m называются перестановками.

Число перестановок обозначается символом

Из определения следует . Например,

,

;

, .

Произведение натуральных чисел от 1 до n сокращенно обозначается n! (читается n факториал). По определению считается, что 0!=1.

Итак,

Значит,

, ,

,

Формулу числа перестановок из m элементов можно записать так:

Задача 3.3.1. Сколькими способами можно составить расписание на один день, если в этот день предусмотрено 6 уроков по 6 разным предметам?

Решение:  

Задача 3.3.2. Сколькими различными способами можно разместить на скамейке 10 человек?

Решение:  

Задача 3.3.3. Сколько различных шестизначных чисел, кратных 5, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что цифры в числе не повторяются?

Решение:  Чтобы число было кратным 5, цифра 5 должна стоять на последнем месте. Остальные цифры могут стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое количество шестизначных чисел, кратных 5, равно числу перестановок из 5 элементов, т.е.

.

Задача 3.3.4. Сколькими способами можно написать список учеников класса, в котором 20 человек и нет однофамильцев?

Решение:  

Задача 3.3.5. Сколько чисел можно составить из цифр 1, 2, 3, 4, 5, 6, если число начинается: с цифры 4; с цифр 4 и 5; с цифр 4, 5 и 6?

4) Сочетания (без повторений).

Определение. Сочетаниями называются соединения, содержащие по n элементов из числа m данных элементов и различающихся друг от друга по крайней мере одним элементом.

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

Число сочетаний из m элементов по n обозначается символом .

Для того чтобы найти способ вычисления числа сочетаний из m элементов по n элементов, запишем все размещения из четырех элементов по 3 так, чтобы в первой строке стояли все различные сочетания, а каждый столбец представлял одно и то же сочетание:

АБВ, АБД, АВД, БВД – это различные сочетания, их количество  .

Таких строк столько, сколько можно перестановок из трех элементов, т.е.

Итак, ; .

Можно предложить учащимся следующие задание: записать все размещения из трех элементов по 2 так, чтобы в первой строке стояли различные сочетания, а каждый столбец представлял одно и то же сочетание. Выполнив это, они придут к формуле:

, т.е. .

Анализируя два числовых равенства:

 и ,

Учащихся можем подвести к формуле:

.

Задача 3.4.1. На тренировках занимаются 12 баскетболистов. Сколько может быть организовано тренером разных стартовых пятерок?

Решение:  .

Задача 3.4.2. Сколько экзаменационных комиссий, состоящих из 7 членов можно образовать из 14 преподавателей?

Решение:  .

Задача 3.4.3. В чемпионате страны по футболу (высшая лига) участвует 18 команд, причем каждые две команды встречаются между собой дважды. Сколько матчей играется в течение сезона?

Решение:  В первом круге состоятся матча. Столько же матчей будет сыграно и во втором круге – всего 306 встреч.

Задача 3.4.4. В классе 30 учащихся. Сколькими способами можно выделить двух человек на дежурство, если: один из них должен быть старшим; старшего быть не должно?

Решение:  ; .

Задача 3.4.5. Для полета на Марс необходимо укомплектовать следующий экипаж космического корабля: командир, его первый помощник, второй помощник, два бортинженера (обязанности которых одинаковы) и один врач. Командная тройка может быть отобрана из числа 25 готовящихся к полету летчиков, два бортинженера – из числа 20 специалистов, в совершенстве знающих устройство космического корабля, и врач – из числа 8 медиков. Сколькими способами можно укомплектовать команду космического корабля?

Решение:  Командная тройка может быть укомплектована  способами, так как каждый из ее членов строго несет свои функции, пара бортинженеров - способами, врач -  способами.

Весь экипаж может быть укомплектован: способами.

Задача 3.4.6. Во взводе три сержанта  и 30 солдат. Сколькими способами можно выделить одного сержанта и трех солдат для патрулирования?

Решение:  Чтобы закрепить навыки вычисления числа сочетаний, можно решить следующие задачи.

Доказать:

; ; ; ; ; .

Вычислить: ; ; ; ; ; ; .

Отсюда получаем равенство: , , , , ,

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

Перед тем как рассматривать свойства числа сочетаний, закодируем сочетания из четырех элементов (А, Б, В, Г) по три следующим образом:

1 означает, что буква взята для данного сочетания;

0 означает, что буква не взята для данного сочетания.

Так, слово 1100 соответствует сочетанию АБВ, 1101 – сочетанию АБГ, 1011 – сочетанию АВГ, 0111 – сочетанию БВГ.

Чтобы найти все сочетания из четырех элементов по три, надо найти все слова из четырех букв (цифр), в которых три раза стоит 1 и один раз 0.

Задача 3.4.7. Из четырех элементов (А, Б, В, Г) составим все сочетания по два и закодируем по тому же принципу, который изложен выше.

Имеем:

 АБ,   АВ,    АГ,     БВ,   БГ,    ВГ

1100, 1010, 1001, 0110, 0101, 0011

Итак, число сочетаний из четырех элементов по два совпадают с числом слов из четырех букв (цифр), в которых два раза стоит 1 и два раза 0.

5) Основное свойство числа сочетаний.

Задача 3.5.1. Имеются пять ящиков, пронумерованных числами от 1 до 5. Сколькими способами в этих ящиках можно расположить три одинаковых шара, чтобы каждый ящик содержал не более одного шара?

Так как реальными ящиками и шарами пользоваться неудобно, то можно предложить делать это с помощью рисунков.

Например:

                                 1                2              3                4            5

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

Ш   П   Ш   Ш   П

П   Ш   Ш   Ш   П

Ш   Ш   Ш   П   П

П   Ш   П   Ш   Ш

Задача 3.5.1 сводится к тому, чтобы найти все слова из пяти букв, в которых трижды входит буква Ш и дважды буква П.

Если учащиеся воспользуются деревом возможных вариантов, то они придут к такому решению: (Слайд 7).

Существует 10 способов расположить три шара в пяти ящиках (не более одного шара в ящике), т.е. . Далее надо предложить учащимся заменить П на Ш, а Ш на П. Так определится количество способов, которыми можно расположить два шара в пяти ящиках (не более одного шара в ящике). Это количество равно 10. Итак, .

Вполне естественно поставить задачу о количестве расположений одного шара (четырех шаров) в пяти ящиках (не более одного шара я ящике). В этих двух случаях ситуация гораздо проще и учащиеся обнаружат пять возможных расположений.

Можно решить такую задачу. Сколькими способами в пяти ящиках можно расположить: пять шаров (не более одного шара в ящике); 0 шаров?

, это расположение соответствует слову ШШШШШ.

, нет никакого расположения нуля шаров в ящиках. Это соответствует слову ППППП.

Такое небольшое исследование приводит к следующей таблице:

Из этой таблицы видно:

, , .

На основании вышеизложенного можно составить еще две подобные таблицы:

, , .

, , , .

На основании этих таблиц запишем следующее важное свойство числа сочетаний:

.

Использование этого свойства существенно упрощает вычисления. Например,

;

;

 и т.д.