Виды комбинаторных задач и способы их решения

Пусть дано множество X = {5, 1, 2, 8}. Составим и решим 4 задачи.

Задача 1. Сколько трехзначных чисел можно составить из цифр 5, 1, 2, 8, если цифры в числах могут повторяться?

Решение. Три «окошечка» – ððð – символизируют три места, которые занимают цифры произвольного составляемого трехзначного числа.

На первое место (в качестве первой цифры) можно поставить любую из четырех цифр, на второе место тоже любую из четырех цифр и на третье место – тоже. Число способов выбора «тройки» цифр определяется по правилу произведения: п (Х ´ Х ´ Х) = 4 · 4 · 4 = = 4³ = 64.

С точки зрения комбинаторики в задаче 1 речь шла о составлении размещений с повторениями из 4 элементов по 3 и о подсчете их числа.

Определение. Кортеж длины k, составленный из элементов т элементного множества X, называют размещением с повторениями из т по k. Число таких кортежей обозначают .

Рассуждая аналогично, как в приведенной выше задаче, можно записать общую формулу:

.

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

Решение. Три «окошечка» ððð символизируют три места, которые занимают цифры трехзначного числа.

На первое место можно поставить любую из четырех цифр, на второе место любую из оставшихся трех цифр (после выбора первой цифры), на третье место – любую из оставшихся двух цифр.

Число способов выбора «тройки» цифр определяется по правилу произведения 4 · 3 · 2 = 24.

С точки зрения комбинаторики в задаче 2 речь шла о составлении размещений без повторений из 4 элементов по 3 и о подсчете их числа.

Определение. Упорядоченные k -элементные множества, составленные из элементов т элементного множества X, называют размещениями без повторений из т по k. Число таких размещений без повторений обозначают .

Рассуждая аналогично, как в приведенной выше задаче, можно записать общую формулу:

.

Задача 3. Сколько четырехзначных чисел можно составить из цифр 5, 1, 2, 8, если цифры в числе не повторяются?

Решение. Четыре «окошечка» ðððð символизируют места, которые занимают цифры четырехзначного числа. На первое место (в качестве первой цифры) можно выбрать любую из четырех цифр. Такой выбор может быть осуществлен четырьмя способами. Вторую цифру (после выбора первой) можно выбрать тремя способами, третью цифру – двумя способами, четвертую цифру – одним способом.

Число способов выбора «четверки» цифр определяется по правилу произведения так: 4·3·2·1=24.

С точки зрения комбинаторики в задаче 3 речь шла о составлении перестановок без повторений из 4 элементов и о подсчете их числа.

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

Рассуждая аналогично, как в приведенной выше задаче, можно записать общую формулу:

Р_т = т · (т – 1) · (т – 2) ·... · 1 = т!

Обозначение т! читается «m -факториал» и обозначает произведение всех натуральных чисел от 1 до т (или от т до 1).

Задача 4. Сколько подмножеств, содержащих три элемента, можно составить из элементов множества X = {5, 1, 2, 8}?

Решение. Составим всевозможные трехэлементные подмножества: {5, 1, 2}, {5, 1, 8}, {1, 2, 8}, {5, 2, 8}. Таких подмножеств оказалось 4. С точки зрения комбинаторики в задаче речь шла о составлении сочетаний из четырех элементов по три и подсчете их числа.

Определение. Неупорядоченные k элементные подмножества, составленные из элементов m -элементного множества X, называют сочетаниями из т элементов по k. Их число обозначают .

Пусть из элементов некоторого m элементного множества Х составлены все подмножества. Упорядочим всеми способами каждое из этих подмножеств, получим все упорядоченные k -подмножества m -множества Х.

Их число равно , но число k элементных подмножеств равно , а упорядочить каждое из них можно k! способами. Значит,  = · k!

Отсюда: .

§ 6. Свойства чисел

Числа , выражающие количество k –элементных подмножеств данного множества X, состоящего из т элементов, т.е. количество сочетаний без повторений из т элементов по k, обладают целым рядом свойств, устанавливающих различные соотношения между подмножествами множества X. Рассмотрим некоторые из свойств.

1°. .

В самом деле, .

Смысл этого утверждения состоит в следующем. Пусть множество X состоит из т элементов. Тогда каждому k элементному подмножеству А множества X соответствует однозначно определенное подмножество, содержащее (т – k)элементов. Оно получается из X удалением всех элементов подмножества А и называется дополнением к А в X. Любое (т – k)элементное подмножество в множестве X является дополнением одного и только одного k элементного подмножества. Значит, существует взаимно однозначное соответствие между k элементными и (т – k) элементными подмножествами, а потому число подмножеств этих двух видов одинаково. Это утверждение и выражается формулой .

2°. Для любых т и k, таких, что 1£ k £ т – 1,справедливо равенство

.

Доказательство. Найдем по формулам  и :

, . Тогда

.

Теоретико-множественный смысл этого равенства состоит в следующем. Пусть X состоит из т элементов. Выделим один из элементов, например, элемент а. Тогда все k элементные подмножества множества X разбиваются на классы: первый состоит из подмножеств, не содержащих элемент а, а второй из подмножеств, содержащих а. Все k элементные подмножества первого класса являются k элементными подмножествами множества Х \ { а } = Х'. Поскольку число элементов множества X' равно т – 1,то число его k элементных подмножеств равно .Найдем теперь число k элементных подмножеств второго класса. Все эти подмножества содержат элемент а. Если исключить из них этот элемент, то получатся (k – 1) элементные подмножества, не содержащие а и состоящие из элементов множества X'. Следовательно, число подмножеств второго класса равно числу (k – 1)элементных подмножеств множества Х', т.е. .

Поскольку каждое k элементное подмножество либо содержит элемент а, либо не содержит его, то оно принадлежит либо первому, либо второму классу. Значит, по правилу суммы получаем, что  всех k элементных подмножеств т элементного множества X равно .Поэтому . Эта формула позволяет вычислять значения , зная  и .

Заметим, что . Вычисления удобно записывать в виде бесконечной треугольной таблицы, называемой треугольником Паскаля[3].

					1
				1		1
			1		2		1
		1		3		3		1
	1		4		6		4		1
1		5		10		10		5		1
.	.	.	.	.	.	.	.	.	.	.

В строке под номером т (т = 0, 1, 2 …)таблицы по порядку стоят числа . При этом «стороны» этого равнобедренного треугольника состоят из единиц, поскольку . Чтобы получить , надо сложить числа и , которые располагаются в таблице строкой выше. Эти числа принято писать в верхней строке слева и справа от . Например, число 10 в пятой строке получено в результате сложения чисел 4 и 6, которые находятся в четвертой строке слева и справа от числа 10.

Вопросы и задания для самопроверки

1.Соответствие R между множествами X = {1, 3, 5, 7} и Y = {2, 4, 6} задано перечислением пар:{(1, 2), (3, 2), (5, 2), (5, 4), (7, 4), (7, 6)}.Покажите, что R Ì X ´ Y. Задайте перечислением пар соответствия обратное и противоположное данному.

2. Какой частный случай соответствия называется отношением?

3. Определите свойства отношения «равно» в множестве N натуральных чисел.

4. Почему в математике среди отношений выделили два класса: отношения эквивалентности и отношения порядка?

5. Какой частный случай соответствия называется отображением?

6. С каким видом отображений связаны понятия равномощности и счетности множеств?

КУРС 2 СЕМЕСТР