Таблицы Брадиса

Комбинаторика 2. Бином Ньютона

Комбинаторика 2. Бином Ньютона

Элементы математики в задачах - Г. А. Мерзон

пп+1 > (п + 1)п и (п + 1)п+2 ^ (п + 2)п+1.

Перемножая эти неравенства, получаем

(п + 1)2п+2 = ((п + 1)2)п+1 < ((п + 2)п)

что неверно.

Комбинаторика 2. Бином Ньютона

листок 5 / октябрь 20 04

Ш в этом листке изучаются биномиальные коэффициенты и соотно­шения между ними. Для биномиальных коэффициентов дается два определения: рекурсивное, через треугольник Паскаля, и комбина­торное, через число подмножеств (а позже в листке появляются и другие интерпретации). Из-за этого большинство задач имеет мини­мум два решения — формальное доказательство по индукции через рекурсивное определение и комбинаторное доказательство, объяс­няющее, почему левая и правая часть равенства соответствуют двум способам подсчета числа каких-то объектов. А возникающий в конце листка бином Ньютона дает третий метод доказательства, развитием которого является метод производящих функций. Все это учит, в частности, работать с объектами, имеющими несколько различных определений, используя в каждый момент наиболее удобное. (Тем не менее, полезно иногда попросить школьника, решившего задачу через одно из определений, попытаться придумать решение и через другое определение.)

Таким образом, в листке обсуждаются два метода решения ком­бинаторных задач из трех основных (еще один — выписывание всех вариантов и учет повторов — обсуждается в листке «Комбинатори­ка 1»): 1) рекурсивное вычисление с доказательством по индукции,

2)   установление биекции между двумя множествами.

Вообще, установление биекций между множествами «комбина­торной природы», наравне с нахождением числа элементов, является одной из основных задач комбинаторики. Это связно, в частности, с тем, что при нахождении числа элементов множества промежу­точные шаги часто можно интерпретировать как построение биек­ций, сводящих, в конце концов, задачу к вычислению числа эле­ментов какого-нибудь простого множества (отличный пример такой задачи — теорема Кэли из листка «Теория графов 2»). Такой план часто оказывается проще преобразования алгебраических выраже­ний.