bulgakov

28. Полиномиальная формула

Бином Ньютона раскрывает степень суммы двух слагаемых, а полиномиальная формула — степень суммы любого числа слагаемых: (x1+x2+⋯+xr)n=∑n!d1! d2!⋯dr!x1d1x2d2⋯xrdr(x_1+x_2+\dots+x_r)^n=\sum\dfrac{n!}{d_1!\,d_2!\cdots d_r!}x_1^{d_1}x_2^{d_2}\cdots x_r^{d_r}. Коэффициент при одночлене — это число слов, в которых буква xix_i встречается ровно did_i раз.

Что пригодится из прошлого: бином Ньютона — идея «выбираем слагаемое из каждой скобки»; перестановки с повторяющимися элементами — число слов с заданными кратностями букв; число решений уравнения — сколько одночленов получится. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Начнём с трёх слагаемых

Раскроем (x+y+z)3=(x+y+z)(x+y+z)(x+y+z)(x+y+z)^3=(x+y+z)(x+y+z)(x+y+z). Из каждой скобки выбираем одно из трёх слагаемых: всего 33=273^3=27 выборов. Одинаковые одночлены собираем вместе. Например, x2yx^2y получается из выборов xxyxxy, xyxxyx, yxxyxx — их три, и коэффициент равен 33. А xyzxyz получается шестью способами (xyz,xzy,yxz,yzx,zxy,zyxxyz,xzy,yxz,yzx,zxy,zyx). Полный итог:

(d1,d2,d3)(d_1, d_2, d_3) Коэфф. Одночлен
(3, 0, 0) 1 x3x^3
(2, 1, 0) 3 x2yx^2y
(2, 0, 1) 3 x2zx^2z
(1, 2, 0) 3 xy2xy^2
(1, 1, 1) 6 xyzxyz
(1, 0, 2) 3 xz2xz^2
(0, 3, 0) 1 y3y^3
(0, 2, 1) 3 y2zy^2z
(0, 1, 2) 3 yz2yz^2
(0, 0, 3) 1 z3z^3
сумма 27

Одночленов получилось 1010, коэффициентов в сумме 27=3327=3^3 — как выборов. Коэффициент при xd1yd2zd3x^{d_1}y^{d_2}z^{d_3} оказался равным 3!d1! d2! d3!\dfrac{3!}{d_1!\,d_2!\,d_3!}. Из главы про слова с повторяющимися буквами мы знаем, что это в точности число слов длины 33, где xx встречается d1d_1 раз, yy — d2d_2 раз и zz — d3d_3 раз.

Теорема

Теорема (полиномиальная формула). Для любого n∈Nn\in\mathbb N

(x1+x2+⋯+xr)n=∑d1+d2+⋯+dr=nn!d1! d2!⋯dr! x1d1x2d2⋯xrdr.\boxed{(x_1+x_2+\cdots+x_r)^n=\sum_{d_1+d_2+\cdots+d_r=n}\frac{n!}{d_1!\,d_2!\cdots d_r!}\,x_1^{d_1}x_2^{d_2}\cdots x_r^{d_r}}.

Здесь суммируют по всем наборам целых неотрицательных чисел (d1,…,dr)(d_1,\dots,d_r), сумма которых равна nn.

Как читать. Знак ∑d1+⋯+dr=n\sum_{d_1+\dots+d_r=n} — «сумма по всем наборам показателей, дающим в сумме nn». Для каждого набора записан одночлен x1d1⋯xrdrx_1^{d_1}\cdots x_r^{d_r} и коэффициент — число перестановок с повторениями. При r=2r=2 получаем бином Ньютона: n!k! (n−k)!=(nk)\dfrac{n!}{k!\,(n-k)!}=\dbinom nk.

Доказательство. Запишем степень как произведение nn одинаковых скобок:

(x1+⋯+xr)n=(x1+⋯+xr)⋯(x1+⋯+xr)⏟n штук.(x_1+\dots+x_r)^n=\underbrace{(x_1+\dots+x_r)\cdots(x_1+\dots+x_r)}_{n\text{ штук}}.

Чтобы получить одночлен x1d1x2d2⋯xrdrx_1^{d_1}x_2^{d_2}\cdots x_r^{d_r}, где d1+⋯+dr=nd_1+\dots+d_r=n, нужно:

  1. выбрать d1d_1 скобок из nn и взять в них x1x_1: (nd1)\dbinom n{d_1} способов;
  2. из оставшихся n−d1n-d_1 скобок выбрать d2d_2 и взять в них x2x_2: (n−d1d2)\dbinom{n-d_1}{d_2} способов;
  3. и так далее; последние drd_r скобок остаются для xrx_r.

Каждая скобка отдаёт ровно одно слагаемое, поэтому выбранные группы скобок не пересекаются, и каждому такому выбору отвечает ровно один одночлен.

Коэффициент при одночлене — число таких выборов:

(nd1)(n−d1d2)(n−d1−d2d3)⋯(n−d1−⋯−dr−1dr).\binom n{d_1}\binom{n-d_1}{d_2}\binom{n-d_1-d_2}{d_3}\cdots\binom{n-d_1-\dots-d_{r-1}}{d_r}.

Запишем каждый множитель через факториалы:

n!d1! (n−d1)!⋅(n−d1)!d2! (n−d1−d2)!⋅(n−d1−d2)!d3! (n−d1−d2−d3)!⋯\frac{n!}{d_1!\,(n-d_1)!}\cdot\frac{(n-d_1)!}{d_2!\,(n-d_1-d_2)!}\cdot\frac{(n-d_1-d_2)!}{d_3!\,(n-d_1-d_2-d_3)!}\cdots

Числитель каждой дроби сокращается со знаменателем предыдущей. Остаётся n!d1! d2!⋯dr!\dfrac{n!}{d_1!\,d_2!\cdots d_r!} (последний знаменатель содержит (n−d1−⋯−dr)!=0!=1(n-d_1-\dots-d_r)!=0!=1). □\square

Сколько получится одночленов

Одночленов столько же, сколько наборов (d1,…,dr)(d_1,\dots,d_r) с суммой nn — то есть сколько целых неотрицательных решений уравнения d1+⋯+dr=nd_1+\dots+d_r=n. Из главы про такие уравнения их (n+r−1r−1)\dbinom{n+r-1}{r-1}. (В той главе число переменных обозначали nn, а сумму kk; здесь число переменных rr, а сумма nn — отсюда другая запись.) Для (x+y+z)3(x+y+z)^3: (52)=10\dbinom{5}{2}=10 — как в таблице.

Следствие

Следствие.

∑d1+⋯+dr=nn!d1! d2!⋯dr!=rn.\boxed{\sum_{d_1+\dots+d_r=n}\frac{n!}{d_1!\,d_2!\cdots d_r!}=r^n}.

Доказательство. Подставим x1=x2=⋯=xr=1x_1=x_2=\dots=x_r=1 в полиномиальную формулу. Слева (1+⋯+1)n=rn(1+\dots+1)^n=r^n, справа все одночлены равны 11, остаются коэффициенты. □\square

Смысл. Слева — все слова длины nn в алфавите из rr букв, разложенные по числу появлений каждой буквы; справа — их общее число rnr^n. Для r=3r=3, n=3n=3 в таблице выше три коэффициента 11, шесть коэффициентов 33 и один коэффициент 66: 3⋅1+6⋅3+1⋅6=273\cdot1+6\cdot3+1\cdot6=27 — все слова из трёх букв, сгруппированные по составу.

Примеры

1. Один коэффициент. Найти коэффициент при x2yz2x^2yz^2 в (x+y+z)5(x+y+z)^5. Показатели (2,1,2)(2,1,2), сумма 55: 5!2! 1! 2!=1204=30\dfrac{5!}{2!\,1!\,2!}=\dfrac{120}{4}=30.

2. Три буквы, четыре степени. Коэффициент при ab2cab^2c в (a+b+c)4(a+b+c)^4: 4!1! 2! 1!=12\dfrac{4!}{1!\,2!\,1!}=12.

3. Сколько одночленов. В (a+b+c+d)5(a+b+c+d)^5 после приведения подобных получается (5+4−14−1)=(83)=56\dbinom{5+4-1}{4-1}=\dbinom83=56 одночленов.

Частые ошибки

  • Показатели не в сумме nn. Для каждого одночлена d1+⋯+dr=nd_1+\dots+d_r=n.
  • Использовать бином вместо полиномиальной формулы. При r≥3r\ge3 один биномиальный коэффициент не годится — нужны факториалы всех показателей.
  • Забыть про коэффициенты у чисел. В (2a+b+3c)n(2a+b+3c)^n множители 22 и 33 возводятся в степени вместе с буквами.
  • Считать число одночленов как rnr^n. rnr^n — число выборов (и сумма коэффициентов), а одночленов после приведения подобных меньше: (n+r−1r−1)\dbinom{n+r-1}{r-1}.

Проверь себя

1. Раскройте (x+y+z)2(x+y+z)^2.

Решение

Показатели с суммой 22: (2,0,0)(2,0,0), (0,2,0)(0,2,0), (0,0,2)(0,0,2) с коэффициентом 2!2!=1\dfrac{2!}{2!}=1 и (1,1,0)(1,1,0), (1,0,1)(1,0,1), (0,1,1)(0,1,1) с коэффициентом 2!1!1!=2\dfrac{2!}{1!1!}=2. Итого x2+y2+z2+2xy+2xz+2yzx^2+y^2+z^2+2xy+2xz+2yz. Проверка: при x=y=z=1x=y=z=1 слева 99, справа 3+6=93+6=9.

2. Найдите коэффициент при x2y3zx^2y^3z в (x+y+z)6(x+y+z)^6.

Решение

6!2! 3! 1!=72012=60\dfrac{6!}{2!\,3!\,1!}=\dfrac{720}{12}=60.

3. Чему равна сумма всех коэффициентов в разложении (x+y+z+w)3(x+y+z+w)^3?

Решение

Подставим единицы: 43=644^3=64.

4. Сколько одночленов в (x+y+z)4(x+y+z)^4 после приведения подобных?

Решение

Показатели (d1,d2,d3)(d_1,d_2,d_3) с суммой 44: (4+3−13−1)=(62)=15\dbinom{4+3-1}{3-1}=\dbinom62=15.

Итог

  • Степень суммы rr слагаемых раскрывается как выбор слагаемого из каждой из nn скобок.
  • Коэффициент при x1d1⋯xrdrx_1^{d_1}\cdots x_r^{d_r} равен n!d1!⋯dr!\dfrac{n!}{d_1!\cdots d_r!} — число слов, в которых буква xix_i встречается ровно did_i раз.
  • Сумма всех коэффициентов равна rnr^n; одночленов (n+r−1r−1)\dbinom{n+r-1}{r-1}.
ПрактикаЗагружаем тест…