Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 59 стр.

сочетание из a1, a2, a3, ...., an-1, an принадлежит одному и только одному из
этих классов, а общее число равно Сkn, то приходим к равенству (2).
        Пример.
        Пусть дано множество М = {a, b, c, d, e}. Тогда Mc = {(a,b), (a, c), (a,
d), (a, e), (b, c), (b, d), (b, e), (c, d), (c, e), (d, e)}.
        M1c = {(a, e), (b, e), (c, e), (d, e)}. M2c = {(a, b), (a, c), (a, d), (b, c),(b, d),
(c, d),}.
                                         5!
        С другой стороны, С 52 =              = 10 . С 2 = C1 + C 2 = 4 + 6 = 10.
                                        2!3!            5    4    4

                3. С 0n + C1n + K + C kn + K + C nn = 2n                (3)
      Доказательство:
      2n – это число всех n размещений с повторениями из элементов двух
типов. Разобьем эти размещения на классы, отнеся в k-й класс те, в которые
входят k элементов 1-го типа и (n–k) элементов 2-го типа. Размещения k-го
класса – это не что иное, как всевозможные перестановки из k элементов 1-
го типа и (n–k) элементов 2-го типа. Мы знаем, что число таких перестано-
вок равно
                                  ~=
                                  Р          n!     .
                                        k! (n − k)!
       Вспомним формулу
                                       ~ =
                                       Р               m!        ,
                                         m       i1! i 2!K i n !
где i1 = k, i2 = n–k, P(k, n–k) = Ckn. Значит, общее число размещений всех клас-
сов равно С 0n + C1n + K + C kn + K + C nn . С другой стороны, это же число
равно 2n . Тем самым соотношение доказано.
     4. Рассмотрим m-элементные сочетания с повторениями, составлен-
ные из элементов n+1типов, скажем из n+1 букв a, b, c,..., x. Число таких со-
четаний равно
                    ~ m = Сm .
                    С
                           n +1     n+m
     Разобьем все сочетания на классы, отнеся к k-му классу сочетания, в
которые k раз входит буква a, остальные (m–k) мест могут быть заняты ос-
тавшимися n буквами с повторениями. Поэтому в k-й класс входит столько
сочетаний, сколько можно составить (m–k)-элементных сочетаний с повто-
рениями из элементов n типов, т. е. С m - k , значит, общее число всех со-
                                                n + m - k -1




                                           59