Методика обучения школьников основам комбинаторики, теории вероятностей и математической статистики в рамках профильной школы

Большинство учащихся 5-6 классов обучаются по учебникам «Математика», авторы Н.Я. Виленкин, В.И. Жохов, А.С. Чесноков, С.И. Шварцбурд. Учебники имеют некоторые возможности для реализации новой содержательной линии.

В учебнике Н.Я. Виленкина «Математика» для 5-го класса имеется немалое количество задач пяти типов: прикладные и математические задачи на составление комбинаций из нескольких элементов; перебор элементов заданного множества и выделение тех, которые подчиняются заданному свойству; задачи на выявление общего признака некоторого множества чисел, фигур; арифметические упражнения на вычисление рациональным способом. В учебнике для 6-го класса комбинаторных задач меньше.

Автор отмечает, что развитию комбинаторного мышления способствует также решение комбинаторных головоломок. К ним можно отнести задачи на переправы, задача «Ханойская башня»; кубик Рубика и другие.

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

Для изучения вероятностно-статистического материала при работе по учебникам «Алгебра, 7», «Алгебра, 8», «Алгебра, 9» авторов Ю.Н Макарычева, Н.Г. Миндюк, К.И. Нешкова, С.Б. Суворовой (под ред. С.А. Теляковского) предназначено учебное пособие для учащихся 7-9 классов общеобразовательных учреждений «Элементы статистики и теории вероятностей» (авторы Ю.Н. Макарычев, Н.Г. Миндюк) [10]. Учебный материал распределен между 7, 8 и 9 классами. Учащиеся знакомятся с простейшими статистическими характеристиками (среднее арифметическое, размах, мода, медиана), изучают элементы статистики и получают начальные представления о сборе и группировке статистических данных, составлении таблиц частот и относительных частот. Рассматриваются различные способы наглядного изображения результатов статистических исследований - построение столбчатых и круговых диаграмм, полигонов, гистограмм. Вводятся начальные понятия теории вероятностей. Учащиеся знакомятся с комбинаторным правилом умножения.

Изучение комбинаторики, математической статистики и теории вероятностей продолжается на старшей ступени средней общеобразовательной школы. В учебнике «Алгебра и начала анализа» для 10-11 классов общеобразовательных учреждений (авторы Ю.Н. Калягин, М.В. Ткачева, Н.Е. Федорова, М.И. Шабунин [9]) этот материал включен в отдельную главу «Элементы комбинаторики». Раскрываются следующие вопросы: комбинаторные задачи, правило умножения, перестановки, размещения, сочетания и их свойства, биноминальная формула Ньютона. Кроме того, все указанные учебные пособия для 7-9 классов содержат этот учебный материал.

В учебниках Никольского С.М. [12], [13], [14] [15] даются лишь определения различных соединений, формулы для их вычисления (6класс) и классическое определение вероятности (8класс).

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

1.2.2 Структура и содержание элективного курса «Основы комбинаторики, теории вероятностей и математической статистики» в профилях различных направлений

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

Раздел 1. Элементы комбинаторики

Исторические и занимательные комбинаторные задачи (фигурные числа, магические и латинские квадраты). Основные комбинаторные методы: перебор всех возможных вариантов (систематический перебор, перебор с ограничениями), полный граф, дерево вариантов (граф-дерево), таблица вариантов, правила произведения и суммы. Факториал. Перестановки. Размещения. Сочетания. Формулы для подсчёта числа перестановок, размещений и сочетаний. Треугольник Паскаля. Бином Ньютона. Комбинированные задачи.

Ученические проекты:

· «Из истории комбинаторики».

· «Задание для друга» (по бесформульным методам).

· «Бином Ньютона».

· «Комбинаторика вокруг нас».

Раздел 2. Элементы теории вероятностей

Испытания и события. Невозможные, достоверные и случайные события. Виды случайных событий (совместные и несовместные, равновозможные и неравновозможные, противоположные, независимые), действия над случайными событиями (сумма, произведение). Полная группа. Эксперименты и их исходы. Классическое определение вероятности. Решение вероятностных задач с помощью формул комбинаторики. Относительная частота. Статистическая вероятность. Геометрические вероятности. Теоремы сложения и умножения вероятностей. Формула полной вероятности. Вероятность гипотез, формула Бейеса. Формула Бернулли. Закон больших чисел.

Ученические проекты:

· Доклады об ученых, стоящих у истоков теории вероятности.

· «Парадоксы».

· «Кому нужна теория вероятностей?».

Раздел 3. Случайные величины

Случайная величина. Дискретная и непрерывная случайные величины. Закон распределения вероятностей ДСВ. Математическое ожидание ДСВ. Дисперсия ДСВ. Среднее квадратическое отклонение.

Ученические проекты:

· «Современные азартные игры».

· «Моделирование методом Монте-Карло».

Раздел 4. Элементы математической статистики

Предмет статистики. Основная задача и основной метод статистики. Статистическая информация и способы её представления: простой статистический ряд (выборка), таблицы частот, таблицы относительных частот, столбчатые диаграммы, полигоны частот, круговые диаграммы, гистограммы. Простейшие статистические исследования. Этапы статистических исследований. Опрос общественного мнения как пример сбора, обработки, представления и интерпретации данных. Статистические характеристики: среднее значение, мода, медиана, размах, выборочная дисперсия, выборочное среднее квадратичное отклонение. Определение линии регрессии для двумерных выборок.

Ученические проекты:

· «Развитие математической статистики».

· Статистическое исследование на заданную тему.

В процессе обучения учащиеся приобретают умения:

· подсчитывать количество всевозможных комбинаций элементов, образованных определённому правилу;

· решать задачи с помощью графов;

· определять типы случайных событий;

· вычислять вероятность события, пользуясь простейшими свойствами вероятности;

· проводить эксперименты со случайными исходами;

· извлекать информацию из таблиц и диаграмм, анализировать её;

· записывать исходные данные в таблицу, используя их составлять диаграммы;

· регистрировать результаты наблюдений и делать выводы;

· выполнять математические, процентные расчёты.

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

№	РАЗДЕЛ	ТЕМА ЗАНЯТИЯ	КОЛ-ВО ЧАСОВ
			Матема-тический профиль	Гумани-тарный профиль	Естествен-нонауч-ный профиль
1	Элементы комбинаторики	1. Комбинаторные задачи. Перебор всех возможных вариантов. 2. Подсчет вариантов с помощью графов, таблица вариантов. 3. Кортежи. Правила произведения и суммы. 4. Перестановки. 5. Размещения. 6. Сочетания. 7. Самостоятельная работа 8. Некоторые свойства сочетаний. 9. Свойство сочетаний =+ и треугольник Паскаля. 10. Бином Ньютона. 11. Решение задач. 12. «Комбинаторика вокруг нас» (итоговое).	1 2 2 2 2 2 1 2 1 2 3 2	1 1 1 1 1 2 1	1 1 1 1 1 2 1
Всего	23	8	8
2	Элементы теории ве-роятностей	1. Предмет теории вероятностей. События. 2. Виды случайных событий. 3. Эксперименты и их исходы. 4. Классическое определение вероятности. 5. Решение вероятностных задач с помощью формул комбинаторики. 6. Статистическая вероятность. 7. Геометрическая вероятность. 8. Теорема сложения вероятностей. 9. Теорема умножения вероятностей. 10. Следствия теорем сложения и умножения. 11. Формула Бернулли. Закон больших чисел. 12. Решение задач. 13. Контрольная работа. 14. «Кому нужна теория вероятностей?» (итоговое).	2 1 1 1 2 1 2 2 2 2 1 3 1 2	1 1 1 1 1 1 1 1 2 1 1	1 1 1 1 1 1 1 1 2 1 1
Всего	23	12	12
3	Случайные величины	1. Понятие случайной величины. Закон распределения вероятностей дискретной случайной величины. Математические операции над случайными величинами. 2. Числовые характеристики ДСВ. Математическое ожидание. Дисперсия ДСВ. Среднее квадратическое отклонение. 3. Решение ключевых задач. 4. Зачет.	1 1 2 3	1 1 1 2	1 1 1 2
Всего	7	5	5
4	Элементы математической статистики	1. Выборочный метод. 2. Числовые характеристики статистических рядов. 3. Статистические исследования. Этапы статистического исследования. 4. Определение линий регрессии для двумерных выборок. 5. Исследовательские проекты и их защита.	2 2 2 3 2	1 2 2 2	1 1 1 2 2
Всего	11	7	7
Итого	64	32	32

Таким образом, на изучение элективного курса по данной теме учащимся математического профиля отводится 64 часа (по 2 часа в неделю), гуманитарного и естественнонаучного - 32 часа (по 1 часу в неделю).

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

Глава 2. Методика обучения школьников основам комбинаторики, теории вероятностей и математической статистики в рамках профильной школы

2.1 Особенности преподавания в классах различных профилей

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

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

У учащихся математических классов преобладает абстрактно-логическое мышление. Также их мышление характеризуется:

· быстрым и широким обобщением (каждая конкретная задача решается как типовая);

· тенденциями мыслить свернутыми умозаключениями (при наличии очень четко логически обоснованной канвы);

· большой подвижностью мыслительных процессов, многообразием аспектов в подходе к решению задач, легким и свободным переключением от одной умственной операции к другой, с прямого на обратный ход мысли;

· стремлением к ясности, простоте, рациональности, экономичности решения.

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

Такие ученики отличаются хорошо развитыми пространственными представлениями. Однако при решении ряда задач они могут обходиться без опоры на наглядные образы (даже там, где задача наталкивает на это). В каком-то смысле логичность заменяет им «образность», они не испытывают трудностей при оперировании абстрактными схемами.

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

Больше всего трудностей возникает при организации обучения математике в гуманитарных классах. Это связано с некоторыми особенностями их познавательной деятельности.

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

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

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

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

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

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

Из форм работы на уроке они предпочитают объяснение учителем нового материала, лабораторные работы, деловые игры, выполнение индивидуальных заданий с привлечением научно-популярной литературы. Из методов работы выбирают коллективные методы, дискуссии.

Исходя из интересов и особенностей познавательной деятельности учащихся гуманитарных классов, можно дать некоторые советы по организации работы с ними:

· Изложение материала вести на индуктивно-практической основе: от конкретных жизненных ситуаций к теоретическому обобщению, а от него к применению.

· Необходимо помогать учащимся за деталями увидеть сущность понятия, приема или метода решения (доказательства), их структуру.

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

· Вырабатывать умения свертывать рассуждения, избегать многословности.

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

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

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

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

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

Закрепление теоретических знаний следует осуществлять в основном в ходе решения прикладных задач.

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

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

2.2 Методика обучения школьников основам комбинаторики, теории вероятностей и математической статистики в профильных классах

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

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

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

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

Предполагаются следующие формы организации обучения:

* индивидуальная, групповая, коллективная;

* взаимное обучение, самообучение, саморазвитие.

Занятия включают в себя теоретическую и практическую части, в зависимости от целесообразности - лекции, консультации, самостоятельную работу, творческую проектную работу.

Эффективность обучения отслеживается следующими формами контроля:

* самостоятельная работа;

* срезы знаний, умений в процессе обучения;

* итоговый контроль.

Итоговый контроль предусматривает:

I РАЗДЕЛ - Доклады учащихся по теме «Комбинаторика вокруг нас».

II РАЗДЕЛ - Контрольная работа.

III РАЗДЕЛ - Зачёт.

IV РАЗДЕЛ - Исследовательские проекты и их защита

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

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

Раздел 1. Элементы комбинаторики

Специального изучения этого раздела для гуманитарного и естественнонаучного профилей, на мой взгляд, не требуется. Достаточно восьми - девяти занятий, чтобы познакомить учащихся с понятием «комбинаторика», ее применением в различных областях знаний, рассмотреть основные комбинаторные методы, правила. По схеме определение - формула - пример дать понятия перестановок, размещений и сочетаний, провести итоговое занятие.

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

Комбинаторные задачи. Перебор всех возможных вариантов

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

В науке и практике часто встречаются задачи, решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются подобные задачи, называют комбинаторикой. Слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать». Методы комбинаторики находят широкое применение в физике, химии, биологии, экономике, теории вероятностей и других областях знаний.

Приведем примеры некоторых комбинаторных задач.

1) Сколькими способами можно расположить в электрической цепи 7 различных приборов?

2) Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из 5 языков: русского, английского, французского, немецкого, итальянского, на любой другой из этих 5 языков?

3) Вова точно помнит, что в формуле азотной кислоты подряд идут буквы H, N, O и что есть один нижний индекс - то ли двойка, то ли тройка. Сколько имеется вариантов, в которых индекс стоит не на втором месте?

4) Сколько разных типов гамет может дать гибрид, гетерозиготный по 3 независимым признакам?

5) Перечислить все трехзначные числа, в записи которых встречаются только цифры 1 и 2.

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

Таким образом, различают следующие типы комбинаторных задач:

· Задачи, в которых требуется перечислить все решения (пример 5).

· Задачи, состоящие в требовании выделить из всех возможных решений такое, которое удовлетворяет заданному дополнительному требованию (пример 3).

· Задачи, в которых требуется подсчитать число решений (пример 1, 2, 6, 4).

Процесс навыков подсчета комбинаторных объектов можно расчленить на три этапа в зависимости от времени обучения и методов подсчета:

- подсчет методом непосредственного перебора;

- подсчет с использованием комбинаторных принципов;

- подсчет с использованием формул комбинаторики.

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

Рассмотрим основные методы, используемые в решении комбинаторных задач.

Перебор всех возможных вариантов

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

Пример 1. Из группы теннисистов, в которую входят четыре человека - Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары?

Составим сначала все пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий). Получим три пары: АГ, АС, АФ.

Выпишем теперь пары, в которые входит Григорьев, но не входит Антонов. Таких пар две: ГС, ГФ.

Далее составим пары, в которые входит Сергеев, но не входит Антонов и Григорьев. Такая пара только одна: СФ.

Других вариантов составления пар нет, так как все пары, в которые входит Федоров, уже составлены.

Итак, мы получили 6 пар: АГ, АС, АФ, ГС, ГФ, СФ. Значит, всего существует 6 вариантов выбора тренером пары теннисистов из данной группы.

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

Тут же необходимо пояснить учащимся, что в данном примере нам не важен порядок выбора пары: Антонов и Григорьев или Григорьев и Антонов, и привести пример задачи, где учитывается порядок элементов в комбинации.

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

Если на матч пойдут Антон и Борис, то они могут занять места двумя способами: 1-е место - Антон, 2-е - Борис, или наоборот. Аналогично Антон и Виктор, Борис и Виктор. Таким образом, мы получили 6 вариантов: АБ, БА, АВ, ВА, БВ, ВБ.

Следующая система задач направлена на формирование умений учащихся систематическому перебору, составлению комбинаций с учетом и без учета порядка.

Задачи:

1. Перечислить знакомые виды четырехугольников.

2. В кафе предлагают два первых блюда: борщ и рассольник - и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из двух блюд, которые может заказать посетитель.

3. Сколько двузначных чисел можно составить, используя цифры 1, 2, 3, при условии, что цифра в числе не может повторяться? (перебор с ограничением).

4. (Устно) Важен или нет порядок в следующих выборках (комбинациях):

а) капитан волейбольной команды и его заместитель;

б) три ноты в аккорде;

в) «шесть человек останутся убирать класс!»;

г) две серии для просмотра из нового многосерийного фильма.

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

6. Стадион имеет 4 входа: A, B, C, D. Укажите все возможные способы, какими посетитель может войти через один вход, а выйти через другой. Сколько таких способов?

7. В магазине продают кепки трех цветов: белые, красные и синие. Кира и Лена покупают себе по одной кепке. Сколько существует различных вариантов покупок для этих девочек? Перечислите их.

В качестве домашнего задания можно предложить учащимся написать работу (сообщение, реферат, доклад) на тему «Из истории комбинаторики».

Подсчет вариантов с помощью графов. Таблица вариантов

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

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

Пример 1. Сколько различных трехзначных чисел можно записать с помощью цифр 1, 2, 3 при условии, что цифры в числе могут повторяться?

Перебор вариантов можно организовать следующим образом. Выписать все числа, начинающиеся с цифры 1 в порядке их возрастания; затем - начинающиеся с цифры 2; после чего - начинающиеся с цифры 3.

Таких комбинаций получим 27. При переборе легко было упустить какую-нибудь из них.

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

Рассмотрим два вида графов:

1. Граф-дерево (называют за внешнее сходство с деревом).

С помощью дерева проиллюстрируем проведенный перебор вариантов в примере 1.

На первом месте в трехзначном числе может стоять одна из цифр 1, 2 или 3; на втором и третьем местах - (при условии, что цифры могут повторяться) также любая из трех цифр.

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

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

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

Четырех друзей поместим в вершины графа и проведем все возможные ребра. В данном случае отрезки-ребра обозначают рукопожатия каждой пары друзей.

Из рисунка видно, что граф имеет 6 ребер, значит, и рукопожатий было сделано 6.

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

Пример 3. Записать всевозможные двузначные числа, используя при этом цифры 0, 1, 2 и 3. Подсчитать их количество N.

Для подсчета образующих чисел составим таблицу:

1-я цифра	2-я цифра
	0	1	2	3
1	10	11	12	13
2	20	21	22	23
3	30	31	32	33

N=3?4=12

Задачи:

1. По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовало 5 человек?

2. Перечислить все возможные цветовые сочетания брюк, свитера и ботинок, если в гардеробе имеются брюки трех цветов: серые, бежевые и зеленые; свитера двух расцветок: песочный и малиновый; ботинки двух цветов: черные и коричневые.

3. Одновременно происходят выборы мэра города и префекта округа. На должность мэра выставили свои кандидатуры Алкин, Балкин, Валкин, а на должность префекта - Эшкин, Юшкин, Яшкин.

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

б) В скольких вариантах будет кандидатура Эшкина?

в) В скольких вариантах фамилии кандидатов на должность мэра и на должность префекта состоят из разного числа букв?

г) Как изменятся ответы в пунктах а) и б), если учесть еще кандидата «против всех»?

4. Группа туристов планирует осуществить поход по маршруту Антоново - Борисово - Власово - -Грибово. Из Антонова в Борисово можно сплавиться по реке или дойти пешком. Из Борисова во Власово можно дойти пешком или доехать на велосипедах. Из Власова в Грибово можно доплыть по реке, доехать на велосипедах или дойти пешком.

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

б) Сколько всего вариантов похода могут выбрать туристы?

в) Сколько есть полностью не пеших вариантов?

г) Сколько вариантов похода могут выбрать туристы при условии, что хотя бы на одну из участков маршрута они должны использовать велосипеды?

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

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

Определиться в успешности усвоения данной темы поможет самостоятельное составление учащимися задач. Можно предложить им придумать так называемое «задание для друга» с использованием каждого из трех методов.

Кортежи. Правило произведения

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

Рассмотрим задачу про «Суеверного председателя» [33].

«Опять восьмерка!» - горестно воскликнул председатель клуба велосипедистов, взглянув на прогнутое колесо своего велосипеда. «А все почему? Да потому, что у меня членский билет № 888 - целых три восьмерки. И теперь не проходит и месяца, чтобы то на одном, то на другом колесе не появилась восьмерка. Надо менять номер билета! А чтобы меня не обвинили в суеверии, проведу-ка я перерегистрацию всех членов клуба и буду выдавать только билеты с номерами, в которые не входит ни одна восьмерка. Не знаю только, хватит ли на всех номеров - ведь у нас в клубе почти 600 членов. Неужели придется сначала выписать все номера от 000 до 999, а затем вычеркивать из них все номера с восьмерками?» Чтобы помочь председателю, нам нужно решить такую комбинаторную задачу (учащимся можно предложить ее сформулировать):

Сколько существует трехзначных номеров, не содержащих цифры 8?

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

Сначала найдем количество однозначных номеров, отличных от 8. Ясно, что таких номеров девять: 0,1,2,3,4,5,6,7,9. А теперь найдем все двузначные номера, не содержащие восьмерок. Их можно составить так: взять любой из найденных однозначных номеров и написать после него любую из девяти допустимых цифр. В результате из каждого однозначного номера получится 9 двузначных. А так как двузначных номеров было 9, то получится 9?9 = 9² двузначных номеров.

Итак, существует 9² = 81 двузначный номер без цифры 8. Но к каждому из этих номеров можно приписать справа любую из цифр 0,1,2,3,4,5,6,7,9 и получить трехзначный номер, не содержащий цифру 8. При этом получаются все трехзначные номера с требуемым свойством. В результате мы нашли 9²?9 = 9³ = 729 трехзначных номеров без восьмерок.

Если бы председатель клуба был еще суевернее и отказался и от цифры 0, поскольку она походит на вытянутое колесо, то он смог бы составить лишь 8³ = 512 трехзначных номеров и их уже не хватило бы на всех членов клуба.

С помощью этого примера вводятся понятие кортежа и правило произведения.

Кортежи. Номера, составленные из трех цифр, нельзя рассматривать как множество элементов. Во-первых, в номерах цифры могут повторяться (например, 775), а в множествах элементы не повторяются, во-вторых, в номерах важен порядок цифр (175 и 571 - совсем разные номера), а в множествах порядок элементов роли не играет. Поэтому, если мы хотим изучать такие объекты, как номера, или слова (в них тоже могут буквы повторяться, от перестановки букв слово меняется), нужно ввести новое математическое понятие, отличное от понятия множество.

Это новое понятие математики назвали кортежем (наряду со словом «кортеж» применяют названия «слово», «набор», «вектор», «конечная последовательность» и т.д.). Кортеж - французское слово, означающее торжественное шествие. И у нас иногда говорят «кортеж автомашин», «свадебный кортеж» и т.д. При этом кортеж автомашин может состоять из нескольких «Волг», нескольких «БМВ» и нескольких «Ауди». Если считать машины одной и той же марки неразличимыми, то получим, что в кортеже автомашин один и тот же элемент может повторяться несколько раз.

В математике кортеж определяют так. Пусть имеется несколько множеств X₁, …, X_k. Представим себе, что их элементы сложены в мешки, а мешки перенумерованы. Вытащим из первого мешка какой-нибудь элемент (то есть возьмем какой-нибудь элемент а₁ множества Х₁), затем вытащим элемент а₂ из мешка Х₂ и будем продолжать этот процесс до тек пор, пока из мешка Х_k не будет вытащен элемент а_k. После этого расставим полученные элементы в том порядке, в котором они появились из мешков (а₁, а₂, …, а_k). Это и будет кортежем длины k, составленным из элементов множеств X₁, …, X_k. Элементы а₁, а₂, …, а_k называют компонентами кортежа.

Два кортежа называют равными в том и только в том случае, когда они имеют одинаковую длину, а на соответствующих местах стоят одни и те же элементы.

Здесь учащимся можно дать индивидуальное задание: взять любое множество и составить из его элементов кортеж, при этом спросить их, почему он является кортежем, и сколько кортежей можно составить из этого множества?

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

Правило суммы. Если элемент а можно выбрать m способами, а элемент b можно выбрать n способами, причем любой выбор элемента a отличен от любого выбора элемента b, то выбор «a или b» можно сделать m + n способами. (Например, если на блюде лежат 7 яблок и 4 груши, то выбрать один плод можно 7+4=11 способами).

На языке теории множеств это правило формулируется следующим образом: Если пересечение конечных множеств A и B пусто, A?B=O, то число элементов в их объединении равно сумме чисел элементов множеств A и B:

A?B=O =>

Здесь целесообразно задать учащимся вопросы: А как будет сформулировано правило суммы для пересекающихся множеств A и B? в общем случае для конечного числа множеств?

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

Правило произведения. Возьмем несколько конечных множеств X₁, …, X_k, состоящих соответственно из n₁, …, n_k элементов, и найдем, сколько кортежей длины k можно составить из элементов этих множеств. Способ, которым мы решим эту задачу по сути дела будет тем же самым, каким было найдено число трехзначных номеров без восьмерок. Сначала найдем число кортежей длины 1, составленных из элементов множества Х_1. Ясно_, что их число равно n₁. Возьмем теперь один из этих кортежей (а₁) и припишем к элементу а₁ справа по очереди все элементы множества х₂.Получится n₂ кортежей длины 2, у которых первая координата равна а₁. Но вместо а₁ можно было бы взять любой другой элемент из Х₁. Поэтому получается n₁ раз по n₂ кортежа, а всего n₁• n₂ кортежей длины 2 или, как чаще говорят пар. Из каждой такой пары получим n₃ троек, приписав к ней по очереди все элементы множества Х₃, а всего n₁• n₂• n₃ троек. Продолжая этот процесс, получим, в конце-то концов, n₁• n₂• …• n_k кортежей длины k, составленных из элементов наших множеств.

Полученный результат является одним из важнейших в комбинаторике. На нем основан вывод многих формул комбинаторики. Его называют «правилом произведения». Сформулируем это правило так. Если элемент а₁ можно выбрать n₁ способами, после каждого выбора этого элемента следующий за ним элемент а₂ можно выбрать n₂ способами … после выбора элементов а₁, а₂, …, а_k-1 элемент а_k выбирается n_k способами, то кортеж (а₁, а₂, …, а_k) можно выбрать n₁ • n₂ • … • n_k.

Подсчитаем, например, сколько слов, содержащих 6 букв, можно составить из 33 букв русского алфавита при условии, что любые две стоящие рядом буквы различны (например, слово «корова» допускается, а слово «колосс» нет). При этом, разумеется можно писать бессмысленные слова. В этом случае на первое место у нас 33 кандидата. Но после того, как первая буква выбрана, вторую можно выбрать лишь 32 способами - ведь повторять первую букву нельзя. На третье место тоже 32 кандидата - первую букву уже можно повторить, а вторую - нельзя. Также убеждаемся, что на все места, кроме первого, имеется 32 кандидата. А так как число этих мест равно 5, то получаем ответ 33•32•32•32•32•32=1107396236.

Задачи на непосредственное применение комбинаторных правил произведения и суммы:

1. В отделе научно-исследовательского института работают несколько человек, причем каждый из них знает хотя бы один иностранный язык, 6 человек знают английский, 6 - немецкий, 7 - французский, 4 знают английский и немецкий, 3 - немецкий и французский, 2 - французский и английский, 1 человек знает все три языка. Сколько человек работает в отделе? Сколько из них знают только английский язык? Сколько человек знают только один язык?

2. Сколько чисел среди первых 100 натуральных чисел не делятся ни на 2, ни на 3, ни на 5?

3. Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт и марку для посылки письма?

4. Сколькими способами можно выбрать на шахматной доске черный и белый квадраты, не лежащие на одной горизонтали или одной вертикали?

5. Имеется 20 тетрадей в линейку и 30 тетрадей в клетку. Необходимо выбрать две тетради одного вида. Сколько способов выбора двух тетрадей возможно, если учитывается порядок выбора тетрадей?

Размещения. Перестановки. Сочетания

Эти занятия можно построить с использованием презентации (см. Приложение 1) по единой схеме: определение > вывод формулы (доказательство) > пример. По мере рассмотрения каждого из комбинаторных понятий целесообразно отработать с учащимися эти понятия на символическом материале. Для усвоения содержания понятия нужно рассмотреть упражнения по составлению объектов, относящихся к определенному комбинаторному понятию. Эти упражнения должны носить внутримодельный характер. Упражнения лучше давать на карточках. Систему упражнений и задач можно подобрать из [40], [42].

Самостоятельная работа

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

Вариант 1

1. Сколькими способами можно обозначить вершины данного треугольника, используя буквы A, B, C, D, E и F?

2. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать?

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

4. Сколько различных маршрутов может избрать пешеход, решив пройти 9 кварталов, из них 5 на запад и 4 на юг?

5. В магазине продают кепки трёх цветов: белые, красные и синие. Наташа и Лена покупают себе по одной кепке. Сколько существует различных вариантов покупок для этих девочек?

6. Каждая из 5 подруг собирается вечером пойти либо в кино, либо на каток. Сколькими различными способами эти пять подруг смогли бы провести вечер?

Вариант 2

1. Сколькими способами можно обозначить вершины куба буквами

A, B, C, D, E, F, G, K?

2. Сколькими способами можно разложить 12 различных деталей по трем ящикам?

3. Сколькими способами могут быть распределены первая, вторая и третья премии между 13 участниками конкурса?

4. В библиотеке Кате предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами она может выбрать из них 3 книги и 2 журнала?

5. Найти число различных способов, которыми можно записать в один ряд 6 плюсов и 4 минуса.

6. В списке класса для изучения английского языка 15 человек. Сколько существует вариантов присутствия (отсутствия) этих людей на занятии?

Некоторые свойства сочетаний [42]

Этот вопрос можно предложить учащимся в качестве самостоятельной работы.

I.

а) Составьте всевозможные сочетания по 2 элемента без повторений из элементов множества М={а, б, в, г, д}. Для каждого из составленных подмножеств выпишите дополнения - трехэлементные подмножества оставшихся элементов - и сравните число тех и других. Какой вывод можно сделать о числах и ?

б) Из n элементов некоторого множества составлены всевозможные k-элементные подмножества и соответствующие им дополнения -- (n-k) - элементные подмножества оставшихся элементов. Какой вывод можно сделать о сравнительной величине чисел и ?

в) Воспользуйтесь формулой подсчета числа сочетаний без повторений и докажите равенство =. Это равенство выражает одно из важных свойств сочетаний. Им удобно пользоваться для вычисления в случае k>n.

г) Не производя вычислений, выберите равные из следующих чисел: , , , , , , , , , , , , , .

д) Вычислите , , .

е) Множество М={а, б, в, г, д, е} разбейте всеми возможными способами на два подмножества так, чтобы в одно из них входило 2 элемента, а в другое - 4.

ж) Из 12 человек нужно составить 2 волейбольные команды по 6 человек в каждой. Сколькими способами это может быть сделано?

II. Докажите следующее свойство сочетаний:

+++…+=2ⁿ.

а) Возьмите множество М={а, b, с} из трех элементов и составьте k-элементные подмножества М /k=0, 1, 2, 3/.

Каждому подмножеству поставьте в соответствие последовательность из трех цифр - единиц и нулей - следующим образом: каждому из трех элементов а, b, с поставьте в соответствие 1, если он входит в подмножество, 0 - если он в подмножество не входит. Рассмотрите таблицу

Таблица 1.

Виды подмножеств	Число подмнож.	Подмножества	Последовательности из 1 и 0
Пустые			000
Одноэлементные		{a}, {b}, {c}	100, 010 ,001
Двухэлементные		{ab}, {ac}, {bc}	110, 101 ,011
Трехэлементные		{a, b, c}|	111

Число всех подмножеств множества М равно +++ и равно числу всех последовательностей длины три из единиц и нулей. Число таких последовательностей нетрудно подсчитать: каждое из трех мест в последовательности может быть занято 1 или 0, то есть двумя способами, а все три места - по принципу умножения - 222=2³ способами. Это число можно получить и по формуле подсчета числа размещений с повторением, таким образом,

+++=2³.

б) Проведите аналогичные рассуждения для множества из n элементов. Тогда какие изменения следует внести в таблицу? Сделайте вывод, результат запишите.

Свойство сочетаний =+ и треугольник Паскаля [42]

I. Для изучения следующего свойства сочетаний предварительно составим трехэлементные подмножества множества М={а, б, в, г, д}. Затем выберем из множества М любой элемент, например, «а» и разобьем все подмножества на два класса: не содержащие «а» и содержащие «а».

I класс: {б, в, г}, {б, в, д}, {б, г, д}, {в, г, д}

II класс: {а, б, в}, {а, б, г}, {а, б, д}, {а, в, г},

{а, в, д}, {а, г, д}.

Первый класс состоит из всевозможных сочетаний без повторений по три элемента из следующих четырех: б, в, г, д. Таких сочетаний . Каждое подмножество второго класса состоит из элемента «а» и двух элементов, выбираемых из множества следующих элементов: б, в, г, д. Очевидно, число таких подмножеств равно .

Подмножества I и II классов исчерпывают все трехэлементные подмножества множества М, что означает:

=+.

Аналогичными рассуждениями получите равенство:

=+.

Убедитесь в справедливости последнего равенства, воспользовавшись формулой подсчета числа сочетаний без повторений.

II. Составим таблицу значений при различных значениях n и k. В таблицу 2 занесем значения =1, =1, =1, =1, =2, =1. Заполните остальные строки таблицы, используя свойство сочетаний.

Займемся изучением таблицы 2.

Первые и последние элементы любой строки равны 1, так как ==1. Это равенство будем считать верным и при n=0 (пустое множество своим единственным подмножеством имеет самое себя).

Любой другой элемент таблицы 2 согласно свойству сочетаний, на основании которого составлена таблица, равен сумме двух элементов предшествующей строки: стоящего непосредственно над ним и стоящего над ним слева.

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

Исследованием свойств такой треугольной таблицы и применениями ее занимался выдающийся ученый Франции Блез Паскаль (1623 --1662). Поэтому рассматриваемую таблицу часто называют треугольником Паскаля. Хотя задолго до Паскаля этот треугольник встречался в работах итальянских и арабских математиков.

Отметим некоторые из свойств треугольника Паскаля.

1. Сумма чисел k-той строки равна 2^k: ранее было доказано, что

+++…+=2^k.

Таблица 2

	0	1	2	3	4	5	6	7	8	9	10	…
0	1											…
1	1	1										…
2	1	2	1									…
3	1	3	3	1								…
4	1	4	6	4	1							…
5	1	5	10	10	5	1						…
6	1	6	15	20	15	6	1					…
7	1	7	21	35	35	21	7	1				…
8	1	8	28	56	70	56	28	8	1			…
9	1	9	36	84	126	126	84	36	9	1		…
10	1	10	45	120	210	252	210	120	45	10	1	…
…	…	…	…	…	…	…	…	…	…	…	…	…

Числа каждой строки треугольника, равноудаленные от ее концов, равны между собой. Обоснованием этого свойства служит равенство

=.

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

Задания:

1. Сколько различных подмножеств имеет множество всех цифр?

2. Сколько различных делителей, включая 1, имеет число а)2•3•5•7•11? б) 195?

3. Сколько различных произведений, кратных 10, можно составить из множителей 2, 7, 11, 9, 3, 5?

4. С помощью свойства сочетаний =+ докажите равенство: +++…+=.

5. Пользуясь треугольником Паскаля, найдите числа , .

6. Напишите 11 строку треугольника Паскаля.

Бином Ньютона [42]

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

В процессе самостоятельной подготовки докладов учащиеся овладевают навыками работы с научно-популярной и справочной литературой.

Система итоговых задач

Блок задач должен содержать задачи на простое однократное применение какой-либо формулы, задачи, решаемые бесформульными методами, комбинированные задачи.

1. Имеется 5 видов конвертов без марок и 4 вида марок. Сколькими способами можно выбрать конверт с маркой для посылки и письма?

2. Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?

3. Сколькими способами можно выбрать на шахматной доске белый и черный квадраты, не лежащие на одной горизонтали или одной вертикали?

4. Сколько можно составить пятибуквенных слов из 7 гласных и 25 согласных букв, если гласные и согласные должны чередоваться?

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

6. Сколько четырехбуквенных слов можно составить из букв слова «кибитка»?

7. Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом?

8. Сколькими способами можно выбрать 3 краски из имеющихся 5 различных красок?

9. На школьном вечере присутствуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них 4 пары для танца?

10. Во скольких девятизначных числах все цифры различны?

11. Сколько четырехзначных чисел можно составить из цифр числа 123153?

12. Сколько существует семизначных телефонных номеров, в первых трех цифрах которых не встречаются 0 и 9?

13. Сколькими способами можно выбрать из натуральных чисел от 1 до 30 три натуральных числа так, чтобы их сумма была четной?

14. На прямой взято p - точек, а на параллельной ей прямой еще g - точек. Сколько существует треугольников, вершинами которых являются эти точки?

15. В комнате n лампочек. Сколько всего разных способов освещения комнаты, при которых горит ровно k лампочек?

16. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей?

17. Сколькими способами можно рассадить n гостей за круглым столом?

18. Имеется 10 различных книг и 15 различных журналов. Сколькими способами можно составить посылку из 3 книг и 5 журналов?

19. Сколько трехзначных чисел, оканчивающихся цифрой 3?

20. Сколько ожерелий можно составить из 7 различных бусин?

21. Сколькими способами можно разбить множество из 20 элементов на два подмножества так, чтобы одно содержало 3 элемента, а другое - 17?

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