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

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

Размещения. Пусть имеется множество, содержащее nэлементов. Каждое его упорядоченное подмноженство, содержащее по m элементов, называется размещением из nэлементов по m элементов.

Из определения вытекает, что  и что размещения из n элементов по m – это все m- элементы подмножества, отличающиеся составом элементов или порядком их следования.

Число размещений из n элементов по m элементов в каждом обозначают  и вычисляют по формуле

Число размещений из n элементов по m элементов в каждом равно произведению m последовательно убывающих натуральных чисел, из которых большее есть n .

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

Условились считать, что

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

Решение. Состав актива группы является упорядоченным множеством из 25 элементов по три элемента. Значит, искомое число способов равно числу размещений из 25 элементов по три элемента в каждом:

Или         

Пример 2. Перед выпуском группа учащихся в 30 человек обменялась фотокарточками. Сколько всего было роздано фотокарточек?

Решение. Передача фотокарточки одним учащимся другому есть размещение из 30 элементов по два элемента. Искомое число фотокарточек равно числу размещений из 30 элементов по два элемента в каждом:

Перестановки. Размещения из n элементов по n элементов называются перестановками из n элементов.

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

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

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

, т.е из цифр 1, 2, 3, 4 можно составить 24 четырехзначных числа (без повторений цифр).

Пример 4. Сколькими способами можно рассадить 10 гостей по десяти местам за праздничным столом?

Решение. Искомое число способов равно числу перестановок из десяти элементов

Сочетания. Пусть имеется множество, состоящее из n элементов. Каждое его подмножество, содержащее m элементов, называется сочетанием из n элементов по m элементов.

Таким образом, сочетания из n элементов по m  элементов – это все m-элементные подмножества n -элементного множества, причем различными подмножествами считаются только те, которые имеют неодинаковый состав элементов.

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

Число подмножеств по m элементов в каждом, содержащихся во множестве n элементов, т.е. число сочетаний из n элементов по m элементов в каждом, обозначают  и вычисляют по формуле

  или

Число сочетаний  обладает следующим свойством: Так,

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

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

Пример 6. Сколькими способами можно распределить 12 человек по бригадам, если в каждой бригаде по 6 человек?

Решение. Состав каждой бригады является конечным множеством из 12 элементов по 6. Значит, искомое число способов равно числу сочетаний из 12 элементов по 6 в каждом: