Три вида соединений
Определение 1
Определение 2
Определение 3
Теорема 1
Теорема 2
Свойства сочетаний
Оглавление
Предметный указатель
Литература

§ 1. СОЕДИНЕНИЯ. ВИДЫ СОЕДИНЕНИЙ

   Пусть А - совокупность различных предметов а1, а2, ..., аn, объединенных каким-нибудь общим признаком. Например, A – есть совокупность нечетных чисел от 1 до 99, или учащихся данной школы, или заданных точек на плоскости и т. д. Вместо слова "совокупность" будем говорить "множество".
   Итак, А – множество, состоящее из конечного числа элементов а1, а2, ..., аn.
   Из различных элементов множества А можно образовывать группы. Если в каждую группу входит одно и то же число элементов m( m ≤ n), взятых из множества A, то говорят, что они образуют соединения из n элементов по m в каждом. В зависимости от того, входят ли в соединение все элементы множества А или только часть их, играет ли роль порядок элементов или не играет, различают три вида соединений:    Определение 1. Соединения, каждое из которых содержитm различных элементов (m ≤ n), взятых из n элементов множества A, отличающиеся друг от друга или составом элементов, или их порядком, называются размещениями из n элементов по m в каждом.
   Число таких размещений обозначается символом Anm. Так, например, различные трехзначные числа, составленные из девяти цифр 1, 2, 3, ..., 9 и не содержащие одинаковых цифр, образуют размещения. Их число есть А93.
   Определение 2. Соединения, в каждое из которых входят все n элементов множества A и которые, следовательно, отличаются друг от друга только порядком элементов, называются перестановками из n элементов. Число таких перестановок обозначается символом Рn. Перестановки являются частным случаем размещений, когда m = n. Поэтому Рn = Ann.
   Определение 3. Соединения, каждое из которых содержит m различных элементов (m ≤ n), взятых из n элементов множества A, отличающиеся друг от друга по крайней мере одним элементом, называются сочетаниями из n элементов по m.
   Число таких сочетаний обозначается символом Сnm или (nm). Изменение порядка элементов внутри одного сочетания не приводит к новому сочетанию. Например, всевозможные комбинации трех различных сомножителей, образованные из пяти цифр 1, 2, 3, 5, 7, есть сочетания из пяти элементов по 3, так как изменение порядка сомножителей здесь не дает ничего нового.
   Выведем формулы числа размещений, перестановок и сочетаний.
   Теорема 1. Число всевозможных размещений из n элементов по m в каждом равно произведению m последовательно убывающих на еданицу чисел, из которых большее есть n, т. е.
Аnm = n·(n - 1)·( n - 2) ... (n - m + 1).
   Комментарий. Такое произведение называется обобщённой степенью и обозначается символом
n[m] = n·(n - 1)·( n - 2) ... (n - m + 1). Если n = m, то произведение n[m] = n·(n - 1)·( n - 2) ... (n - m + 1) ... 1 обозначается символом n ! ( n факториал), причем условно считается, что 0 ! = 1. В дальнейшем будет понятно удобство такого соглашения. В литературе встречается также символ n !! = n·(n - 2)·(n - 4)·...·1. Например,
1·3·5·7·...·(2n + 1) = (2n + 1)!!.                     (1)
   Доказательство проведем методом индукции. Если m = 1, то, очевидно, что An1 = n, так как из n различных элементов можно составить n различных размещений по одному элементу в каждом.
   Допустим теперь, что составлены все Anm-1 размещений, причем число таких размещений равно
Anm-1 = n·(n - 1)·(n - 2)...[n - (m - 1) + 1] = n·(n - 1)·(n - 2)...(n - m + 2).                     (2)
Составим теперь размещения из n элементов по m в каждом. С этой целью возьмем произвольное размещение, содержащее m - 1 элементов и будем присоединять к "его правому краю" по одному элементу из n - m + 1 не вошедших в него элементов. При этом получится n - m + 1 различных размещений по m элементов. Поступая так с каждым размещением, содержащим m - 1 элементов (число этих размещений равно Anm-1), получаем
(n - m + 1)· Anm-1
размещений по m элементов. Все эти размещения различны. В самом деле, два произвольных размещения по m элементов либо образованы из одного размещения, содержащего m - 1 элементов, и тогда они отличаются присоединенными крайними элементами справа. Если они образованы из двух различных размещений, содержащих m - 1 элементов, то они отличаются порядком или элементами среди первых m - 1 членов.
   Покажем, что в это число вошли все размещения по m элементом из n. Действительно, любое размещение из m элементов после отбрасывания крайнего справа элемента вошло в число размещений, содержащих по m - 1 элементов, и, следовательно, образовано из него приписыванием справа отброшенного элемента, который не содержится среди его первых m - 1 элементов.
   Таким образом, число всех различных размещений из n элементов по m, т. е. Anm, вычисляется по формуле
Anm = (n - m + 1)· Anm-1
или в силу нашего предположения (2)
Anm = n·(n - 1)·(n - 2)...(n - m + 2)·(n - 2)...(n - m + 1)                     (3)
   Следствие. Полагая в равенстве (3) m = b, имеем
Pn = n·(n - 1)·(n - 2)·...·1 = n!   (4)
т. е. число всевозможных перестановок из n элементов равно n!.
   Теорема 2. Число всех различных сочетаний из n элементов по m в каждом выражается формулой
                     (5)
   Доказательство. Пусть составлены все сочетания из n элементов по m в каждом. Если в каждом из этих сочетаний произвести всевозможные перестановки элементов, то получатся все размещения из n элементов по m в каждом. В самом деле, взяв произвольное размещение по m элементов, можно указать сочетание, содержащее те же элементы, которое может отличаться от взятого размещения только лишь порядком элементов. Но тогда это размещение совпадает с одной из перестановок, которая получается из соответствующего сочетания. Остается показать, что среди всех полученных размещений нет одинаковых. Для этого возьмем два различных размещения. Они получены либо из одного сочетания и тогда отличаются порядком, либо из различных сочетаний и тогда отличаются хотя бы одним элементом. И в том, и в другом случае эти размещения различны.
   Из одного сочетания получается Рm = m! перестановок, из сочетаний – ·Pm перестановок.
   Следовательно, = ·Pm и .    Формулу (5) можно записать в другом виде.
   Предполагая, что 1 ≤ m < n, умножим числитель и знаменатель дроби (5) на произведение 1·2·...·(n - m) = (n - m)!. Имеем
                     (6)
Заметим, что формула (6), выведенная в предположении 1 ≤ m < n, остается верной для m = n. В самом деле, при m = n равенство (0! = 1). очевидно, так как из n элементов можно образовать только одно сочетание, содержащее n элементов.
   Из определения размещений, перестановок и сочетаний следует, что выражения , Pn и имеют смысл лишь для 1 ≤ m < n. При m > n полагают по соглашению = = 0. Если m = 0, то считают An0 = 1 и Cn0 = 1. Последнее согласуется с формулой (6). Полагая в ней m = 0, имеем
.
Таким образом, можно считать, что формула (6) справедлива для 0 ≤ m ≤ n.
   Свойства сочетаний.
  1.    Для всех m = 0, 1, 2, ..., n справедливо равенство
    Cnm = Cnn-m                     (7)
    Согласно формуле (6)
    Можно доказать свойство (7) для m ≠ 0 и m ≠ n другим способом. Образуем всевозможные сочетания из n элементов по m в каждом и рассмотрим соединения из элементов, не вошедших в каждое из таких сочетаний. Этих соединений будет столько, сколько сочетаний по m элементов, т. е. . С другой стороны, эти соединения образуют всевозможные различные сочетания из n элементов по n - m в каждом. (Доказательство этих утверждений проводится по той же схеме, как и в теореме 2. Предоставляем его читателю.)
       Таким образом, Cnm = Cnn-m.
  2. Для всех m = 0, 1, 2, ..., n справедливо равенство
                            (8)
    В самом деле, согласно формуле (6)
  3. Для всех m = 1, 2, ..., n справедливо равенство
                            (9)
    В самом деле, согласно формуле (6) для m = 1, 2, ..., n - 1
    Приведенные выкладки теряют смысл при n = m, так как в этом случае (n - m - 1)! = (-1)!. Однако формула (9) остается верной для n = m. Это проверяется непосредственной подстановкой n = m в левую и правую часть формулы. Действительно, так как
    то
          Формулу (9) для m ≠ 0 и m ≠ n можно доказать и другим способом. Разобьем все сочетания из n элементов по m в каждом на два класса: к первому отнесем все сочетания из n по m, не содержащие какой-нибудь фиксированный элемент, например а, ко второму отнесем все остальные сочетания, содержащие элемент а. Число сочетаний в первом классе равно, очевидно, (из множества А исключаем элемент а), число элементов во втором классе равно (из множества А исключаем элемент а и образуем из оставшихся n - 1 элементов сочетания по m - 1 элементу в каждом, а затем к каждому получившемуся сочетанию приписываем элемент а). Так как число всех сочетаний из n элементов по m равно , то