Комбинаторные тождества

Содержание:

  1. Рекуррентное соотношение
  2. Наибольший элемент

Комбинаторные тождества

Комбинаторные тождества

Комбинаторные тождества

Комбинаторные тождества

 

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

 

этом параграфе будет доказан ряд соотношений для биномиальных коэффициентов. Все они интересны сами по себе и многие будут использоваться нами в дальнейшем. Однако не менее интересны способы их доказательства (или получения). Мы будем, как правило, предлагать доказательства, исходящие из комбинаторной природы соотношений.

Общая схема рассуждений здесь такова. Пусть доказывается тождество По виду левой и правой частей реконструируется задача на подсчет чист комбинаций определенного вида (п, т,... выступают в роли параметров), решая которую одним способом, получаем в качестве ответа , а другим способом — В нижеприводимых соотношениях значения параметров предполагаются такими, чтобы все биномиальные коэффициенты имели смысл (например, если в формуле присутствует CJ, то предполагается, что Комбинаторные тождества Имеют место следующие тождества:

1) Каждому к -элементному подмножеству n-элементного множества поставим в соответствие его дополнение до всего множества. Нетрудно видеть, что при этом задается взаимно однозначное соответствие между к -элементными и (п - Л;)-элементными подмножествами n-элементного множества. Если между двумя конечными множествами существует взаимно однозначное соответствие, то эти множества содержат одинаковое количество элементов.

Таким образом, число сочетаний из п по к совпадает с числом сочетаний, из п по п - к. 2) Пусть в парламенте п депутатов, включая спикера. Подсчитаем число способов составить парламентскую делегацию из к человек. С одной стороны, это число сочетаний СJ. Произведем подсчет по-другому. Для того чтобы сформировать делегацию, включающую спикера, нужно из п - I рядовых депутатов выбрать к — 1; это можно сделать способами. Если же спикер в делегацию не входит, то ее членов можно выбрать , способами (из п - 1 рядовых депутатов выбирается *; человек).

Таким образом, всего имеется , способов составить делегацию.

3) 2П — число всех подмножеств n-элементного множества. Так как CJ — число всех его fc-элементных подмножеств, то просуммировав Cj по к от 0 до п, вновь получим общее число всех подмножеств. Другой способ доказательства состоит в применении формулы бинома Ньютона Положив в ней х = 1, получим требуемое. 4) Тождество доказывается подстановкой в приведенной выше формуле х = -1. Приведем также комбинаторное доказатыьство. Найдем количество подмножеств n-элементного множества, имеющих четное число элементов.

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

 

Возможно вам будут полезны данные страницы:

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

 

Согласно правилу произведения, эти решения могуг быть вынесены 2П~' способами. Спикер включается в делегацию только в том случае, когда в ней нечетное число «рядовых» депутатов. Таким образом, общее число делегаций с четным числом членов равно 2п~1, Поскольку обшее число подмножеств есть 2П, подмножеств с нечетным числом элементов также 2П_|, то есть столько же, сколько и с четным числом элементов. Значит, поскольку части записанного равенства выражают собой число подмножеств n-элементного множества соответственно с нечетным и четным числом элементов.

Полученное равенство равносильно

доказываемому. 5) Данное соотношение является другой формой записи предыдущего тождества. Комбинаторные тождества 6) Решим такую задачу. Имеется т мужнин и п женщин. Из них нужно сформировать делегацию из к человек. Каким числом способов это можно сделать? Отвег очевиден: с£+п. Будем классифицировать делегации по числу мужчин. Если в делегацию входят з мужчин и k - а женщин, то мужчин можно выбрать способами, а женшин — способами; значит, число делегаций с з > мужчинами равно .

Суммируя ~a по s от 0 до к, получим обшее число делегаций. 7) Для доказательства достаточно в предыдущем соотношении положить применить 1). 8) Доказательство тождества может быть получено из решения следующей задачи: Каким числом способов можно из п кандидатов выбрать к депутатов и среди последних спикера? Депутаты выбираются С£ способами, после чего спикер выбирается к способами; таким образом, общее число способов равно С„ к.

Рекуррентное соотношение

То же число можно подсчитать по-другому. Будем сначала (всенародным голосованием) избирать спикера (из п кандидатов), а затем из оставшихся п - 1 кандидата — еще депутата. Указанная процедура может быть выполнена п • J способами. Доказано, что . Отсюда вытекает полезное рекуррентное соотношение , применяя которое несколько (точнее: к) раз, можно вновь вывести формулу для числа сочетаний 9) Это тождество — обобщение предыдущего (если в 9) положить m = 1, то получим 8)) и может быть доказано с помощью решения задачи, таюсе являющейся обобщением ранее рассмотредаой:

Каким числом способов можно выбрать из п кандидатов к депутатов и среди последних т членов президиума? 10) 1-й способ. Докажем тождество математической индукцией по к. База индукции. При к = 0 имеем верное равенство: Индукционный шаг. Пусть доказываемое утверждение верно при : Прибавив к обеим частям равенства , получим Таким образом, соотношение 10) справедливо и при . 2-й способ. Общее число (-элементных подмножеств множества равно , (правой части доказываемого тождества). Будем классифицировать указанные подмножества по их наибольшему элементу, который, очевидно, принимает значения .

Наибольший элемент

Найдем число подмножеств с наибольшим элементом т+р 4-1. Поскольку наибольший элемент уже выбран, оставшиеся m элементов выбираются из множества значит, число таких подмножеств равно Суммируя , вновь получим общее число -элементных подмножеств (левую часть доказываемого тождества). 11) Тождество доказывается на основе предыдущего: 12) Решим задачу: Каким числом способов можно из п кандидатов выбрать т депутатов и среди депутатов некоторых (может быть, всех, а может быть, никого) наградить ?

С одной стороны, депутаты выбираются способами, а награжденные выделяются 2т способами (столько подмножеств имеет множество из m элементов), и, значит, ответ к задаче: . С другой стороны, если число награждаемых депутатов равно к , то их можно выбрать способами, после чего остальные m - к депутатов выбираются способами. Суммируя по к от 0 до тп, вновь Комбинаторные тождества получим ответ к рассматриваемой задаче. Тождество доказано. 13) Используя соотношение 8), преобразуем общий член суммы: 2-й способ. Воспользовавшись 13) тождеством, заметм и в полученной двойной сумме поменяем порядок суммирования