Задача про stars and bars

Математика Комбинаторика
6

Комментарий 1: \binom{n}{k} это другой формат записи C_{n}^{k}
По методу шаров и перегородок (stars and bars) мы считаем следующую сумму:

\binom{3}{3} + \binom{3}{4} + \binom{3}{5} + ... + \binom{3}{2009}.

Вспомним тождество:

\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.

Тогда добавим к нашей сумме \binom{3}{4} = 0:

\binom{3}{4} + \binom{3}{3} + \binom{4}{3} + \binom{5}{3} + ... + \binom{2009}{3} = \binom{4}{4} + \binom{4}{3} + \binom{5}{3} + \binom{6}{3} ... + \binom{2009}{3} = \\= \binom{5}{4} +\binom{5}{3}+ \binom{6}{3} ... + \binom{2009}{3} = ... = \binom{2009}{4} + \binom{2009}{3} = \binom{2010}{4}.

Подобные тождества с биномиальными коэффициентами можно найти здесь:
Полезные комбинаторные тождества - Математика / Комбинаторика - Спроси! | Beyond Curriculum (bc-pf.org)

Комментарий 2:
Многие комбинаторные тождества имеют и комбинаторные доказательства, и алгебраические доказательства. Алгебраические часто используют индукцию. Комбинаторные же более идейные, но это и помогает запоминать тождества лучше.
Так например, я всегда вспоминаю тождество

\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1},

через его доказательство. Доказательство верности тождества:
Предположим нам нужно выбрать k+1 элемент из множества мощности n+1. Рассмотрим какой-нибудь элемент множества, скажем E.
Существует ровно \binom{n}{k} способов выбрать k+1 элемент, среди которых обязательно есть элемент E. Также существует ровно \binom{n}{k+1} способов выбрать k+1 элемент, среди которых нет элемента E. Таким образом всего способов выбрать k+1 элемент из n+1

\binom{n}{k} + \binom{n+1}{k}.

С другой стороны, это просто \binom{n+1}{k+1}. Поэтому

\binom{n}{k} + \binom{n+1}{k} = \binom{n+1}{k+1}

В этом посте аска тоже показан пример комбинаторного доказательства.
Здесь тоже есть комбинаторное доказательство.

5 лайков