Доказательство идентичности биномиального коэффициента с использованием производящей функции

Используем коэффициент оператора$[z^n]$для обозначения коэффициента ряда. Таким образом, мы можем написать, например,

Мы получаем

$$\begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{ (-1)^k \binom{n}{k} \binom{nx-kx}{n+1}}\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\binom{kx}{n+1}\tag{2}\\ &=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[z^{n+1}](1+z)^{kx}\tag{3}\\ &=[z^{n+1}]\left(\left(1+z\right)^x-1\right)^n\tag{4}\\ &=[z^{n+1}]\left(\sum_{j=1}^x\binom{x}{j}z^j\right)^n\tag{5}\\ &=[z]\left(\sum_{j=0}^{x-1}\binom{x}{j+1}z^j\right)^n\tag{6}\\ &\,\,\color{blue}{=nx^{n-1}\binom{x}{2}}\tag{7} \end{align*}$$ и утверждение следует.

Комментарий:

• В (2) меняем порядок суммирования$k\to n-k$.

• В (3) применим коэффициент оператора согласно (1).

• В (4) мы используем линейность коэффициента оператора и применяем биномиальную теорему.

• В (5) мы снова применяем биномиальную теорему.

• В (6) мы сдвигаем индекс, чтобы начать с$j=0$и факторизовать$z^n$применяя правило$[z^p]z^qA(z)=[z^{p-q}]A(z)$.

• В (7) заметим, что для выбора коэффициента$z$в (6) надо взять$j=1$раз и$j=0$для другого$(n-1)$факторы. Это мы делаем$n$раз.

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

Представьте себе$n\times x$сетка объектов. Обе части уравнения являются ответами на вопрос «Сколько способов выбрать$n+1$объекты из этой сетки так, чтобы у каждого был хотя бы один выделенный объект?»

С одной стороны,$\sum_{k=0}^n (-1)^k \binom{n}{k} \binom{nx-kx}{n+1}$отвечает на этот вопрос, используя принцип включения-исключения. Взять все$\binom{nx}{n+1}$способы выбора$n+1$объекты из сетки, затем для каждой строки вычтите$\binom{nx-x}{n+1}$выборки, которые пропускают эту строку. Затем добавьте обратно для каждой пары строк$\binom{nx-2x}{n+1}$выборки, которые пропускают обе эти строки, и так далее.

С другой стороны, если каждая строка покрыта, то должна существовать ровно одна строка с двумя выбранными объектами, а в каждой другой строке выбран ровно один объект. Есть$n$способы выбора строки с двумя выделенными объектами,$\binom x2$способов выбрать два объекта из этой строки, затем$x^{n-1}$способы выбора объектов из оставшихся рядов.