Доказательство. Умножим обе части равенства

Умножим обе части равенства

на (х₁+х₂+…+х_m). Получим

.

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

.

Задача.

Раскрыть скобки и привести подобные члены в выражении (x+y+z)⁴, используя полиномиальную формулу.

Решение.

Ясно, что коэффициенты при x²yz и xy²z равны. Поэтому достаточно найти коэффициенты для таких разбиений n=k₁+k₂+…k_m, что k_1³k_2³…_³k_m, а потом переставлять показатели всеми возможными способами. Для нашего примера имеем:

4=4+0+0; 4=3+1+0; 4=2+2+0; 4=2+1+1;

Р(4,0,0)=1; Р(3,1,0)=4; Р(2,2,0)=6; Р(2,1,1)=12.

(x+y+z)⁴=

=x⁴+y⁴+z⁴+4x³y+4x³z+4y³x+4y³z+4z³x+4z³y+6x²y²+6x²z²+6y²z²+12x²yz+12xy²z+12xyz².

Задача.

Найти коэффициенты при х⁵ после раскрытия скобок и приведения подобных членов в выражении (2+х²-х³)⁹.

Решение.

В задаче нас интересует только коэффициент при х⁵, поэтому нет необходимости искать все коэффициенты. Член, содержащий х⁵, появится только один раз как слагаемое вида 2⁷(х²)¹(-х³)¹, коэффициент при этом члене согласно полиномиальной формуле будет равен Р(7, 1, 1)=72. Следовательно, коэффициент при х⁵ равен (–1) × 2⁷× 72 =–9 216.

Задача.

Найти коэффициенты при х¹² после раскрытия скобок и приведения подобных членов в выражении (1+х²+х⁵)⁸.

Решение.

Данная задача отличается от предыдущей тем, что член, содержащий х¹², появится два раза: как слагаемое вида 1²∙(х²)⁶ (х⁵)⁰ и 1⁵ (х²)¹ (х⁵)². В первом случае коэффициент будет равен Р(2, 6, 0)=28, во втором – Р(5, 1, 2)=168. Следовательно, коэффициент при х¹² равен 28+168=196.

Рекуррентные соотношения.

Задача.

Сколькими способами можно замостить прямоугольную доску размером 2 х 7 костями домино, если все кости считать одинаковыми и учитывать только положение кости: горизонтальное или вертикальное?

Решение.

Обозначим через Ф(k) количество способов замостить костями домино прямоугольную доску размером 2 х k. Угловая клетка может быть закрыта одним из двух способов: либо костью, которая лежит вертикально, тогда оставшуюся k–1 кость можно положить Ф(k–1) способами, либо костью, которая лежит горизонтально, тогда еще одну кость можем положить только горизонтально, а оставшиеся k–2 кости можно уложить Ф(k–2) способами. Используя правило суммы, приходим к соотношению Ф(к)=Ф(к–1)+Ф(к–2). Учитывая, что Ф(0)=Ф(1)=1, можем для любого значения k найти ответ: Ф(2)=2, Ф(3)=3, Ф(4)=5, Ф(5)=8, Ф(6)=13, Ф(7)=21. Имеем 21 способ замостить костями домино прямоугольную доску размером 2 х 7.

При решении многих комбинаторных (и не только) задач часто встречается способ, когда задачу с заданными значениями параметров сводят к аналогичной задаче, но уже с меньшими значениями параметров. Таким образом, можно довести задачу до простой. Данный метод решения задач носит название метода рекуррентных соотношений. (От латинского слова recurrere – возвращаться).