Конспект_лекций_по_курсу_Дискретная_математика

Пример 3.6. В почтовом отделении продаются открытки 10 видов. Подсчита-

ем, каким количеством способов можно купить 8 открыток разных видов. Так как порядок, в котором производится отбор открыток, не имеет значения, то рассмат-

риваемая расстановка является сочетанием из 10 объектов по 8. По формуле (3.7)

получаем C8 10! 45.

10 8! 2!

3.3.6. Определение числа k-сочетаний из элементов n типов с повторениями Имеются элементы n типов. Количество элементов каждого типа не ограни-

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

Для определения числа таких сочетаний (его принято обозначать Cnk ) поста-

вим в соответствие каждому такому сочетанию шифр, состоящий из нулей и еди-

ниц. Этот шифр будем составлять следующим образом: сначала напишем столько единиц, сколько в сочетании имеется элементов 1-го типа, затем напишем 0. После этого нуля напишем столько единиц, сколько в сочетании имеется элементов 2-го типа, после чего опять напишем 0 и так далее. Если элементы какого-либо типа в данном сочетании отсутствуют, то единицы записывать не будем, но 0 поставим.

Таким образом, в шифре будет k единиц и n – 1 ноль.

Нетрудно видеть, что каждое сочетание таким способом шифруется одно-

значно. С другой стороны, если мы имеем произвольный набор из k единиц и n – 1

нуля, то по нему можно однозначно составить k-сочетание из элементов n типов.

То есть между описанными шифрами и сочетаниями с повторениями существует взаимно однозначное соответствие, и число k-сочетаний с повторениями из эле-

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

Таким образом,

-61-

Сравнивая эту формулу с формулой для числа сочетаний без повторений, по-

лучаем: Cnk Cnk k 1 .

Пример 3.7. Рассмотрим задачу из примера 3.6. отбросив, однако, требова-

ние, чтобы все открытки были разными, т.е. теперь нам нужно выбрать 8 любых открыток из открыток 10 типов. Так как теперь в наборе могут быть и одинаковые открытки, то мы имеем дело с сочетаниями из объектов 10 типов по 8 элементов с

3.3.7. Рекомендации по решению комбинаторных задач

При решении комбинаторных задач нужно в первую очередь определить, к

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

как видно из вышеприведенных определений, следует обращать внимание на то,

имеет ли значение порядок следования элементов в расстановках, могут ли повто-

ряться в одной расстановке одни и те же элементы и, если расстановки упорядоче-

ны, то все ли возможные элементы (или типы элементов) используются в каждой из них. Процедура определения типа расстановки представлена в таблице 1.

Если расстановка упорядочена и известно количество способов, которыми можно выбрать каждый ее элемент, причем количество вариантов выбора данного элемента не зависит от того, как были выбраны предыдущие элементы, то для оп-

ределения числа таких расстановок можно воспользоваться правилом произведе-

ния (раздел 3.2).

Если не удается применить ни одну из рассмотренных выше формул к расста-

новке в целом, то следует проверить, нельзя ли множество расстановок, рассмат-

риваемых в задаче, разбить на взаимно не пересекающиеся подмножества, число расстановок в каждом из которых можно определить по известным правилам. Ес-

ли это сделать можно, то применяют правило суммы (раздел 3.2).

-62-

Пример 3.8. Сколько существует четырехзначных чисел, больших или рав-

ных 1000, в которых цифра 3 встречается ровно 1 раз?

Решение. Четырехзначные числа можно рассматривать как расстановки из элементов 10 типов (цифр 0, 1, 2, …, 9) по 4, причем порядок следования элемен-

тов имеет значение, и все цифры, кроме цифры 3, могут встречаться несколько раз.

Так как цифра 3 в каждой расстановке может встречаться только один раз и занимает при этом ровно одно из четырех возможных мест, то все множество рас-

становок можно разбить на 4 непересекающихся подмножества (в расстановках из i-го подмножества цифра 3 занимает i-ое место слева). Пусть цифра 3 стоит на первом месте слева, тогда остальные разряды могут быть заполнены любыми из оставшихся 9 цифр, т.е. могут рассматриваться как размещения с повторениями из элементов 9 типов по 3. По формуле (3.3) число таких размещений равно 93 = 729.

Пусть теперь цифра 3 стоит на втором, третьем или четвертом месте слева. Из трех свободных мест первое слева может быть заполнено любой из оставшихся 9

цифр, кроме 0, т.е. существует 8 способов заполнения этого места. На каждое из следующих двух мест можно поставить любую из 9 цифр. Так как количество ва-

риантов заполнения каждого из этих разрядов не зависит от того, как были запол-

нены остальные разряды, то можно воспользоваться правилом произведения: чис-

ло расстановок в каждом из этих подмножеств равно 8 9 9 = 648.

По правилу суммы общее число рассматриваемых расстановок равно

-63-

729 + 3 648 = 2673.

Пример 3.9. Сколькими способами можно расставить белые фигуры (2 коня, 2 слона, 2 ладьи, ферзя и короля) на первой линии шахматной доски?

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

менты повторяются, то эти расстановки являются перестановками с повторениями из элементов 5 типов. Их количество определим по формуле (3.6):

P (2, 2, 2,1,1) 8! 7! 5040. 2!2!2!1!1!

ЛИТЕРАТУРА

1.Судоплатов С. В., Овчинникова Е. В. Дискретная математика. – Новосибирск:

Изд-во НГТУ , 2010

2.Кузнецов О. П. Дискретная математика для инженера. – СПб.: Лань, 2007

3.Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер ,

2007

4.Плотников А. Д. Дискретная математика. – М.: Новое знание , 2006

5.Шапорев С. Д. Дискретная математика. – СПб.: БХВ-Петербург , 2006

6.Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.

7.Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975.

8.Кристофидес Н. Теория графов. – М.: Мир, 1978.

9.Ренин С.В. Сборник задач и упражнений по основам теории систем. – Новоси-

бирск: НЭТИ, 1985.

10.Ренин С.В. Спецглавы математики. Сборник задач и упражнений. – Новоси-

бирск: Изд-во НГТУ, 2000.

-64-