Дано шесть чисел $a_1$, $a_2$, $\ldots$, $a_6$. Чтобы подсчитать «в лоб» сумму их попарных произведений $a_1 a_2+a_1 a_3+\ldots+a_5 a_6$, нужно затратить 15 умножений и 14 сложений. Покажите, как можно найти сразу сумму этих чисел, сумму их произведений по два, по три, по четыре и по пять, затратив всего 15 сложений и 14 умножений.
Обозначим через $S_n^1$ сумму $n$ первых чисел $a_1+a_2+\ldots+a_n$, через $S_n^k$ — сумму их произведёний по $k$ штук. Тогда мы можем последовательно найти
$$
S_2^1=x_1+x_2,\quad S_2^2=x_1x_2,
$$
затем
$$
S_3^1=S_2^1+x_3,\quad S_3^2=S_2^2+S_2^1\cdot x_3,\quad S_3^3=S_2^2\cdot x_3,
$$
затем $S_n^k$ ($1\le k\le4$), $S_5^k$ ($1\le k\le5$) и, наконец, $S_6^k$ ($1\le k\le5$), пользуясь формулами
$$
S_n^1=S_{n-1}^1+x_n,\quad S_n^k=S_{n-1}^k+S_n^{k-1}\cdot x_n~(1\lt k\lt n),\quad S_n^n=S_{n-1}^{n-1}\cdot x_n.
$$
Для вычисления всех $S_n^k$ ($1\le k\le n$) потребуется $n-1$ сложений и $n-1$ умножений. Таким образом, чтобы сделать это вплоть до $n=6$, нужно $1+2+3+4+5=15$ сложений и столько же умножений. Последнее умножение $S_6^6=S_5^5\cdot x_6$, можно сэкономить, поскольку не требуется считать произведение всех шести чисел.
Эту последовательность операций иллюстрирует схема на рисунке (голубые стрелки — сложения, красные — умножения).
Коротко это решение можно объяснить так. Нам нужно найти коэффициенты многочлена $(x+a_1)(x+a_2)\ldots(x+a_6)$ при $x$, $x^2$, $\ldots$, $x^5$, а мы последовательно находим произведения $x+a_1$ на $x+a_2$, затем на $x+a_3$, $\ldots$, на $x+a_6$.
Аналогично можно доказать, что все суммы произведений $n$ чисел по $k$ ($k=1$, 2, $\ldots$, $n$) можно найти за $1+2+\ldots+(n-1)=\dfrac{n(n-1)}2$ сложений и столько же умножений. Интересно выяснить, можно ли обойтись для этого меньшим числом операций.
