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

       +  … + + … + = 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.

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

     Пример  7

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

     Решение

     Из 20-ти элементов необходимо сделать  три выборки, причем порядок внутри выборок значения не имеет. Поэтому  используем формулу для сочетаний. Чтобы выбрать из 20-ти элементов 3, существует способов. Остается 17 элементов, из которых выбирается 5 элементов - способами. Остается 12 элементов, из которых выбирается 12 элементов. Это можно сделать = 1, т.е. одним способом. Используя принцип произведения, получаем: ∙  ∙ .

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

     Пример  8

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

     Решение

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

       = = =   = 6 5∙ 4 3 =360.

     2.  Необходимо исключить букву р из рассмотрения. Количество слов, не содержащих эту букву:

       = = = 120.

     3.  На первое место поставить  букву с можно только одним  способом. На последнее место  поставить букву р можно тоже только одним способом. Остаются 4 буквы, которые необходимо разместить по двум местам:

       = = =   = 12

     Ответ: 360, 120, 12.

     Пример  9

     Сколькими способами можно переставить  буквы слова «ананас»?

     Решение

     Всего букв 6. Из них одинаковы n₁«а» = 3, n₂«н» = 2, n₃«с» = 1. Следовательно, число различных перестановок равно

      = 60.

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

     Пример  10

     В кондитерском магазине продавались 4 сорта  пироженных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пироженных.

     Решение

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