Комбинаторика в задачах (стр. 1 )

Составитель: , учитель математики

 

ОГЛАВЛЕНИЕ:

1.  Введение.	2
2.  Перебор возможных вариантов. Дерево возможных вариантов. Правило суммы и правило произведения.	3 - 5
3.  Размещения.	6 - 8
4.  Перестановки.	9 - 10
5.  Сочетания.	11 - 12
6.  Прояви смекалку!!!	13 - 18

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ:

	Внимательно прочитай и разберись
	Это нужно запомнить

Введение

В обыденной жизни нам нередко встречаются задачи, которые имеют несколько различных вариантов решения. Чтобы сделать правильный выбор, важно не упустить ни один из них. Для этого надо уметь осуществлять перебор всех возможных вариантов или подсчитывать их число. Задачи, требующие такого решения, называются комбинаторными. С аналогичными задачами люди сталкивались в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлеклись составлением магических квадратов, в которых заданные числа располагались так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же. В Древней Греции подсчитывали число различных комбинаций длинных и коротких слов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата и т. д. Комбинаторные задачи возникли и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т. д. Область математики, в которой изучают комбинаторные задачи, называется комбинаторикой.

КОМБИНАТОРИКА – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Наукой комбинаторика становится лишь в 18 веке - в период, когда возникла теория вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчиненных тем или иным условиям. После первых работ, выполненных в 18 веке итальянским ученым Дж. Кардано, Н. Тартальей, и Г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма. Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 году работу " Об искусстве комбинаторики", в которой впервые появляется сам термин "комбинаторный". Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру.

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

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

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

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

Правило суммы и правило произведения.

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

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

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

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

Других вариантов составления пар нет, так как все пары, в которые входит Федоров уже составлены. Итак, мы получили 6 пар: АГ, АС, АФ, ГС, ГФ, СФ, т. е. 3•2•1=6. значит, существует всего шесть вариантов выбора тренером пары теннисистов из данной группы.

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

Полный перебор вариантов:

12 21 31 12 21 31

12 23 32 или 13 23 32

11  22 33 (без повтора)

Эту же задачу можно решить используя способ, который носит название «Дерево возможных вариантов» (без повтора):

Двузначные

1 2 3

2 3 1 3 1 2 (одинаковое число веток)

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

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

Решение. На первый вопрос ответ очевиден. Коробку конфет можно выбрать пятью способами, коробку печенья – четырьмя способами. Следовательно, конфеты или печенье можно выбрать 5+4=9 способами.

Если мы составляем набор из коробки конфет и коробки печенья, то к каждой из пяти различных коробок конфет можно подобрать печенье четырьмя способами: к коробке конфет первого вида – 4 способа выбора печенья, к коробке конфет второго вида – опять 4 способа и т. д. Всего 5х4=20 различных способов.

Ответ: 9; 20.

Этот простейший пример показывает применение правил суммы и произведения. Как мы видим, союзу “или” в постановке задачи соответствует сложение, союзу “и” - умножение. Сформулируем теперь правила в общем виде.

Правило суммы. Если некоторый объект a можно выбрать m способами, а объект b – k способами (не такими, как объект a), то объект “a или b” можно выбрать (m + k) способами.

Правило произведения. Если объект a можно выбрать m способами, а после каждого такого выбора другой объект b можно выбрать (независимо от выбора a) k способами, то объект “a и b” можно выбрать m х k способами.

Задачи:

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

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

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

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

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

6.  В костюмерной танцевального кружка имеются зелёные и жёлтые кофты, а также синие, красные и чёрные юбки. Сколько можно из них составить различных костюмов?