 Формулы комбинаторики

Задача. Пусть дано множество. Составить все его подмножества и упорядоченные подмножества (кортежи).

Решение.

Что дано? Дано множество, состоящее из четырех элементов.

Что нужно сделать? Составить все подмножества данного множества. Составить все упорядоченные подмножества данного множества.

Создадим таблицу, в которой выпишем все необходимые подмножества от самого маленького (Ø) до самого большого (самого множества).

Таблица 2

Подмножества	Упорядоченные подмножества (подмножества кортежей)
Ø	Ø
,,	, ,
,,	,, ,, ,
	, ,,,,
в составлении подмножеств, важен только их состав	в составлении упорядоченных подмножеств, важен порядокисостав

Таким образом, после рассмотрения данной задачи, можно ввести понятия «сочетание», «размещение» и «повторение».

Определение.

Сочетаниями (от англ. «combination» – комбинация) изnэлементов поkназываются все подмножества, множества состоящего изnэлементов, каждое из которых содержитkэлементов .

Определение.

Размещениями (от франц. «arrangement» – размещение) изnэлементов поkназываются все упорядоченные подмножества (кортежи с длиноюk), множества состоящего изnэлементов, каждое из которых содержитkэлементов .

Определение.

Перестановками(от англ. «permutation» – перестановка)kэлементов называются все его упорядоченные подмножества (кортежи с длиноюk), каждое из которых содержитnэлементов .

Тогда Таблица 2 принимает следующий вид:

Таблица 3

Подмножества		Упорядоченные подмножества (подмножества кортежей)
	Ø		Ø
	,,		, ,
	,,		,, ,, ,
			, ,,,,

Свойства сочетаний :

1. ;

2. (правило симметрии);

3. ;

4. (правило Паскаля);

5. .

Нередко встречаются задачи, требующие вычислить сочетания, размещения и перестановки, элементы которых в выбираемых подмножествах могут повторяться, а могут и нет, т.е. вычисления зависят от способа выбора (элементы взяли с повторением или без повторения) (см. Схема 3).

Схема 3. Формулы сочетания, размещения и повторения при различных способах выбора элементов

Решения задач всегда состоит из двух основных этапов: 1 этап – определение способа выбора элементов, 2 этап – выбор формул и правил.

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

Решение.

Что дано? Даны три цифры: 1, 2 и 3.

Что нужно сделать? Вычислить количество возможных способов создания трехзначных чисел.

1. Способ выборки – без повторения, т.к. цифры 1, 2, 3 различные.

2. Так как цифр – 3 и нужно вычислить количество способов составления трехзначных чисел, то имеем задачу на перестановку трех элементов без повторения:

.

Ответ. Возможно 6 способов записи трехзначного числа.

Пример 2. Сколько различных «слов» (под «словом» понимается любая комбинация букв) можно составить из букв слова «МАТЕМАТИКА»?

Решение.

Что дано? Слово «МАТЕМАТИКА».

Что нужно сделать? Вычислить количество возможных способов создания «слов» из букв слова «МАТЕМАТИКА».

1. Способ выборки – с повторением, т.к. в слове «МАТЕМАТИКА», некоторые буквы повторяются.

2. Всего в слове «МАТЕМАТИКА» 10 букв и их все необходимо переставить, значит это перестановка с повторением:

.

Ответ. Возможно 151200 способов создания «слов».

Пример 3. В юридической конторе работают 8 юристов. Сколькими способами можно распределить между ними пять дел (по одному на каждого)?

Решение.

Что дано? 8 юристов и 5 дел.

Что нужно сделать? Вычислить количество возможных способов распределения дел между юристами (по одному на каждого).

1. Способ выборки – без повторения, т.к. одному юристу не могут быть распределены два дела.

2. Так как из дел всего 5, а юристов – 8, то имеем дело либо с сочетанием, либо с размещением, но поскольку распределение дел идет следующим образом: вначале одно дело назначается юристу, затем другое – другому и т.п., значит это размещение без повторения.

.

Ответ. Возможно 6720 способов распределения дел юристам.

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

Решение.

Что дано? Даны пять цифр:1, 2, 2, 3, 4.

Что нужно сделать? Вычислить количество возможных способов создания трехзначных чисел.

1. Способ выборки – с повторением, т.к. цифра 2 может два раза попасть в число, например, 232.

2. Так как цифр – 5 и нужно вычислить количество способов составления трехзначных чисел, т.е. порядок цифр в числе важен, то имеем задачу на размещение с повторением:

.

Ответ. Возможно 125 способов записи трехзначного числа.

Пример 5. У мамы 6 яблока и 4 груши. Каждый день в течение недели она выдает Васе по одному фрукту. Сколькими способами это может быть сделано?

Решение.

Что дано? 6 яблока и 4 груши.

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

1. Способ выборки – без повторения, т.к. мама выдает только один фрукт.

2. Всего фруктов 10 и для мамы нет разницы, как она будет выдавать фрукты сыну: сначала яблоко, а затем грушу или наоборот, т.е. порядок следования фруктов не важен, значит эта задача на сочетание без повторения:

.

Ответ. Возможно 10 способов выдачи фруктов.

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

Решение.

Что дано? 4 вида цветков и 5 цветков в букете.

Что нужно сделать? Вычислить количество возможных способов создания букетов.

1. Способ выборки – с повторением, т.к. цветков 4, а их в букете должно быть 5, т.е. хотя бы один цветок в букете повториться дважды.

2. Так как всего 4 вида цветков, а нужно в букет взять 5 и для нас не важно с какого начнем брать цветки в букет, то эта задача на сочетание с повторением.

3. Всего фруктов 10 и для мамы нет разницы, как она будет выдавать фрукты сыну: сначала яблоко, а затем грушу или наоборот, т.е. порядок следования фруктов не важен, значит эта задача на сочетание без повторения:

.

Ответ. Возможно 56 способов создания букетов.

Формула сочетаний с повторениями неудобна для запоминания, поэтому представим эту формулу в другом виде: .