Комбинаторные доказательства формулы Ньютона

45

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

Алгебра и начала анализа

«Как возникло и развивалось понятие функции» (1977, № 7),
«Четные и чечные функции» (1977, № 4),
«Перiodические функции» (1976, № 12),
«Осторожно: максимум!» (1976, № 10),
«Геометрический смысл произвольной» (1977, № 2),
«Как выглядит парабола?» (1978, № 3),
«Комбинаторное доказательство формулы Ньютона» (1978, № 8),
«Сложение гармоничских колебаний» (1976, № 11),
«Площадь и интеграл» (1977, № 5),
«Производная показательной функции» (1977, № 12),
«Аналіз помогает алгебре» (1978, № 6),
«Вопросы по алгебре и анализу» (1978, № 2),
«17 задач по анализу» (1977, № 1),

Геометрия

«Освая симметрия» (1976, № 9),
«Композиция двух освых симметрии» (1978, № 2),
«Гомотетия и замечательные точки в треугольнике» (1977, № 10),
«Щест驹 доказательств теоремы о медианах» (1978, № 4),
«Расстояние от точки до плоскости» (1977, № 3),
«Что значит «больше»?» (1977, № 11),
«В поисках определения площади поверхности» (1978, № 5),

---

«Задачи на повторение» (1977, № 9),
«Вопросы для выпускников» (1978, № 7).

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

Р. Мешойр

Комбинаторные доказательства формулы Ньютона

Начался учебный год. Учащся девятых классов скоро познакомятся с таким понятиями как индукция, комбинаторика, биом Ньютона. Оргинальное доказательство формулы Ньютона прислал в редакцию прошлогодный девятиклассик, ученик 444-й Московской школы Роман Мешойр. К его стать мы добавили еще два (более известных) комбинаторных доказательства.

В учебнике «Алгебра и начала анализа 9» в пункте 9 приводится вывод формулы Ньютона.

$$a + b)^n = a^n + C_n^1 a^{n-1} b + \ldots + C_n^k a^{n-k} b^k + \ldots + b^n,$$

основанный на методе математической индукции. Здесь мы приводим комбинаторное доказательство этой формулы (правда, лишь для натуральных a и b).

Рассмотрим такую задачу: скольки способами можно раскрасть n

46

яциков, если имеется a отменков красной краски и b отменков синей.

С одной стороны, таких способов $(a + b)^n$: первый ящик можно раскрасть в любой из $a + b$ оттенков, второй (независимо от первого!) — тоже в любой из $a + b$ оттенков, значит, для первых двух ящиков существует $(a + b)(a + b) = (a + b)^2$ возможных раскраски и т. д.

С другой стороны, число раскрасков равно правой части равенства (1). Показем это, сосчитав это число иначе. Сначала найдем число раскраскок, при которых все $n$ ящиков — красные (их, очень/no, — $a^n$); затем найдем число раскраскок, при которыхровно один ящик — синий (их $nba^{n-1}$), либо имеется $n$ способов выбрать ящик, который мы будем красить синей красной, для него имеется $b$ оттенков, и $a^{n-1}$ раскраскок — для оставшихся $n-1$ ящиков); …; далее найдем число раскраскок, при которых все $n$ ящиков — синее (их $C_n^k b^k a^{n-k}$, либо имеется $C_n^k$ способов выбрать из $n$ ящиков $k$ ящиков, которые мы будем красить синей красной *), для этих $k$ ящиков имеется $b^k$ раскраскок, для оставшихся $n-k$ ящиков существует $a^{n-k}$ раскраскок); …; наконец, найдем число раскраскок, при которых все $n$ ящиков — синее (их $b^n$). Таким образом, общее число раскраскок равно

$$a^n + nba^{n-1} + \dots + C_n^k b^k a^{n-k} + \dots + b^n,$$

а эта сумма совпадает с правой части формулы (1), которая тем самым доказана.

Если вы хорошо поняли это доказательство, то вы сумете доказать обобщение формулы Ньютона на случай $m$ (натуральных) слагаемых:

$$(a_1 + a_2 + \dots + a_m)^n = a_1^n + \dots + N_{k_1 k_2 \dots k_m}^n a_{k_1}^k a_{k_2}^k \dots a_m^k m + \dots + a_m^n,$$

(*) «Алгебра и начала анализа 9», п. 6.