Введение в комбинаторику и теорию вероятностей

Землякова Ольга Владимировна, учитель математики
Клиндухова Анастасия Сергеевна, учитель математики
Осетрова Надежда Евгеньевна, учитель

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

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

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

Цели и задачи

- введение в комбинаторику, знакомство с основными понятиями: перестановки, размещения, сочетания;

- введение в теорию вероятностей (частота и вероятность, сложение и умножение вероятностей);

- коррекция базовых математических знаний, систематизация, расширение и углубление знаний;

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

- воспитание творческой личности, умеющей самореализовываться и интегрироваться в системе мировой математической культуры;

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

- развивать способности учащихся к математической деятельности;

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

Урок 1. “Престановки”

Цели урока:

- познакомить с понятием “комбинаторика”, привести примеры комбинаторных задач;

- ввести (повторить) понятие “факториал”;

- дать определение понятия “перестановка”;

- доказать равенство Рn=n!;

- решать задачи на перестановки.

Ход урока

1) Что такое комбинаторика, решение комбинаторных задач, исторические комбинаторные задачи.

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

Определение. Комбинаторика – это раздел математики, посвящённый задачам выбора и расположения предметов из различных множеств.

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

Пример 1. Дано три элемента a, b и c. Сколькими способами можно расставить эти элементы друг за другом?

Решение: abc, acb, bac, bca, cab, cba. Всего 6 различных способов.

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

1						3						5						7
3		5		7		1		5		7		1		3		7		1		3		5
5	7	3	7	3	5	5	7	1	7	1	5	3	7	1	7	1	3	3	5	1	5	1	3

Итого 24 числа: 135, 137, 153, 157, 173, 175, 315, 317, 351, 357, 371, 375, 513, 517, 531, 537, 571, 573, 713, 715, 731, 735, 751, 753. Такой способ решения называют деревом возможных вариантов.

Некоторые комбинаторные задачи решали ещё в Древнем Китае, а позднее – в Римской империи. Как самостоятельный раздел математики комбинаторика оформилась в Европе в XVIII веке в связи с развитием теории вероятностей.

В древности для облегчения вычислений часто использовались камешки. При этом, особое внимание уделялось числу камешков, которые можно было разложить в виде правильной геометрической фигуры. Так появились квадратные числа (1, 4, 16, 25, ...):

Были сконструированы и треугольные числа (1, 3, 6, 10, 15, ...):

Все составные числа древние математики представляли в идее прямоугольников размером m x n, выложенных из камней, где обязательно m 1 и n 1. Простые числа представляли в виде линий 1 х n. В связи с этим составные числа древние учёные называли прямоугольными, а простые – непрямоугольными числами.

2) Факториал.

Определение. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Обозначение n!

Для того, чтобы в различных формулах не делать исключения для числа 0, принято соглашение: 0! = 1.

Таблица факториалов от 0 до 10:

n	0	1	2	3	4	5	6	7	8	9	10
n!	1	1	2	6	24	120	720	5 040	40 320	362 880	3 628 800

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

В примерах 1 и 2 мы составляли различные комбинации элементов и чисел, переставляя их различными способами.

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

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

Число всевозможных перестановок из n элементов вычисляется по формуле:

P_n = n!

Доказательство:

Если n = 1, то P_n = 1! = 1 – верно.

Допустим, что P_k = k! – верно.

Докажем, что P_k+1 = (k + 1)! – тоже верно:

Мы имеем k + 1 элемент. На первое место можно поставить любой из них. Для каждого выбора первого элемента на второе место можно поставить один из оставшихся k элементов. Для каждого выбора первых двух элементов на третье место можно поставить один из оставшихся k – 1 элементов и т.д. В результате получим, что

4) Примеры решения задач.

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

Решение: P₈ = 8! = 40 320

Значит, существует 40 320 способов расстановки восьми участниц на восьми беговых дорожках. (Понятно, что решить эту задачу методом построения дерева возможных вариантов практически невозможно.)

Ответ: 40 320 способов.

Пример 2. Сколько различных четырёхзначных чисел можно составить из цифр 0, 1, 2, 3, причём в каждом числе цифры должны быть разные?

Решение: Количество четырёхзначных чисел, которые можно составить из 4-х различных цифр (без повторения цифр) равно числу перестановок из четырёх элементов P₄. Но в этом случае будут образовываться числа, начинающиеся с 0, что невозможно. И таких перестановок будет P₃. Следовательно, Р₄ – Р₃ = 4! – 3! = 18.

Ответ: 18 чисел.

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

Решение: Будем считать трёхтомник одной книгой (т.к. порядок книг в самом трёхтомнике возможен любой). Тогда у нас всего не 10 книг, а 8. Их можно расставить Р₈ способами. Но книги в трёхтомнике можно расставить Р₃ способами. Для каждой перестановки из 8-и элементов соответствует определённая перестановка из 3-х элементов. Следовательно, .

Ответ: 241 920 способов.

5) Задачи для самостоятельного решения (в классе и дома).

1). Сколькими различными способами могут сесть на скамейку

а) 5 человек;

б) 7 человек.

Решение: а) Р₅ = 5! = 120; б) Р₇ = 7! = 5 040.

Ответ: а) 120 способов; б) 5 040 способов.

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

Решение: Р₃ = 3! = 6.

Ответ: 6 флагов..

3). Сколькими способами можно расставить по этапам четырёх участниц эстафеты в беге 4 х 100 м?

Решение: Р₄ = 4! = 24.

Ответ: 24 способа.

4). Составьте всевозможные трёхзначные числа, в которых все цифры разные, используя лишь цифры:

а) 7, 5, 1; б) 2, 0, 9.

Решение:

а) Р₃ = 3! = 6 – всего 6 чисел: 751, 715, 571, 517, 175, 157.

7		5		1
5	1	7	1	7	5
1	5	1	7	5	7

б) Р₃ – Р₂ = 3! – 2! = 4 – всего 4 числа: 209, 290, 902, 920.

2		9
0	9	0	2
9	0	2	0

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

Решение: Р₄ = 4! = 24.

Ответ: 24 числа.

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

Решение: Р₄ = 4! = 24.

Ответ: 24 способа.

7). Из цифр 2, 3, 4, 7 составлены всевозможные четырёхзначные числа (без повторения цифр). Сколько среди этих чисел таких, которые:

а) начинаются с цифры 7;

б) не начинаются с цифры 4?

Решение: а) Р₃ = 3! = 6; б) Р₄ – Р₃ = 4! – 3! = 18.

Ответ: а) 6 чисел; б) 18 чисел.

8). Из цифр 1, 2, 0, 5, 6 составлены всевозможные пятизначные числа (без повторения цифр). Сколько среди этих чисел таких, которые:

а) кратны 4;

б) кратны 5?

Решение: а) признак делимости на 4: если две последние цифры числа делятся на 4, то и всё число делится на 4. Следовательно, кратны 4 будут числа ***12, ***16, ***20, ***56. Количество чисел, оканчивающихся на 12, 16 и 56: Р₃ – Р₂ = 3! – 2! = 4 (т.к. 0 не может стоять на первом месте). Количество чисел, оканчивающихся на 20: Р₃ = 3! = 6. Следовательно, .

б) Кратны 5 будут числа ****0: Р₄ = 4! = 24 и ****5: Р₄ – Р₃ = 4! – 3! = 18. Следовательно, 24 + 18 = 42.

Ответ: а) 18 чисел; б) 42 числа.

9). В автомашине 5 мест. Сколькими способами в этой автомашине могут разместиться 5 человек, если место водителя могут занять только двое из них?

Решение: Р₄ + Р₄ = 4! + 4! = 48.

Ответ: 48 способов.

10). Чтобы открыть сейф, нужно набрать шифр, содержащий определённую последовательность из цифр 1, 2, 3, 4, 5, 6, и другой шифр, содержащий последовательность из букв a, b, c, d, в которых буквы и цифры не повторяются. Сколько существует комбинаций, при которых сейф НЕ открывается?

Решение: (все возможные варианты минус один вариант, с помощью которого сейф можно открыть).

Ответ: 17 279 комбинаций.

11). Сколькими способами можно расставить на полке четыре книги по алгебре и три по геометрии, причём так, чтобы все книги по алгебре (в любом порядке) стояли рядом?

Решение: .