Решение задач по теме Комбинаторика
материал по алгебре

ПРАКТИЧЕСКАЯ РАБОТА

 Тема: Комбинаторика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(а4,а3,а2,а1);(а2,а4,а3,а1);(а2,а3,а4,а1);(а3,а2,а1,а4);( а4,а2,а3,а1);(а2,а4,а3,а1); (а2,а3,а4,а1);(а2,а3,а1,а4);…;(а4,а1,а2,а3);(а1,а4,а2,а3);(а1,а2,а4,а3);(а1,а2,а3,а4).

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

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

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

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

Пусть имеется множество А=, состоящие из 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 элементов.