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

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

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

В данной работе мы рассмотрели примеры комбинаторных задач, решение которых, связанны с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств,

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

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

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

Решение:

1 способ: перечисление возможных вариантов, с помощью таблицы.

2 способ. Дерево возможностей.

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

3способ. Правило умножения заключается в том, что для того, чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытания А и число всех исходов испытания В, т. е. в нашей задаче имеется 3 элемента: первое, можно выбрать 3 раза, второе – 3 раза и третье – 2раза, получаем: 3х3х2=18

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

Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке. Число перестановок из n элементов обозначается символом Рn (Р из n элементов). Например.

Задача: в книжном шкафу на полке стоят 3 книги, эти книги можно переставить по разному:

Каждое из этих расположений называется перестановкой из трех элементов.

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

Рассуждаем так: на первое место можно поставить любой из трех элементов. Для каждого выбора первого элемента есть две возможности выбора из оставшихся двух элементов. Наконец, для каждого выбора первых двух элементов остается единственная возможность выбора третьего элемента. Значит, число перестановок из трех элементов равно: Р3= 3*2*1= 6 = 3!

Для произведения первых n натуральных чисел используют специальное обозначение: n! (читается «n факториал»).

Размещением из n элементов по k (k меньше или равно n) называется любое множество, состоящее из любых k элементов, взятых в определенном порядке из данных n элементов.

Обозначение: Ank ( читают: «А из n по k).

Рассмотрим задачу, чтобы показать разницу между перестановкой и размещением.

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

Решение: из трех элементов по два будут наборы (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).

Размещения считаются различными, если они отличаются самими элементами или порядком их расположения. Например: (1,2), (2,1), (1,3), (3,1) в нашем примере.

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

В результате получаем: = 3*2 = 6.

Решим задачу:

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

Решение: А84 = 8*7*6*5 = 1680

Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов.

Обозначение: Cnk (читают С из n по k).

Рассмотрим задачу, чтобы показать разницу между размещением и сочетанием.

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

Решение: из трех элементов (1;2;3) по два будут наборы (1,2),(1,3),(2,3).

В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания различны, если отличаются друг от друга хотя бы одним элементом. Например: (1,2),(1,3).

Для решения задачи, можно не выписывать все наборы, а воспользоваться правилом. В нашем примере, в каждом сочетании выполнимы все перестановки. Число таких перестановок равно Р2 = 2. В результате получим все возможные комбинации из 3 элементов по 2, которые отличаются либо самими элементами, либо порядком элементов, т. е. все размещения из 3 элементов по 2. всего мы получим 6 размещений. Значит если количество размещений разделить на количество перестановок, получим количество сочетаний из трех элементов по два.

= 6:2 = 3.

Занимательные квадраты.

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

Задача: Расположить натуральные числа от 1 до 9 в магический квадрат 3х 3:

В магическом квадрате 3х 3 магической постоянной 15 должны быть равны сумме трех чисел по 8 направлениям: по 3 строкам, 3 столбцам и 2 диагоналям. Так как число, стоящее в центре, принадлежит 1 строке, 1 столбцу и 2 диагоналям, оно входит в 4 из 8 троек, дающих в сумме магическую постоянную. Такое число только одно: это 5. Следовательно, число, стоящее в центре магического квадрата 3х 3, уже известно: оно равно 5.

Рассмотрим число 9. Оно входит только в 2 тройки чисел. Мы не можем поместить его в угол, так как каждая угловая клетка принадлежит 3 тройкам: строке, столбцу и диагонали. Следовательно, число 9 должно стоять только в клетке, примыкающей к стороне квадрата в ее середине. Из-за симметрии квадрата безразлично, какую из сторон мы выберем, поэтому впишем 9 над числом 5, стоящим в центральной клетке. По обе стороны от девятки в верхней строке мы можем вписать только числа 2 и 4. Какое из этих двух чисел окажется в правом верхнем углу и какое в левом, опять – таки не имеет значения, так как одно расположение чисел переходит в другое при зеркальном отражении. Остальные клетки заполняются автоматически. Проведенное нами простое построение магического квадрата 3х 3 доказывает его единственность.

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