Избранные комбинаторные задачи

 

     Теорема. Число различных перестановок с повторениями из элементов {a, b, …, c}, в которых элементы a, b, …, c повторяются соответственно α, β, …, γ раз, равно:  

     Пример 

     Дано  p + q + r различных предметов; сколькими способами можно разбить эти предметы на 3 группы так, чтобы первая группа содержала р предметов, вторая q предметов, а третья r предметов?

     Решение. Расположим все данные предметы в каком-нибудь определенном порядке:

     При распределении предметов по группам  будем на месте каждого предмета писать номер той группы, в которую  он попадает. Так, запись

     2  1  2  3 ... 1

означает, что первый предмет попал во вторую группу, второй в первую, третий во вторую и т. д., последний в первую. Всякому  распределению предметов по группам  взаимно однозначно соответствует  перестановка из чисел 1, 2, 3, в которой 1 встречается p раз, 2 встречается q раз и 3 встречается r раз. Число возможных способов распределения предметов равно:  
 

     2.1.6. Размещения с повторениями

     Термином  «размещение с повторениями», составленным из данных элементов:

      , , … ,

по k в комбинаторике называется всякая конечная k-членная последовательность, членами которой являются данные элементы (а).

     Два размещения с повторениями:

      , , … ,   и , , … ,

     одинаковы б том и только в том случае, когда на одинаковых местах находятся одни и те же элементы:

     = ,  = , … , =.

     В размещении с повторениями (как и во всякой последовательности) один и тот же элемент может находиться на нескольких различных местах. Если в размещении с повторениями , , … ,   некоторый элемент занимает р различных мест, то говорят, что этот элемент повторяется в размещении р раз.

     Пример 

     Ниже  выписаны всевозможные размещения с  повторениями из 4 элементов 1, 2, 3, 4 по 3:

     111 112 121 211 113 131 311 114 141 411 222 221 212 223 232

     322 224 242 422 333 331 313 133 332 323 134 343 433 444 441

     414 144 442 424 244 123 124 213 214 132 334 443 434 344 312

     314 142 143 412 413 241 243 421 423 431 432 342 341 321 324

     231 234 122  233  

     Теорема. Число всевозможных размещений с повторениями из n элементов по k равно:

     .

     Пример 

     Имеется n различных книг, каждая в р экземплярах; сколькими способами можно сделать выбор книг из числа данных?

     Решение. Перенумеруем в каком-либо порядке n данных книг. Если первая книга берется в экземплярах, вторая в экземплярах и т. д. n-я в экземплярах, то указанному выбору соответствует размещение с повторениями:

      , , … ,

из  р+1 чисел 0, 1, 2, ..., р, взятых по n (если = 0, то i-я книга не берется вовсе). Таким образом получается различных комбинаций, по числу размещений с повторениями из р+1 элементов по n. Исключив из рассмотрения комбинацию 0, 0, ..., 0, означающую, что не берется ни одна книга, мы получим — 1 различных способов выбора книг. 

     2.1.7. Сочетания с повторениями

     Пусть а, b, с,..., d — данное конечное множество, содержащее n элементов. Поставим в соответствие каждому элементу этого множества некоторое целое неотрицательное число, называемое кратностью данного элемента. Это соответствие определяет функцию, для которой значениями аргумента являются данные элементы, а значениями функции — целые неотрицательные числа — кратности элементов. Пусть α — кратность элемента а, β — кратность элемента b, γ — кратность элемента с и т. д. Для обозначения рассматриваемого соответствия выписывают символ, обозначающий данный элемент столько раз, какова его кратность, если эта кратность положительна, если же кратность данного элемента равна нулю, то соответствующий символ не выписывается. Символы, обозначающие элементы, можно писать в каком угодно порядке, лишь бы каждый из них был написан столько раз, какова кратность соответствующего элемента. Так, например, записи

     aaabbcdd, ababacdd, dbdbaaca

выражают  одно и то же: кратность а равна 3, кратность b равна 2, кратность с равна 1 и кратность d равна 2. Говорят также, что данный элемент берётся столько раз, какова его кратность. Так, в рассмотренном примере элемент а взят 3 раза, элемент b взят 2 раза, элемент с взят 1 раз и элемент d взят 2 раза.

     Определение. Если каждому элементу некоторого конечного множества поставлено в соответствие целое неотрицательное число — кратность данного элемента, то говорят, что задано сочетание с повторениями. Сумма k кратностей всех элементов называется порядком сочетания.

     Всякое  сочетание с повторениями k-гo порядка, составленное из множества, содержащего n элементов, называется также сочетанием с повторением из n элементов по k.

     Если  α, β, ...,γ — кратности элементов а, b, ...,с, то согласно определению α + β + ... + γ есть порядок сочетания

 

     Теорема. Число сочетаний с повторениями из n элементов по k выражается формулой

      = = .

     Пример 

     Имеется n одинаковых предметов, сколькими способами можно распределить эти предметы между ш лицами?

     Решение. Если первое лицо получило α предметов, второе β предметов и т.д., последнее γ предметов, то будем данное распределение предметов символически записывать следующим образом:

     

 

     где

     α + β + ... + γ = n

(если  данное лицо, например, первое не  получает предметов, то и цифра  1 не пишется в символе распределения). Отсюда видно, что число возможных  распределений предметов разно  числу сочетаний с повторениями  из р по n, т.е. 
 

     2.1.8. Комбинаторные тождества и методы их доказательства

     Комбинаторными  тождествами называются соотношения между выражениями для чисел различного вида соединений. Для доказательства комбинаторных тождеств могут применяться различные методы. В частности, эти тождества могут устанавливаться:

     a) непосредственно из рассмотрения самих соединений;

     b) при помощи тождественных преобразований;

     с) косвенным путем на основании свойств многочленов (в частности применение формулы бинома Ньютона);

     d) путем применения метода математической индукции.

     Ниже  на ряде конкретных примеров показаны различные методы доказательства комбинаторных тождеств:

     1. Число сочетаний из n элементов по k равно числу сочетаний из n элементов по n — k:

       =

     Первое  доказательство. Всякой части, содержащей k элементов данного множества из n элементов, соответствует единственная часть, содержащая n—k оставшихся элементов. Обратно, всякой части из n—k элементов соответствует единственная часть, содержащая k не вошедших в нее элементов. Это соответствие взаимно-однозначное. В самом деле, если две части, содержащие данное число элементов, различны, то различны и соответствующие части, образованные оставшимися элементами. Из установленного взаимно-однозначного соответствия следует, что число частей, содержащих k элементов, равно числу частей, содержащих n—k элементов.

     Второе  доказательство. Достаточно принять во внимание, что и   выражаются одной и той же формулой  

     Третье  доказательство. Достаточно принять во внимание, что и    по сути коэффициенты при и в каноническом представлении симметрического многочлена .

     2. Имеет место тождество:

                              = + .                                                          (2)

     Первое  доказательство. Выделим какой-либо один элемент из числа данных n элементов. Все сочетания из n элементов по k разделяются на две группы, содержащие данный элемент и не содержащие данного элемента. Первая группа состоит из , вторая из сочетаний, откуда и следует тождество (2).

     Второе  доказательство. Имеем:

     + = + = ( + ) = =

     3. Имеет место тождество:

      + +  … + = .                                         (3)              

     Доказательство. Пользуясь тождеством (2), напишем ряд следующих тождеств:

                                                                    = (=1),                                             

      + = ,

      + = ,

     . . .

+ = . 

     Сложив  почленно эти тождества, получим, после  сокращения, тождество (3).

     Следствие. В силу тождества 1) тождество 3) может быть переписано в виде

      + +  … + = .                                         (3')

     4. Имеет место тождество:

      + +  … + + = ,                                              (4)

т. е. сумма  биномиальных коэффициентов равна , где n — степень бинома.

     Первое  доказательство. Сумма , находящаяся в левой части, есть количество всевозможных частей (включая и несобственные части, т.е. пустое множество и само множество) конечного множества из n элементов.

     Подсчитаем  другим способом число частей конечного множества. Расположим элементы данного множества в некотором определенном порядке:

      , , … ,

     Рассмотрим  какую-нибудь часть данного множества: поставим 1 на месте элементов, вошедших в состав, и 0 на месте элементов, не вошедших в состав рассматриваемой части. В силу этого всякой части множества ставится во взаимно-однозначное соответствие некоторое размещение с повторениями из двух элементов 0 и 1 по n. Число всех частей множества равно числу полученных размещений, а последнее равно .

     Второе  доказательство. Достаточно в формуле бинома Ньютона

      = + + … + +

положить  x = y = 1.

     5. Сумма биномиальных коэффициентов, взятых с чередующимися знаками, равна нулю