Учебник по дискретной математики. Д. Ушинского Дискретная математика
 Скачать 2.66 Mb.
|
|
Применим выведенную выше формулу для решения задач. Задача.Для того чтобы открыть камеру хранения, используется комбинация из 4 цифр (от 0 до 9), набираемая на 4 колесиках. Сколько различных комбинаций существует? Решение. Из условия задачи следует, что необходимо составить всевозможные комбинации по 4 элемента из данных 10. По формуле размещений с повторением получаем:  =104 = 10 000 вариантов. Задача.Сколько в n-ичной системе счисления натуральных чисел, записываемых ровно k знаками? Решение. Если допустить записи чисел, начинающиеся с нуля, то каждое k-значное число в n-ичной системе счисления можно рассматривать как размещение с повторениями, составленное из k цифр, причем цифры бывают n видов. Получаем, что количество чисел, имеющих такую запись, равно nk. Но натуральные числа не могут начинаться с нуля. Поэтому из полученного значения nk необходимо вычесть количество чисел, запись которых начинается с нуля. Если отбросить от этих чисел первую цифру – ноль, то получим (k–1)-значное число (быть может, начинающиеся с нуля). Таких чисел по формуле для вычисления количества размещений с повторениями существует nk-1. Значит общее количество k-значных чисел в n-ичной системе счисления равно nk – nk-1= nk(n – 1). Размещения без повторений Как изменится решение задачи о камере хранения, если известно, что цифры, набираемые на колесиках, различны. Решение. Вариантов выбора первой цифры 10 (от 0 до 9). Так как повторения быть не может, то вариантов выбора второй цифры всего 9. Аналогично для выбора третьей цифры остается 8 вариантов, для выбора четвертой – 7. По правилу произведения получаем, что всего комбинаций, в которых все числа различны, 10987=5 040. Данная задача относится к классу задач о размещении без повторений. Размещениями без повторений из n элементов по k называются всевозможные комбинации по k элементов, составленные из элементов данных n видов. При этом две комбинации считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Количество размещений без повторений обозначают  . Общее правило вычисления количества размещений: =n(n – 1)…(n – k+1)= .Доказательство. Действительно, на первом шаге можно выбрать любой из n имеющихся предметов. Если этот выбор уже сделан, то на втором шаге приходится выбирать из n – 1 предметов – ведь повторный выбор сделать уже нельзя. Точно так же на третьем шаге для выбора остается n – 3 предмета и т. д. Используя правило произведения, получим требуемую формулу. Задача. В первенстве России по футболу участвуют 17 команд. Разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами они могут быть распределены? Решение. Переформулируем задачу: Сколько существует комбинаций из 17 элементов по 3, если важны порядок элементов в комбинации, состав элементов и в комбинацию не могут входить элементы одного типа. (Повторения здесь быть не может – одна и та же команда не может получить и золотую и серебреную медаль.) Эта задача относится к задачам на размещения без повторения. По формуле получаем: медали могут распределиться  =171615=4 080 способами.Задача.Автомобильные номера некоторой страны состоят из 3 букв (все буквы различны) и четырех цифр (цифры могут повторяться). Сколько максимально машин может быть в этой стране, если в её алфавите 26 букв? Решение. Число комбинаций по 3 буквы из данных 26, при условии, что буквы не могут повторяться, определим с помощью формулы для вычисления количества размещений без повторений:  =262524=15 600.Число комбинаций по 4 цифры из данных 10, если в комбинацию могут входить одинаковые цифры, найдем с помощью формулы для вычисления количества размещений с повторениями: =104.Тогда по правилу произведения различных автомобильных номеров – =15600104=156106.Перестановки При составлении размещений без повторений из n элементов по k мы получали расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называют перестановками из n элементов или n-перестановками. Перестановками из n элементов называют всевозможные комбинации из n элементов, каждая из которых содержит все элементы по одному разу. Комбинации отличаются друг от друга лишь порядком элементов. Число n-перестановок обозначают через Рn. Общее правило вычисления количества перестановок: Рn=Аnn=n (n-1) (n-2) ...21=n! Рассмотрим несколько задач, решаемых с применением этой формулы. Задача. Сколькими способами можно расположить на книжной полке 6 томов детской энциклопедии? Решение. Так как на полке располагаем все 6 томов, то различные расположения отличаются только порядком, но не составом. По формуле перестановок имеем 6!=720. Задача. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга. Решение. На каждой вертикали и горизонтали должно стоять по одной ладье. Введем обозначения: перестановка (13256487) означает, что на первой горизонтали ладья стоит в первом поле, на второй – в третьем, на третьем – во втором и т.д. Таким образом, число искомых расположений равно количеству перестановок чисел 1, 2, 3, 4, 5, 6, 7, 8, то есть Р8=8!=40320. Задача. Сколько способов разбить 6 мужчин и 6 женщин на пары для танцев? Решение. Выстроим мужчин в одну линию в произвольном порядке. Пусть каждая женщина выбирает себе пару. Тогда количество способов разбиения на пары равно количеству способов переставить 6 различных предметов, то есть равно 6!. Задача. Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг? Решение. Если бы девушки стояли на месте, то получилось бы 7! способов. Так как танцующие кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении танцовщиц, необходимо считать одинаковыми. Из каждой перестановки можно получить еще шесть новых путем вращения. Значит, число 7! необходимо разделить на 7. Получаем 7!:7=6!=720 различных перестановок девушек в хороводе. Перестановки с повторениями Рассмотрим, как изменится количество перестановок, если некоторые из переставляемых предметов одинаковы. Задача. Сколько слов можно получить, переставляя буквы слова «март»? Сколько слов можно получить, если переставлять буквы слова «мама»? Решение Переставляя буквы слова «март» получим 24 различные перестановки, так как все переставляемые элементы различны. Если же некоторые переставляемые предметы одинаковы, то получается меньше перестановок – некоторые перестановки совпадают друг с другом. При перестановке букв слова «мама» имеем две пары одинаковых букв мм и аа. Сделаем их различными, дописав к одинаковым буквам различные индексы: м1а1м2а2. Рассмотрим все возможные перестановки: м1а1м2а2 м1м2а1а2 а1а2м1м2 м1а1м2а2 м1а1а2м2 а1м1м2а2 а1м1а2м2 м2а1м1а2 м2м1а1а2 а2а1м1м2 м2а1м1а2 м2а1а2м1 а1м2м1а2 а1м2а2м1 м1а2м2а1 м1м2а2а1 а1а2м2м1 м1а2м2а1 м1а2а1м2 а2м1м2а1 а2м1а1м2 м2а2м1а1 м2м1а1а1 а2а1м2м1 м2а2м1а1 м2а2а1м1 а2м2м1а1 а2м2а1м1 Получили 24 различные перестановки, которые разбиваются на четверки одинаковых слов, если убрать индексы при буквах «м» и «а». Значит, всего различных перестановок  .Общая задача формулируется следующим образом: Перестановками с повторениями из n1 элементов первого типа, n2 элементов второго типа, ... , nk элементов k-го типа называются всевозможные комбинации из этих элементов, каждая из которых содержит ni элементов i-го вида. Комбинации отличаются друг от друга лишь порядком элементов. Число перестановок с повторениями обозначают через Р(n1, n2, ..., nk). Общее правило вычисления количества перестановок с повторениями: Р(n1, n2, ..., nk)=.  .Доказательство. Если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. Возьмем, например, перестановку aa ... a bb ... b ... xx ... x, n1 n2 nk в которой сначала выписаны элементы первого типа, потом все элементы второго типа, …, наконец, все элементы k-го типа. Элементы первого типа можно переставлять n1! способами, это ничего не меняет. Точно так же ничего не меняют n2! перестановок элементов второго типа, ... , nk! перестановок элементов k-го типа. Перестановки элементов первого типа, второго типа и т. д. можно делать независимо друг от друга. По правилу произведения элементы перестановки можно переставлять n1!∙n2! ∙...∙nk! способами так, что она останется неизменной. То же самое верно и для любого другого расположения элементов. Поэтому множество всех n! перестановок распадается на части, состоящие из n1! ∙n2! ∙...∙nk! одинаковых перестановок каждая. Значит, число различных перестановок с повторениями, которые можно сделать из данных элементов, равно P(n1,n2,…,nk)= .Задача. Сколькими способами можно поставить в ряд 3 красных, 4 синих и 5 зеленых кубиков? Решение. По формуле перестановок с повторениями получаем: Р(3, 4, 5)=  .Задача. Слово – любая конечная последовательность букв русского алфавита. Сколько различных слов можно составить из слова КАСАТЕЛЬНАЯ, если необходимо использовать все буквы? Решение. В слове имеется 3 буквы А и еще 8 различных букв. По формуле перестановок с повторениями получаем: Р(1, 1, 1, 1, 1, 1, 1, 1, 3)=  =6 652 800.Сочетания До сих пор при составлении комбинаций из элементов различных типов нас интересовал порядок расположения элементов. Но некоторый класс задач приводит к составлению комбинаций, в которых порядок элементов совершенно не важен. Задача. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов? Решение. Это задача на размещения без повторений Ответ:  =543=60 способов составить флаг.Задача. Сколькими способами можно выбрать три краски из имеющихся пяти? Решение. В данном случае порядок выбора красок не важен. Поэтому количество способов выбора красок, полученное в предыдущей задаче, необходимо разделить на 3! – количество способов переставить выбранные краски. Ответ:  =10.Эта задача относится к классу задач о сочетаниях. Сочетаниями из n элементов по k называют всевозможные комбинации по k элементов, составленные из данных n элементов. Комбинации отличаются друг от друга составом, но не порядком элементов. Количество сочетаний из n элементов по k обозначают  . Формула для вычисления числа сочетаний получается из формулы для вычисления количества размещений. Составим сначала все k-сочетания из n элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получатся все k-размещения из n элементов, причем каждое только по одному разу. Элементы каждого k-сочетания можно переставить k! способами, а число этих сочетаний равно . Значит, справедлива формула  . Получаем  .Задача. Два филателиста хотят обменяться марками. У одного для обмена есть 7 марок, у другого – 5. Сколькими способами они могут поменять две марки одного на две марки другого? Решение. Первый филателист должен выбрать 2 марки из 7. Он может это сделать  способами. Второй должен выбрать 2 марки из 5. Он может это сделать  способами. По правилу произведения получаем,  способов совершить обмен.Задача. Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди них окажется ровно три туза? Решение. Необходимо выбрать трех тузов и семь «не тузов». Всего в колоде 4 туза. Поэтому выбрать из них 3 можно  способами. «Не тузов» в колоде 48. Выбрать из них 7 можно  способами. По правилу произведения получаем: = способов выбрать из колоды 10 карт так, что среди них будет ровно три туза.Свойства чисел Числа обладают рядом замечательных свойств. Эти свойства можно доказывать по-разному. Можно прямо воспользоваться формулой  . Однако часто удается получить доказательство из комбинаторных соображений.1 свойство: P(k, n-k) = Доказательство.  Комбинаторное доказательство. Поставим по порядку все n элементов, из которых составляют сочетания, и зашифруем каждое сочетание комбинацией из n нулей и единиц. Каждому k-сочетанию соответствует комбинация из к единиц и n – k нулей, и наоборот. Отсюда и следует, что число сочетаний из n элементов по k совпадает с числом перестановок с повторениями из к элементов одного вида (единиц) и n – k элементов другого (нулей). 2 свойство – свойство симметричности  Доказательство.  .Комбинаторное доказательство Если выбрать из n различных предметов некоторое k-сочетание, то останется дополнительное (n – k)-сочетание, а дополнительным к (n – k)-сочетанию является исходное k-сочетание. Таким образом, k-сочетание и (n – k) сочетание образуют взаимно дополнительные пары, поэтому число этих сочетаний одно и то же. |