Лекции по курсу математики для юристов. Саакян Г.Р - 24 стр.

                                         - 24 -
       6. Элементы комбинаторики. Человеку часто приходится иметь дело с задачами, в
которых нужно подсчитать число всех возможных способов расположения некоторых пред-
метов или число возможных способов осуществления некоторого действия. Задачи такого
типа называют комбинаторными.
       Вообще же, комбинаторикой называется область математики, в которой изучаются
вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, мож-
но составить из элементов, принадлежащих заданному, обычно конечному, множеству.
       Рассмотрим два общих правила, с помощью которых решается большинство комбина-
торных задач, – правило суммы и правило произведения.
                                              Правило суммы
       Допустим, в ящике имеется n различных (например, разного цвета) шаров. Произ-
вольным образом вынимаем один шар. Сколькими способами это можно сделать? Конечно,
n . Теперь эти n шаров распределим по двум ящикам: в первом – m шаров, во втором – k .
Произвольно из какого-нибудь ящика извлекаем один шар. Сколькими разными способами
можно это сделать? Из первого ящика шар можно извлечь m разными способами, из второго
– k разными способами. Всего n = m + k способами.
       Правило суммы. Если некоторый объект A можно выбрать m способами, а объект
B – k способами (не такими, как A ), то объект «либо A , либо B » можно выбрать m + k
способами.
       Другими словами, если два действия взаимно исключают друг друга, причем одно
из них можно выполнить m способами, а другое – k способами, то имеется m + k способов
осуществить хотя бы одно из этих действий.
                                        Правило произведения
       Пример 8. В чемпионате страны по шахматам принимает участие 16 человек. Сколь-
кими способами могут быть распределены золотая и серебряная медали?
       ∆ Золотую медаль может получить один из 16 шахматистов. После того, как опреде-
лен владелец золотой медали, серебряную медаль может иметь один из 15-ти человек. Отсю-
да, общее количество способов, которыми могут быть распределены золотая и серебряная
медали, равно 16 ⋅ 15 = 240 . (Выбрав один из 16-ти возможных способов вручения золотой
медали, имеем 15 возможных способов вручения серебряной медали). ▲
       Рассуждения, которые были использованы при решении примера 8, доказывают спра-
ведливость следующего простого утверждения.
       Правило произведения. Если объект A можно выбрать m способами, а после каж-
дого такого выбора другой объект B можно выбрать (независимо от выбора объекта A )
k способами, то пару объектов A и B (в указанном порядке) можно выбрать m ⋅ k спосо-
бами.
       Правило произведения можно сформулировать в общем виде (для любого конечного
числа объектов): Пусть требуется выполнить одно за другим k действий. Если первое дейст-
вие можно выполнить n1 способами, второе действие – n2 способами, третье – n3 способами
и так до k -го действия, которое можно выполнить nk способами, то все k действий вместе
могут быть выполнены n1 ⋅ n2 ⋅ ... ⋅ nk способами.
       Рассмотрим теперь три наиболее часто встречающихся вида комбинаций: перестанов-
ки, размещения и сочетания.
                                           Перестановки
       Определение. Конечное множество называется упорядоченным, если в нем установле-
но отношение порядка, т.е. для любых двух различных элементов известно, что один из них
предшествует другому. Другими словами, конечное множество называют упорядоченным,
если каждому элементу этого множества поставлено в соответствие некоторое число (номер
элемента) от 1 до n , где n – число элементов множества, так что различным элементам со-
ответствуют различные числа.