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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 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. Их число обозначают Виды комбинаторных задач и способы их решения - student2.ru .

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

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

Отсюда: Виды комбинаторных задач и способы их решения - student2.ru .

§ 3. Свойства чисел Виды комбинаторных задач и способы их решения - student2.ru

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

1°. Виды комбинаторных задач и способы их решения - student2.ru .

В самом деле, Виды комбинаторных задач и способы их решения - student2.ru .

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

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

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

Доказательство. Найдем по формулам Виды комбинаторных задач и способы их решения - student2.ru и Виды комбинаторных задач и способы их решения - student2.ru :

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

Виды комбинаторных задач и способы их решения - student2.ru . Тогда

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

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

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

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

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

                   
                 
               
             
           
         
. . . . . . . . . . .

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

Наши рекомендации