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

aaabbcdd, ababacdd, dbdbaaca

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

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

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

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

1 1 … 1 α раз

2 2 … 2 β раз

p p … p γ раз

 

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

= = .

Пример 

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

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

a a … a   α раз

b b … b                           c c … c                                   .  .  .               β раз                                  γ раз

 

где

α + β + ... + γ = 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. Сумма биномиальных коэффициентов, взятых с чередующимися знаками, равна нулю

  +  … + + … + = 0                            (5)

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

x = 1, у = –1.

Следствие 1. Имеют место равенства:

+ + + … = + + … =

Следовательно, сумма биномиальных коэффициентов (при данном n), занимающих четные места, равна сумме коэффициентов, занимающих нечетные места. В самом деле, в силу тождеств (4) и (5) имеем:

+ =   и — = 0,

откуда следует равенство  рассматриваемых сумм.

Следствие 2. Общее число тех частей конечного множества, которые состоят из нечетного количества элементов, равно числу тех частей, которые состоят из четного числа элементов.

Это следует из предыдущего и из того, что есть число всех частей конечного множества, содержащих k его элементов.

6. Доказать тождества:

+ + + … = ( + 2 cos ),         (6')

+ + + … = ( + 2 cos ),    (6'')

+ + + … = ( + 2 cos ).    (6''')

Доказательство. Пусть ɛ — мнимый кубический корень из 1

ɛ = cos + i sin = .

Положив в формуле бинома Ньютона х = 1, у = 1, затем х = 1, y = ɛ, и, наконец, х = 1, y = , получим:

=   + + + + + … ,                                      (a)

=   + ɛ + + + ɛ + … ,                            (b)

=   + + ɛ + + + …                            (c)

Сложив почленно равенства (а), (b) и (с) и разделив на 3, получим в правой части сумму биномиальных коэффициентов, взятых через 2, начиная с , а в правой части

[ + + ].   

Приняв во внимание, что 

1 + ɛ = + i = cos + i sin ,

1 + = — i = cos(– ) + i sin(– ),

получим:

[ + + ] = ( + 2 cos ),        

откуда следует тождество (6').

Для доказательства тождеств (6") и (6'") следует составить суммы:

+ +     и   + + .

7. Доказать тождество:

+ + … + =                                       (7)

Доказательство. Рассмотрим тождество:

= .

Воспользуемся каноническими  представлениями сомножителей левой  части:

= + + … + + … + ,

= + + … + + … + .

Подсчитаем коэффициенты при ; этот коэффициент равен левой части тождества (7). С другой стороны, коэффициент при найдем, применив формулу бинома Ньютона к , этот коэффициент равен . Отсюда следует тождество (7).

8. Имеет место следующая формула для суммы квадратов биномиальных коэффициентов:

+ + … = .                                        (8)

Доказательство. Достаточно в формуле (7) положить n = m = p и принять во внимание тождество = .

 

2.2. Примеры решения  комбинаторных задач

Пример 1

У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она  выдает по одному фрукту. Сколькими  способами это может быть сделано?

Решение

Имеем набор {я, я, г, г, г}. Всего  перестановок пятиэлементного множества  5!, но мы не должны учитывать перестановки, в которых объекты одного типа меняются местами несколько раз, поэтому нужно поделить на возможное число таких перестановок: 2! 3!. Получаем в итоге

= =10

Ответ: 10 способов.

Пример 2

Предприятие может предоставить работу по одной специальности 4 женщинами, по другой - 6 мужчинам, по третьей - 3 работникам независимо от пола. Сколькими способами  можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Решение

Имеем 14 претендентов и 13 рабочих  мест. Сначала выберем работников на первую специальность, то есть 4 женщин из 6:

= = 15.

·Далее независимо аналогичным образом выберем мужчин на вторую специальность:

= = 28.

Осталось 2 женщины, 2 мужчин и 3 вакантных места, которые, по условию, могут занять любые из четырех оставшихся человек. Это может быть сделано 2 вариантами:

1. 1 женщина и 2 мужчин (выбираем женщину = 2 способами)
2. 1 мужчина и 2 женщины (выбираем мужчину = 2 способами).

В итоге получаем 15 · 28(2 + 2) = 1680 способов.

Ответ: 1680 способов.

Пример 3

Сколькими способами можно  распределить уроки в шести классах  между тремя учителями, если каждый учитель будет преподавать в  двух классах?

Решение

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

Поэтому   искомое  число

 =   =

= 6 5 3 =90

Ответ: 90.

Пример 4

Сколькими способами можно  поставить на шахматную доску  белую и черную ладьи так, чтобы  они не били друг друга?

Решение

Белую ладью можно поставить  на любую из 64 клеток. Независимо от своего расположения она бьет 15 полей (включая поле, на котором она  стоит). Поэтому остается 49 полей, на которые можно поставить черную ладью. Таким образом, всего есть 64 49 = 3136 разных способов.

Ответ: 3136 способов.

Пример 5

Имеется 5 разноцветных фишек, которые выкидываются по 3 в ряд. Сколько существует различных комбинаций из трех последовательно выложенных фишек? Сколько будет комбинаций, если одна из фишек имеет уже определенный (один из пяти) цвет?

Решение

Поскольку порядок расположение выбранных из трех фишек имеет  значение, то решением первой задачи является число размещений:

= 5 ∙ 4 ∙ 3 = 60.

Во втором случае число  фишек, из которых производится выбор, уже равен 4 (один цвет уже фиксирован) и требуется выбрать только 2 фишки. Таким образом, число комбинаций равно

К = = 5 ∙ 4 ∙ 3 = 60.

C другой стороны, фиксированная фишка может занимать одно из трех мест. Тогда общее число комбинаций равно

К ∙ 3 = 12 ∙ 3 = 36

Ответ: 36 комбинаций.

Пример 6

В автомашине 7 мест. Сколькими  способами семь человек могут  усесться в эту машину, если занять место водителя могут только трое из них?

Решение

Действие, которое должно быть выполнено особым способом, необходимо выполнять первым. Итак, на место  водителя можно посадить только одного из трех человек (умеющего водить машину), т.е. существуют 3 способа занять первое место. Второе место может занять любой из 6 человек, оставшихся после того, как место водителя будет занято и т.д. Используя принцип умножения, получаем произведение: 3 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 3 ∙ 6! = 3 ∙ 720 = 2260.