Элементы дискретной математики. К. Д. Ушинского Элементы дискретной математики Ярославль, 2005 па. Корнилов, ни. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие
 Скачать 0.81 Mb.
|
|
Доказательство Если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. Возьмем, например, перестановку aa ... a bb ... b xx ... x, n1 n2 n k в которой сначала выписаны элементы первого типа, потом все элементы второго типа, …, наконец, все элементы го типа. Элементы первого типа можно переставлять n 1 ! способами, это ничего не меняет. Точно также ничего не меняют n 2 ! перестановок элементов второго типа, ... , n k ! перестановок элементов го типа. Перестановки элементов первого типа, второго типа и т. д. можно делать независимо друг от друга. По правилу произведения элементы перестановки можно переставлять n 1 !·n 2 ! ·...·n k ! способами так, что она останется неизменной. Тоже самое верно и для любого другого расположения элементов. Поэтому множество всех n! перестановок распадается на части, состоящие из n 1 ! ·n 2 ! ·...·n k ! одинаковых перестановок каждая. Значит, число различных перестановок с повторениями, которые можно сделать изданных элементов, равно P(n 1 ,n 2 ,…,n k )= ! ! ! ! 2 Задача. Сколькими способами можно поставить вряд красных, 4 синих и 5 зеленых кубиков Решение. По формуле перестановок с повторениями получаем Р, 4, 5)= 720 Задача. Слово – любая конечная последовательность букв русского алфавита. Сколько различных слов можно составить из слова КАСАТЕЛЬНАЯ, если необходимо использовать все буквы Решение. В слове имеется 3 буквы Аи еще 8 различных букв. По формуле перестановок с повторениями получаем Р, 1, 1, 1, 1, 1, 1, 1, 3)= ! 3 ! 11 =6 652 800. Сочетания До сих пор при составлении комбинаций из элементов различных типов нас интересовал порядок расположения элементов. Но некоторый класс задач приводит к составлению комбинаций, в которых порядок элементов совершенно неважен. Задача 1. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов Решение. Это задача на размещения без повторений Ответ 3 5 A =5 ⋅4⋅3=60 способов составить флаг. Задача 2. Сколькими способами можно выбрать три краски из имеющихся пяти Решение. В данном случае порядок выбора красок неважен. Поэтому количество способов выбора красок, полученное в предыдущей задаче, необходимо разделить на 3! – количество способов переставить выбранные краски. Ответ ! 3 3 5 A =10. Эта задача относится к классу задач о сочетаниях. Сочетаниями из n элементов по k называют всевозможные комбинации по k элементов, составленные изданных элементов. Комбинации отличаются друг от друга составом, ноне порядком элементов. Количество сочетаний из n элементов по k обозначают Формула для вычисления числа сочетаний получается из формулы для вычисления количества размещений. Составим сначала все сочетания из n элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получатся все размещения из n элементов, причем каждое только по одному разу. Элементы каждого сочетания можно переставить k! способами, а число этих сочетаний равно k n C . Значит, справедлива формула k n k n A C k = ⋅! . Получаем Задача. Два филателиста хотят обменяться марками. У одного для обмена есть 7 марок, у другого – 5. Сколькими способами они могут поменять две марки одного на две марки другого Решение. Первый филателист должен выбрать 2 марки из 7. Он может это сделать 7 C способами. Второй должен выбрать 2 марки из 5. Он может это сделать 2 5 C способами. По правилу произведения получаем, 2 7 C ⋅ 210 ! 2 ! 3 ! 5 ! 5 ! 2 ! 7 2 5 = ⋅ ⋅ ⋅ = C способов совершить обмен. Задача Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди них окажется ровно три туза Решение Необходимо выбрать трех тузов и семь не тузов. Всего в колоде 4 туза. Поэтому выбрать из них 3 можно 3 4 C способами. Не тузов в колоде 48. Выбрать из них 7 можно 7 48 C способами. По правилу произведения получаем 3 4 C ⋅ 7 48 C = 6288 451 29 7 6 5 4 3 2 48 47 46 45 44 43 42 4 ! 41 ! 7 ! 48 ! 1 ! 3 ! 4 = ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ = ⋅ ⋅ ⋅ способов выбрать из колоды 10 карт так, что среди них будет ровно три туза. Свойства чисел Числа k n C обладают рядом замечательных свойств. Эти свойства можно доказывать по- разному. Можно прямо воспользоваться формулой )! ( ! ! k n k n C k n − ⋅ = . Однако часто удается получить доказательство из комбинаторных соображений. 1 свойство P(k, n-k) = k n C Доказательство. Комбинаторное доказательство. Поставим по порядку все n элементов, из которых составляют сочетания, и зашифруем каждое сочетание комбинацией из n нулей и единиц. Каждому сочетанию соответствует комбинация из к единиц и n – k нулей, и наоборот. Отсюда и следует, что число сочетаний из n элементов по k совпадает с числом перестановок с повторениями из к элементов одного вида (единиц) и n – k элементов другого (нулей. 2 свойство – свойство симметричности Доказательство. Комбинаторное доказательство Если выбрать из n различных предметов некоторое сочетание, то останется дополнительное (n – сочетание, а дополнительным к (n – сочетанию является исходное сочетание. Таким образом, сочетание и (n – k) сочетание образуют взаимно дополнительные пары, поэтому число этих сочетаний одно и тоже свойство – основное свойство k n k n k n C C C 1 Доказательство. k n k n k n C k n k n k n k n k n n n k k n k n k n k n k n k k n k n k n k n C C = − ⋅ = = − ⋅ − ⋅ − − ⋅ + − ⋅ = − − ⋅ − + − ⋅ − ⋅ = − − ⋅ − + − ⋅ − − = + − − − )! ( ! ! )! ( ! )! 1 ( )! 1 ( )! 1 ( )! ( ! )! 1 ( ) ( )! ( ! )! 1 ( )! 1 ( ! )! 1 ( )! ( )! 1 ( )! 1 ( 1 1 1 Комбинаторное доказательство. Составим сочетание из n элементов а, аи разобьем их на два класса. В первый из них войдут сочетания, содержащие элемент a n , во второй – не содержащие этого элемента. Если из любого сочетания первого класса откинуть элемента, то останется (к –1)- сочетание, составленное из элементов а, а, …, a n-1. Число таких сочетаний равно 1 Поэтому в первый класс входит 1 1 − − k n C комбинаций. Сочетания второго класса являются k- сочетаниями, составленными из элементов а, а, …,a n-1. Поэтому их число равно Поскольку любое сочетание принадлежит одному и только одному из этих классов, а общее число этих сочетаний равно k n C , то, используя правило сложения, приходим к искомому равенству. 4 свойство Комбинаторное доказательство. 2 n – число всех размещений с повторениями из элементов двух типов. Разобьем эти размещения на классы, отнеся в k-ый класс те, в которые входят k элементов первого типа и n–k элементов второго типа. Размещения го типа - это ничто иное, как всевозможные перестановки из k элементов первого типа и n–k элементов второго типа. Число таких перестановок равно P(k, n–k)=C(n, k). По правилу суммы общее число размещений всех классов равно n n k n n n C C C C + + + + + 1 0 . С другой стороны, это же число равно 2 n 5 свойство Комбинаторное доказательство. Выпишем все сочетания из n элементов а, аи сделаем следующее преобразование к сочетанию, не содержащему элемента, допишем его, а из сочетаний, куда оно входит, вычеркнем. Легко проверить, что при этом снова получаются все сочетания, ипритом по одному разу. Но при этом преобразовании все сочетания, имевшие четное число элементов, превратятся в сочетания, имеющие нечетное число элементов, и обратно. Значит сочетаний счетными нечетным количеством элементов одинаковое количество (пустое сочетание тоже входит в рассмотрение. Это и выражает данная формула. Задача. На окружности отмечено 11 точек. Сколько существует многоугольников с вершинами в отмеченных точках Решение. Первый способ. Существует 3 11 C треугольников с вершинами в отмеченных точках, 4 11 C – четырехугольников, 5 11 C – пятиугольников, … , 11 11 C – одиннадцатиугольников. Таким образом, по правилу суммы всего многоугольников 3 11 C + 4 11 C + 5 11 C +…+ 11 11 C . Из четвертого свойства следует, что это выражение равно 2 11 - 1 11 C - 2 11 C =1 982. Второй способ Любая из одиннадцати точек либо является вершиной рассматриваемого многоугольника, либо не является. Всего вариантов 2 11 . Но одна или две точки не могут составлять многоугольник. Остается 2 11 - 1 11 C - 2 11 C вариантов многоугольников с вершинами в отмеченных точках. Сочетания с повторениями. Задача. В кондитерском магазине продавались 4 сорта пирожных наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных Эта задача не является задачей на размещения с повторениями, так как порядок, в котором укладывают пирожные в коробку, несуществен. Поэтому она ближе к задачам на сочетания. Но от задач на сочетания она отличается тем, что в комбинации могут быть повторяющиеся элементы. Такие задачи называют задачами на сочетания с повторениями. Чтобы решить задачу, поступим следующим образом. Зашифруем каждую покупку с помощью нулей и единиц. Сначала напишем столько единиц, сколько куплено наполеонов. Потом, чтобы отделить наполеоны от эклеров, напишем нуль, затем – столько единиц, сколько куплено эклеров, и т. д. Например, если куплено 3 наполеона, 1 эклер, 2 песочных и 1 слоеное пирожное, то получим такую запись 1110101101. Ясно, что разным покупкам соответствуют разные комбинации из 7 единиц и 3 нулей. Обратно, каждой комбинации 7 единиц и 3 нулей соответствует какая-то покупка. Таким образом, число различных покупок равно числу перестановок с повторениями, которые можно составить из 7 единиц и 3 нулей. А это число равно P(7,3)=120. К тому же самому результату можно было прийти и другим путем, а именно расположим в каждой покупке пирожные в таком порядке наполеоны, эклеры, песочные и слоеные, а потом перенумеруем их. Но при нумерации будем к номерам эклеров прибавлять 1, к номерам песочных – 2, к номерам слоеных – 3. К номерам наполеонов ничего прибавлять не будем. Например, пусть куплено 2 наполеона, 3 эклера, 1 песочное пирожное и 1 слоеное. Тогда эти пирожные нумеруются так 1, 2, 4, 5, 6, 8, 10. Ясно, что самый большой номер может быть 10, самый маленький – 1, а кроме того, ни один из номеров не повторяется, причем они образуют возрастающую последовательность. Обратно, каждой возрастающей последовательности из 7 чисел соответствует некоторая покупка. Например, последовательность 2, 3, 4, 5, 7, 8, 9 соответствует покупке из 4 эклеров и 3 песочных пирожных. Чтобы убедиться в этом, надо отнять от заданных номеров числа 1, 2, 3, 4, 5, 6, 7. Мы получим числа 1, 1, 1, 1, 2, 2, 2. Номы прибавляли к номерам эклеров, а 2 – к номерам песочных. Отсюда, общее число покупок равно числу возрастающих последовательностей из 7 чисел от 1 до 10. А число таких последовательностей равно C(10,7)=120. Сочетаниями с повторениями из n элементов по k называют всевозможные комбинации, составленные из элементов n видов по k элементов в каждой. Комбинации считаются различными, если они отличаются составом, ноне порядком входящих в них элементов. В комбинацию могут входить элементы одного вида. Количество сочетаний с повторениями из элементов по k обозначают k n C . Общее правило вычисления количества сочетаний с повторениями Доказательство Зашифуем каждую комбинацию с помощью нулей и единиц для каждого типа напишем столько единиц, сколько предметов этого типа входит в комбинацию, а предметы различных типов отделить нулями. При этом число единиц будет k, а число нулей – n–1. Различным комбинациям будут соответствовать различные перестановки с повторениями из k элементов первого вида и n–1 элементов второго вида, а каждой перестановке с повторениями – своя комбинация. Итак, Встречаются задачи, в которых на сочетания с повторениями накладывается дополнительное условие, например, когда в комбинацию обязательно должны входить элементы r фиксированных типов, где r≤n. Эта задача легко сводится к уже решенной. Для того чтобы обеспечить присутствие заданных r типов, возьмем с самого начала по одному элементу каждого такого типа. Тем самым в сочетании окажутся заняты r мест. Поэтому ответом на задачу будет число r k r k n r k n C C − − − + − = 1 . В частности, если требуется, чтобы в каждом сочетании был элемент каждого из типов (n≤k), то получится n k k C − −1 Задача. Сколько существует различных бросаний двух одинаковых кубиков Решение. Переформулируем задачу. Всего при подбрасывании одного кубика возможны шесть ситуаций – имеем предметы шести различных типов. Подбрасывают два кубика, следовательно, изданных шести типов предметов необходимо выбрать два, причем нас не интересует порядок выбора, и допускается выбор одинаковых предметов. Таким образом, это задача на сочетания с повторением. По формуле для вычисления количества сочетаний с повторением имеем 21 2 7 2 1 2 6 2 6 = = = − + C C C различных бросаний двух одинаковых кубиков. Комбинаторика разбиений Многим комбинаторным задачам можно придать вид стандартной схемы. В этой схеме объекты (предметы) помещаются в ящики. Из-за наложения различных ограничений получаются различные задачи. Рассмотрим некоторые из них. Имеется n 1 предметов одного сорта, n 2 – другого, ... , n k – го сорта. Сколькими способами можно разложить их в два ящика Так как в каждый ящик может попасть от 0 до n i предметов го сорта (во второй все оставшиеся, по правилу произведения получаем (n 1 +1)·(n 2 +1)·...·(n k +1) способов раскладки. Задача. Двое ребят собрали 10 ромашек, 15 васильков и 14 незабудок. Сколькими способами они могут разделить эти цветы? Решение. Необходимо 10 предметов одного вида, 15 – второго и 14 – третьего разложить в два ящика. Применяя рассуждения, аналогичные приведенным выше, получаем 11 ⋅16⋅15=2460 способов раздела цветов. Следствие 1. Если все предметы различны (n 1 =n 2 =...=n k =1), то их можно разложить 2 k способами. Следствие 2. Если в каждый ящик нужно положить не менее s i предметов го сорта, то получим формулу (n 1 -2s 1 +1) ⋅ (n 2 -2s 2 +1) ⋅...⋅ (n k -2s k +1). Даны n различных предметов и k ящиков. Надо положить в первый ящик предметов, во второй – n 2 , ..., в k-ый – n k , где n 1 +...+n k =n. Сколькими способами можно сделать такое распределение, если не интересует порядок предметов в ящике Выложим все предметы в один ряд. Это можно сделать n! способами. Первые предметов положим в первый ящик, вторые n 2 предмета – во второй ящик, …, k-ые n k предметов – в к-ый ящик. Так как нас не интересует порядок предметов в ящике, то любая перестановка первых n 1 предметов не меняет результат раздела. Точно также его не меняет любая перестановка вторых n 2 предметов, ..., k-ых n k предметов. По правилу произведения получаем n 1 ! ⋅n 2 ! ⋅...⋅n k ! перестановок, не меняющих результата раздела. Таким образом, n! перестановок делятся на группы по n 1 ! ⋅n 2 ! ⋅...⋅n k ! перестановок в каждой группе, причем перестановки из одной группы приводят к одинаковому распределению предметов. Следовательно, число раздела предметов равно ! ! ! ! 2 1 k n n n n ⋅ ⋅ ⋅ =P(n 1 ,...,n k ). Задача. При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать Решение. Переформулируем задачу необходимо разложить 28 предметов в 4 ящика по 7 предметов в каждый, причем порядок предметов в ящике неважен. Получаем способов распределения костей домино. Можно было рассуждать другим способом. Первый игрок выбирает себе 7 костей из 28, это можно сделать 7 28 C способами. Второму необходимо выбрать 7 костей из оставшихся 21, это можно сделать 7 21 C способами. Третьему 7 из 14 – 7 14 C способов. А четвертый заберет оставшиеся. По правилу произведения получаем 7 14 7 21 Даны n различных предметов и k одинаковых ящика. Надо положить в каждый ящик n 1 предметов, где n 1 = k n . Сколькими способами можно сделать такое распределение, если не интересует порядок предметов в ящике, и все ящики одинаковы Задача отличается от предыдущей только тем, что ящики не пронумерованы. Так как k ящиков можно переставить k! способами, то полученный в предыдущей задаче результат необходимо разделить на k!. Всего k n k n ) ! ( ! ! 1 ⋅ способов распределения. Задача. Сколькими различными способами можно разделить 8 книг на 4 бандероли по 2 книги в каждой Решение. Если бы интересовал порядок бандеролей, то существовало бы 4 ) ! 2 ( ! 8 способов распределения книг. Так как неважно, в каком порядке будут отправлены бандероли, то полученное число необходимо поделить на 4!. Итого ! 4 ) ! 2 ( ! 8 4 ⋅ способов разделить 8 книг на 4 бандероли по 2 книги. Сколькими способами можно разложить n одинаковых предметов в k ящиков Выложим все предметы в один ряд, добавим к ним k–1 одинаковых разделяющих предмета. Переставим всеми возможными способами n данных одинаковых предметов и k–1 разделяющих. Каждая такая перестановка определяет один из способов распределения. А именно предметы, расположенные до первого разделителя, положим в первый ящик, предметы, расположенные между первыми вторым разделителем, – во второй ящики так далее, предметы расположенный после k–1 разделителя, – в k ящик. По формуле перестановок с повторениями число таких перестановок равно P(n, k-1)= 1 1 − − + k k n C . Значит, всего имеем 1 1 − − + k k n C способов разложить n одинаковых предметов в k ящиков. Задача. Трое ребят собрали с яблони 40 яблок. Сколькими способами они могут их разделить, если все яблоки считаются одинаковыми (то есть нас интересует, сколько яблок получит каждый, а не какие именно Решение. Добавим два разделяющих предмета, тогда получаем Р, 2)=780 способа разделить яблоки. Следствие 1 . Если в каждый ящик надо положить не менее r предметов, то получим P(n- k ⋅r,k-1) способов. Следствие 2 . Если в каждый ящик надо положить хотя бы один предмет, то r=1 и получим P(n-k,k-1)= 1 1 − − k n C способов распределения. Сколько существует способов разложить n различных предметов в k ящиков, если нет никаких ограничений Каждый предмет можно положить в любой из k ящиков. Получаем k n способов распределения предметов по ящикам. Задача. Сколькими способами можно разделить 8 различных пирожных между 5 детьми Решение. Необходимо разложить 8 предметов по 5 ящикам. Это можно сделать 5 8 =390 625 способами. Сколькими способами можно поместить n различных предметов в k ящиков, если не должно быть пустых ящиков Данные r ящиков остаются пустыми, если в k–r ящиков предметы кладутся без ограничений. r пустых ящиков можно выбрать C n k способами. В оставшиеся k–r ящиков предметы можно разложить (k–r) n способами. По формуле включений и исключений число распределений, при которых хотя бы один ящик остается пустым, равно n k k k n k n k C k C k C 1 ) 1 ( ) 2 ( ) 1 ( 1 2 1 ⋅ ⋅ − + + − ⋅ − − ⋅ − . Тогда количество распределений, при которых ни один ящик не окажется пустым, равно k n -( n k k k n k n k C k C k C 1 ) 1 ( ) 2 ( ) 1 ( 1 2 1 ⋅ ⋅ − + + − ⋅ − − ⋅ − ). Задача. Сколькими способами можно послать по почте 8 различных фотографий, использовав 5 конвертов Разбор. Переформулируем задачу необходимо 8 предметов разложить в 5 ящиков. Посылать пустые конверты нерационально, поэтому накладывается запрет на пустые ящики. Применяя полученную выше формулу, получаем 5 8 - 1 5 C ⋅4 8 + 2 5 C ⋅3 8 - 3 5 C ⋅2 8 + 4 5 C ⋅1 8 =126 020. Имеется n 1 предметов одного сорта, n 2 – другого, ... , n s – го сорта. Сколькими способами их можно разложить по k ящикам, если не должно быть пустых ящиков Применяя рассуждения, аналогичные предыдущей задаче, получим следующую формулу 1 1 3 3 3 3 2 2 2 2 2 1 1 1 1 1 1 1 ) 1 ( 1 1 2 1 − − − − + − − + − − + − − + − − + − − + − − + ⋅ − + − ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ − ⋅ ⋅ ⋅ k k k k k n k k n k k k n k k n k k k n k k n k k n C C C C C C C C C C s s s . Задача. Сколькими способами можно разделить 8 яблок, 10 груши апельсинов между 4 детьми, если каждый должен получить хотя бы один фрукт Решение. Требуется 8 предметов одного сорта, 10 второго и 7 третьего разложить в 4 ящика так, чтобы ни один ящик не оказался пустым. По предыдущей формуле получаем 800 464 5 3 4 1 8 1 11 1 9 2 4 2 9 2 12 2 10 1 4 3 10 3 13 способов такого распределения. Сколькими способами можно распределить n различных предметов по k различным ящикам с учетом порядка расположения предметов в ящиках, причем все n предметов должны быть использованы Добавим к n предметам k–1 одинаковых разделяющих предмета. Рассмотрим всевозможные перестановки из n различных предметов и k–1 одинаковых. Каждая такая перестановка определяет один из способов распределения. Всего таких перестановок )! 1 ( )! 1 ( − − + k k n . Значит, n различных предметов можно разложить в k ящиков, с учетом расположения их в ящиках, )! 1 ( )! 1 ( − − + k k n = n k n A 1 − + способами. К тому же результату можно было прийти и другим путем. Переставим всеми возможными способами данные n предметов (n! способов. Теперь считаем предметы неразличимыми, их можно разложить в k ящиков Р, k–1) способами. Получаем Р n k n A 1 − + способов распределения этих вещей по к различным ящикам с учетом порядка их расположения в ящиках. Задача. Имеются 6 различных сигнальных флагов и 3 мачты, на которые их вывешивают. Значение сигнала зависит оттого, в каком порядке вывешены флаги. Сколькими способами можно развесить флаги, если все флаги должны быть использованы, но некоторые из мачт могут оказаться пустыми Решение. Имеем 6 предметов, которые необходимо разложить в 3 ящика, причем порядок предметов в ящике важен. Это можно сделать 160 20 ! 2 ! 8 )! 1 3 ( )! 1 3 6 ( = = − − + способами. Следствие. Если не должно быть пустых ящиков, то выберем k предметов и разложим по одному в каждый ящик. Это можно сделать k n A способами. Оставшиеся n–k предметов разложим в k–1 ящик, причем теперь некоторые ящики могут оказаться пустыми. Это распределение можно осуществить )! 1 ( )! 1 ( )! 1 ( )! 1 ( − − = − − + − k n k k k n способами. Всего имеем k n A 1 1 ! )! 1 ( )! 1 ( − − ⋅ = − − ⋅ k n C n k n способов распределения. Сколькими способами можно распределить n различных предметов по k различным ящикам с учетом порядка расположения предметов в ящиках, причем не все n предметов могут быть использованы и некоторые ящики могут оказаться пустыми Разобьем всевозможные комбинации на классы. В s класс войдут комбинации, в которых использованы ровно s предметов. Из предыдущей задачи известно, что s предметов можно разложить по k ящикам s k s A 1 − + способами. s предметов изданных можно выбрать s n C способами. Всего в s класс войдут s n C ⋅ s k s A 1 − + комбинаций. По правилу суммы имеем k k n n n k n k n k n A C A C A C A C 1 2 1 2 1 1 0 1 0 − + + − ⋅ + + ⋅ + ⋅ + ⋅ способов распределения n различных предметов по k различным ящикам с учетом порядка их расположения в ящиках, если не все n предметов могут быть использованы. Задача. Имеются 6 различных сигнальных флагов и 3 мачты, на которые их вывешивают. Значение сигнала зависит оттого, в каком порядке вывешены флаги. Сколькими способами можно развесить флаги, если не все флаги могут быть использованы и некоторые из мачт могут оказаться пустыми Решение. Имеем 6 различных предметов, которые необходимо разложить в 3 ящика, причем порядок предметов в ящике важен и не все ящики и предметы могут быть использованы. По формуле получаем 079 42 6 8 6 6 5 7 5 6 4 6 4 6 3 5 3 6 2 4 2 6 1 3 1 6 0 2 Следствие. Если не должно быть пустых ящиков, тов этом случае имеем ! )! 2 ( )! 1 ( ! 1 1 1 1 2 1 1 1 1 n C C k C C k C C k C C k n n n k k k n k k k n k k k n ⋅ ⋅ + + + ⋅ ⋅ + − ⋅ ⋅ + ⋅ ⋅ − − − + + − + − − способов распределения. Вероятность Частотой появления события в серии испытаний называется отношение числа наступления этого события в данной последовательности испытаний к общему числу испытаний. Вероятностью случайного события называется отношение числа равновозможных элементарных событий, благоприятствующих этому событию, к числу всех равновозможных элементарных событий. Равновозможными элементарными событиями будем считать такие события, любое из которых по отношению к другим событиям не обладает никаким преимуществом появляться чаще другого при многократных испытаниях, проводимых в одинаковых условиях. Например, при бросании игральной кости возможны шесть различных результатов из них лишь водном случае выпадает шестёрка. Поэтому вероятность выпадения шестёрки равна 1/6. Задача. Для того чтобы открыть камеру хранения, используется комбинация из 4 цифр (от 0 до 9), набираемая на 4 колесиках. а) Найти вероятность наугад открыть камеру хранения. б) Найти вероятность наугад открыть камеру хранения, если дополнительно стало известно, что все цифры на правильном номере разные. Решение. а) Всего комбинаций из 10 цифр по 4 4 10 A =10 4 вариантов. Открывает дверцу только одна из них, так что вероятность наудачу открыть ее равна 1/10000 = 0,0001. б) Всего комбинаций из 10 цифр по 4, если все цифры различны – 4 10 A =10 ⋅9⋅8⋅7=5 400 вариантов. Открывает дверцу по-прежнему только один, откуда вероятность открыть дверцу становится 1/5400 ≅ 0,0002. Таким образом, вероятность в простейшем случае вычисляется комбинаторно. Свойства вероятности 1. Из определения вероятности следует, что вероятность случайного события Ане больше единицы и не меньше нуля. |