Комбинаторика (практическая работа)

Инструкционная карта № 34

Тақырыбы/ Тема: Комбинаторика.

Мақсаты/ Цель:

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

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

3. Воспитание познавательной самостоятельности: развитие умения самостоятельно классифицировать, выполнять анализ, оценивать результаты.

Теоретический материал:

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

Множество В называется подмножеством множества А, если каждый элемент В принадлежит А.Запись: В( множество В является подмножеством множества А). Считают также , что пустое множество является подмножеством любого множества () и любое множество является подмножеством самого себя (АА). Каждое упорядоченное подмножество множества А называют размещением. Пусть множество А содержит n элементов. Часто возникает вопрос: сколько размещений по m элементов можно составить из n(mn) элементов множества А? Чтобы ответить на этот вопрос, докажем теорему: число размещений, состоящих из n элементов, взятых из m элементов, равно т.е. =n(n-1)(n-2)…(n-m+1).

Пример1. Число перемещений из 5 элементов по 3 равно

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

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

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

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

Часто приходится рассматривать упорядоченные множества , т.е. множества в которых , каждый элемент занимает своё , вполне определенное место. Упорядочить множество-это значить поставить какой –либо элемент множества на первое место, какой либо другой элемент- на второе место и.т.д. Упорядоченные множества принято иногда записывать в круглых скобках .

Упорядочить множество можно различными способами. Например, множество состоящие из трёх элементов a,b и c, можно упорядочить шестью способами(a,b,c,);(a,c,b);(b,a,c);(b,c,a);(c,a,b);(c,b,a).

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

Пример1. Если множество состоит из одного элемента а₁, то его можно, очевидно, упорядочить единственным способом , а именно (а₁). Итак, из одного элемента можно составить одну перестановку.

Пример2. Пусть имеются два элемента :а₁и а_2. Ясно, что из этих элементов можно составить только две перестановки: поставить а₂ перед а₁ или поставить а₂ после а₁:(а₂,а₁); (а₁,а₂). Итак, число перестановок из двух элементов равно 1.

Пример3. Пусть имеются три элемента: а₁,а₂ и а₃.Запишем сначала перестановки из двух элементов а₁и а₂ и в каждую из этих перестановок впишем элемент а₃ вначале на первое место, потом на второе место и , наконец, на третье -последние место. Получи шесть перестановок: (,а₃,а₂,а₁); (а₂,а₃,а₁); (а₂,а₁,а₃);(а₃,а₃,а₂);(а₁,а₃,а₂);(а₁,а₂,а₃). Итак, число перестановок из трех элементов равно

Пример4.Пусть имеются четыре элемента: а₁,а₂,а₃,а₄.Запищем все перестановки из трёх элементов а₁,а₂ и а₃(их число равно)

и в каждую из этих перестановок впишем элемент а₄ в начале на первое место, потом на второе, затем на третье и, наконец, на четвёртое- последние место). Получаем 24 перестановки:

(а₄,а₃,а₂,а₁);(а₂,а₄,а₃,а₁);(а_2,а₃,а₄,а₁);(а₃,а₂,а₁,а₄);( а₄,а₂,а₃,а₁);(а₂,а₄,а₃,а₁); (а₂,а₃,а₄,а₁);(а₂,а₃,а₁,а₄);…;(а₄,а₁,а₂,а₃);(а₁,а₄,а₂,а₃);(а₁,а₂,а₄,а₃);(а₁,а₂,а₃,а₄).

Итак, число перестановок из четырёх элементов равно

Теперь можно сформулировать теорему : число перестановок из n элементов равно произведению n первых натуральных чисел, т.е. P_n=(где P_n-число перестановок из n элементов). Произведение n первых натуральных чисел обозначают n! (читается «эн факториал»), например:

1!=1;2!=12;3!=123;4!=1234.

1. Сочетания.

Пусть имеется множество А=, состоящие из n элементов. Из этого множества можно составить подмножество, состоящие из m элементов (mn). Каждое подмножество состоящие из m элементов, содержащихся в множестве А из n элементов, называется сочетанием из n элементов по m . Число всех таких сочетаний обозначается через Сколько всех сочетаний по m элементов можно образовать из данных n элементов? Для ответа на этот вопрос докажем теорему: число сочетаний из n элементов по m равно .

Пример 1. Вычислить . Применяя формулу сочетаний, имеем =.

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

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

Практическая часть:

Контрольные вопросы:

1. Что такое n факториал? Его обозначение.

2. Дайте определение размещения и запишите формулу размещения из n элементов по m элементов.

3. Дайте определение перестановки и запишите формулу перестановки из n различных элементов.

4. Дайте определение сочетания и запишите формулы сочетания из n элементов по m элементов.