Количество одночленов от n переменных полной степени m

[student1138]

Здравствуйте. Помогите, пожалуйста, решить задачу:

Цитата:

Используя принцип двойной индукции, показать, что число различных одночленов от $n$ независимых переменных полной степени $m$ равно $\binom{m + n - 1}{m}$

Как я понял, нужно сначала при фиксированном $m$ доказать формулу по индукции для $n$ а затем при фиксированном $n$ доказать по индукции по $m$. В общем два независимых доказательства, по существу. Продвинуться мне удалось немного:

Для фиксированного $m$:
Добавляем еще одну переменную $X_{n+1}$ степени от $1$ до $m$. Cтепень одночлена $X_{1}...X_{n}$ соответственно понижается. И все складываем. Получается примерно такая сумма:
$\binom{m+n-1}{m} + \binom{m-1+n-1}{m-1} + \binom{m-2+n-1}{m-2} + ... + \binom{m-m + n-1}{m-m}$. Только вот как это свернуть это красиво и сделать индуктивный переход не получается.

Для фиксированного $n$ еще хуже. Я только могу в голове представить как написать рекурсивную функцию, перебирающую все одночлены. А вот как это превратить в доказательство по индукции мыслей нет.

[VAL]

Пусть наши переменные суть $x_1, x_2,\dots,x_n$.
Нарисуем в ряд $m+n-1$ кружочек, затем вычеркнем $n-1$ из них.
Количество кружочков до первого вычеркнутого примем за показатель степени у $x_1$.
Количество кружочков от первого вычеркнутого до второго вычеркнутого примем за показатель степени у $x_2$.
. . . . .
Количество кружочков после последнего вычеркнутого примем за показатель степени у $x_n$.
Докажите, что между всеми способами вычеркивания кружочков и всеми мономами $m$-й степени от $n$ переменных есть биективное соответствие.

Ну, а посчитать сколькими способами можно вычеркнуть $n-1$ кружочек, Вы, надеюсь сможете.
И никакой индукции.

[Brukvalub]

student1138, вы правильно рассуждаете.

student1138 в сообщении #1171448 писал(а):

Только вот как это свернуть это красиво и сделать индуктивный переход не получается.

Такого рода суммы легко вычисляются. Например, нужная вам сумма вычислена на стр. 185 в Конкретной математике. В том же разделе названной книги учат сворачивать и более сложные суммы с биномиальными коэффициентами.

[DeBill]

student1138 в сообщении #1171448 писал(а):

как это свернуть это красиво

Последнее число в сумме равно 1. Замените в нем верхний индекс большим на единицу - по фигу, это все равно будет 1. А теперь по известной формуле - про сумму двух соседних биноминальных - справа налево все - бамс - и свернется.

[student1138]

Конкретную математику прочитал, свою сумму понял как сворачивать, так что для фиксированного $m$ доказательство ясно. Доказательство VAL тоже понял. Однако, раз уж в учебнике предлагается сделать двойную индукцию, и раз уж одну индукцию мы сделали, то хотелось сделать и вторую индукцию (для фиксированного $n$). А вот тут не могу придумать как сделать индуктивный переход.

[Brukvalub]

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

[student1138]

Brukvalub в сообщении #1172182 писал(а):

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

Базу индукции проверить не сложно - при фиксированном $n$ и $m = 1$ в соответствии с формулой количество различных одночленов степени $1$ от $n$ независимых переменных равно $n$, что действительно так.

Предположим, что формула верна для одночленов $X_1...X_n$ полной степени $m$. Нужно показать что тогда формула будет верна и для степени $m + 1$. Для этого, как я понимаю, нужно число одночленов степени $m+1$ как-то записать отталкиваясь от числа одночленов степени $m$. Наподобие как я это сделал при доказательстве для фиксированного $m$. Вот тут загвоздка - не могу придумать как это сделать.