МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

КУЙБЫШЕВСКОГО РАЙОНА «СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №2»

КОМБИНАТОРНЫЕ ЗАДАЧИ

КУЙБЫШЕВ - 2013 год

Оглавление

Введение …………………………………………………………………………………………........3

Что такое комбинаторика …………………………………………………………………….4-5
1. Понятие комбинаторики, комбинаторных задач ………………………….......…….……4
2. Историческая справка………………………………………………………………… …4-5
Классические задачи комбинаторики ………………………………………………………5-8

2.1. Общие правила комбинаторики…………………………………………………………5-6

2.2. Размещения…………………………………………………………………………….….6-7

2.3. Перестановки………………………………………………………………………………..7

2.4. Сочетания…………………………………………………………………………………....7

2.5. Треугольник Паскаля. Бином Ньютона………………………………………………….. .8

3. Сложные комбинаторные задачи ………………………………………………………..…8-11

3.1. Сочетания, размещения и перестановки без повторений ……………………..……….8-9

3.2. Перестановки с повторениями…………………………………………………………..9-10

3.3. Размещения с повторениями…………………………………………………….………...10

3.4. Сочетания с повторениями…………………………………………………………….10-11

3.5. Схема определения вида комбинации……………………………………….……………11

4. Примеры более сложных задач комбинаторики..……………………………………….11-12

Заключение…………………………………………………………………………….……………..13

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

Приложения………………………………………………………………………………………15-16

ВВЕДЕНИЕ

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

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

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

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

Цели:

более подробное изучение темы: «Комбинаторика. Комбинаторные задачи»;
применение полученных знаний к решению новых познавательных задач.

Задачи:

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

Основными источниками, которыми мы пользовались в своей работе - учебник и задачник Мордович А.Г., Семенова П.В.. Алгебра и начала анализа. Профильный уровень. 10 класс; Математика и информатика. Стефанова Н.Л., Будаев В.Д.. Учеб. пособие для студентов педагогических вузов; интернет.

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

ЧТО ТАКОЕ КОМБИНАТОРИКА

Понятие комбинаторики, комбинаторных задач

Толковый словарь определяет понятие комбинаторика – как раздел дискретной математики, изучающий всевозможные сочетания и расположения предметов (Ожегов С.И. , Шведова Н.Ю. Толковый словарь русского языка, Москва. 1999).

В Большой Российской энциклопедии даётся следующее определение: комбинаторика - раздел математики, в котором исследуется, сколько различных комбинаций (всевозможных объединений элементов), подчиненных тем или иным условиям, можно составить из заданного конечного множества объектов. Комбинаторика (от латинского слова combinare) означает - «соединять, сочетать». Впервые термин «комбинаторика» был введён в математический обиход немецким философом, математиком Лейбницем.

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

Историческая справка

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

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

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

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

Долгие времена комбинаторика развивалась в недрах арифметики, геометрии, алгебры. Однако как ветвь математики комбинаторика возникла только в XVII веке. А толчком к этому послужили азартные игры, прежде всего игра в кости. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н. Тарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б. Паскалю (1623-1662) и П. Ферма.

Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 году. Значительный вклад в развитие комбинаторики внес Л.Эйлер.

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

2. КЛАССИЧЕСКИЕ ЗАДАЧИ КОМБИНАТОРИКИ

2.1. Общие правила комбинаторики

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

Правило суммы: если объект А можно выбрать n способами, а объект В - k способами, то объект "А или В" можно выбрать n+k способами.

Пример. В ящике находятся 20 шаров: 5 белых, 6 черных, 7 синих и 2 красных. Сколькими способами можно взять из ящика один цветной шар?

Решение: здесь предполагается, что цветной шар - это синий или красный, поэтому надо применять правило суммы. Цветной шар можно выбрать 7+2=9 способами.

Правило произведения: если объект А можно выбрать n способами, а объект В независимо от него - k способами, то пару объектов "А и В" можно выбрать n·k способами.

Пример. Сколько может быть различных комбинаций выпавших граней при бросании двух игральных костей (игральная кость - это кубик, на гранях которого нанесены числа 1,2,3,4,5,6)? Решение: на первой кости может выпасть 1, 2, 3, 4, 5 или 6 очков, то есть всего будет 6 вариантов. Точно так же и на второй кости 6 вариантов. Получится всего 6 · 6 = 36 способов.

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

Пример. На книжной полке стоят 3 книги по алгебре, 4 книги по геометрии и 5 книг по литературе. Сколькими способами можно взять с полки одну книгу по математике? Решение: книга по математике - это книга по алгебре или по геометрии. Применяем правило суммы 3+4=7.

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

Решение: полный обед состоит из первого, и второго, и третьего блюд. По правилу произведения получаем 4 · 3 · 2 = 24 различных полных обеда.

2.2. Размещения

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

Например, из цифр 1, 2, 3, 4, 5 составляем трехзначные числа 123, 431, 524, ...и т.д. Это упорядоченные трехэлементные выборки, ведь 123 и 132 - разные числа. Другой пример: из 20 учащихся класса будем выбирать двух дежурных. Любая пара дежурных представляет собой неупорядоченную двухэлементную выборку, так как порядок их выбора не важен.

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

Из определения следует, что размещения отличаются друг от друга либо самими элементами, либо их порядком. Число размещений из n по m обозначается - .

- формула для вычисления числа размещений.

Найдем, например, число размещений из 7 по 3. Здесь , . Значит,

Пример. На пяти карточках написаны числа 1, 2, 3, 4, 5. Сколько различных трехзначных чисел можно из них составить?

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

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

Тогда получится преобразование формулы для вычисления числа размещений: . Вычислим например по этой формуле:

2.3. Перестановки

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

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

Приведем несколько примеров использования этой формулы:

Р₅ = 5! = 1· 2 ·3 · 4 ·5 = 120; Р₂ = 2! = 1· 2 = 2; Р₁ = 1! = 1.

Пример. Составить все размещения из трех букв А, В, С.

Решение: АВС, АСВ, ВАС, ВСА, СВА, САВ. Проверим по формуле: Р₃ = 1·2·3 = 6.

2.4. Сочетания

Определение: Сочетаниями из n элементов по m (mn) называются неупорядоченные m-элементные выборки из данных n элементов.

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

Например, ; ; ; .

Пример. Из 20 учащихся надо выбрать двух дежурных. Сколькими способами это можно сделать? Решение: надо выбрать двух человек из 20. Ясно, что от порядка выбора ничего не зависит, то есть Иванов-Петров или Петров-Иванов - это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2: . Ответ: 190 способами.

2.5. Треугольник Паскаля. Бином Ньютона

Составим таблицу значений для n, m = 0,1,2,3,4,5,6,7 - эту таблицу можно неограниченно продолжать вниз и вправо. Она называется треугольником Паскаля. Еще удобнее ее записывать в виде равнобедренного треугольника. (Приложение 1,2).

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

Нам знакомы формулы сокращенного умножения: (a + b)¹ = a + b;

(a + b) ² = a² + 2ab + b²; (a + b)³ = a³ + 3a²b + 3ab² + b³.

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

Пример. Вычислить без калькулятора:

Решение: сначала возведем в четвертую степень двучлен: .

Поэтому

3. СЛОЖНЫЕ КОМБИНАТОРНЫЕ ЗАДАЧИ

3.1. Сочетания, размещения и перестановки без повторений

Пример. Из 10 роз и 8 георгинов нужно составить букет так, чтобы в нем было 2 розы и 3 георгина. Сколькими способами это можно сделать?

Решение: выберем сначала из 10 роз 2 розы. Это можно осуществить способами. Мы используем сочетания, а не размещения, потому что порядок, в котором выбираются цветы, значения не имеет. Независимо от выбора роз 3 георгина из 8 можно взять способами. Тогда, по правилу произведения, 2 розы и 3 георгина можно выбрать способами:

. Ответ: 2520 способами.

Пример. Сколькими способами можно расставить 8 томов энциклопедии на книжной полке так, чтобы первый и второй тома: а) стояли рядом; б) не стояли рядом? Решение:

а) подсчитаем сначала число вариантов расстановки, когда первый и второй тома стоят рядом. Их можно считать за одну книгу. Тогда получается Р₇ = 7! перестановок. Но первый и второй тома можно соединить двумя способами: слева первый, справа второй том и наоборот. За счет этого количество вариантов удваивается и всего их будет 2·7! = 10080.

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

Итак, 8! - 10080 = 30240. Ответ: а)10080; б) 30240.

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

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

3.2. Перестановки с повторениями

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

Рассмотрим, например, слово "КВАНТ", состоящее из пяти различных букв. Если менять порядок букв, получим 5! =120 перестановок, т.е. 120 новых слов (словом будем называть любую комбинацию букв). Если проделать то же со словом "АТАКА", то перестановок будет меньше, потому что, меняя местами первую, третью и пятую буквы, будем получать то же самое слово. И, так как три буквы "А" можно менять местами способами, то и перестановок в слове "АТАКА" будет в 6 раз меньше.

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

состоящая из n элементов, причем, элемент а повторяется m₁ раз, элемент b – m₂ раз, и т.д., элемент с – m_k раз и m₁ + m₂ +...+ m_k = n. Перестановки в такой выборке, где есть одинаковые элементы, называются перестановками с повторениями и число перестановок с повторениями обозначается P_n(m₁, m₂,....,m_k). Из приведенных выше рассуждений следует формула:

Пример. У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение девяти дней она выдает сыну по одному фрукту. Сколько может быть вариантов такой выдачи?

Решение: обозначая фрукты по первым буквам названия, составим несколько вариантов выдачи: ЯЯГГГАААА, ААГГЯГААЯ, ГГГААЯЯАА. Эти выборки имеют один и тот же состав и отличаются только перестановкой элементов, поэтому применяем формулу числа перестановок с повторениями: . Ответ: 1260 вариантов.

3.3. Размещения с повторениями

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

Число размещений с повторениями из n по m обозначается . В отличие от обычных размещений, где mn, в размещениях с повторениями m и n могут быть любыми. Получим формулу числа размещений с повторениями (m-элементная выборка из n элементов). Применяя правило произведения, получим: .

Пример. Вдоль дороги стоят 6 светофоров. Сколько может быть различных комбинаций их сигналов, если каждый светофор имеет 3 состояния: "красный", "желтый", "зеленый"?

Решение: выпишем несколько комбинаций: КККЖЗЗ, ЗЗЗЗЗЗ, КЖЗКЖЗ... Мы видим, что состав выборки меняется и порядок элементов существенен (ведь если, например, в выборке КЖЗКЖЗ поменять местами К и Ж, ситуация на дороге будет другой). Поэтому применяем формулу размещений с повторениями из 3 по 6: . Ответ: 729 комбинаций.

3.4. Сочетания с повторениями

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

Число сочетаний с повторениями из n по m обозначается . В отличие от обычных сочетаний, где mn, в сочетаниях с повторениями m и n могут быть любыми. Для решения задач применяем формулу, выражающую число сочетаний с повторениями через обычное число сочетаний: .

Пример. В хлебном отделе имеются булки белого и черного хлеба. Сколькими способами можно купить 6 булок хлеба?

Решение: обозначая булки белого и черного хлеба буквами Б и Ч, составим несколько выборок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ, ... Состав меняется от выборки к выборке, значит, это уже не перестановки; порядок элементов несущественен, это - сочетания с повторениями из 2 по 6:

Сделаем проверку и выпишем все варианты покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Их действительно 7. Ответ: 7 вариантов.

3.5. Схема определения вида комбинации

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

Задача №1. В магазине игрушек имеются 7 одинаковых Чебурашек и 2 одинаковых Крокодила. Сколькими способами их можно расставить в один ряд на витрине?

Решение: обозначив игрушки первыми буквами названия, составим несколько комбинаций: КЧЧЧЧЧЧЧК, ЧЧЧКЧКЧЧЧ, ККЧЧЧЧЧЧЧ, ... Повторяются ли элементы в выборке? Да. Меняется ли состав? Нет, ведь каждая выборка состоит из семи букв "Ч" и двух букв "К". Следовательно, это перестановки с повторениями: . Ответ: 36 способами.

Задача №2. Имеются в неограниченном количестве палочки длиной 5,6,7,8,9,10 сантиметров. Сколько различных треугольников можно из них составить?

Решение: составим несколько выборок: (5,5,5); (6,7,8); (8,9,9)… Элементы повторяются, состав меняется, порядок не существенен. Согласно схеме, применяем формулу сочетаний с повторениями из 6 по 3: . Однако, здесь есть небольшой подвох: треугольника со сторонами 5,5,10 не существует, так что их будет 55. Ответ: 55 треугольников.

4. ПРИМЕРЫ БОЛЕЕ СЛОЖНЫХ ЗАДАЧ КОМБИНАТОРИКИ

Задача 1. Выпуклый многоугольник имеет 90 диагоналей. Сколько у него сторон?

Решение: обозначим количество сторон многоугольника через n, вершин у него тоже будет n. Соединим вершины попарно отрезками, которых будет . Среди этих отрезков будет n сторон, остальные - диагонали. Составим уравнение по условию задачи: . Отсюда получается квадратное уравнение: , корни которого n₁=15, n₂= - 12. По смыслу задачи подходит . Ответ: 15 сторон.

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

Решение: если участников - n человек, партий будет сыграно штук. Составим уравнение: , решив которое, найдем: . Ответ: 21 шахматист.

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

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

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

. Ответ: 2048 дорог.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

Большая Российская энциклопедия в 30 томах. Т.14, 2009. - 751 с.
Будаев В.Д., Стефанова Н.Л. Математика и информатика. Учеб. пособие для студентов педагогических вузов. М.: Высш.шк., 2004. - 349 с.
Гнеденко Б. В., Журбенко, И. Г. Теория вероятностей и комбинаторика //Математика в школе. 2007 - №6. – с. 67-70.
Дихтярь М., Эргле Е. Исторические комбинаторные задачи и комбинаторные модели. //Математика. 2007. - №14. – с. 23-24.
Мордкович А.Г., Семенов П.В. Алгебра и начала анализа. Учебник и задачник. 10 класс. М.: Мнемозина, 2007.