Суммы обратных произведений

[Dave]

Пусть $n$ и $S$ - натуральные числа, $S \geqslant n$. Будем рассматривать упорядоченные наборы из $n$ натуральных чисел, не превосходящих $S$. В первую группу отнесём все такие наборы, в которых сумма чисел не превосходит $S$, но как минимум одно число повторяется, а во вторую - те, в которых, наоборот, сумма чисел строго больше $S$ и все числа попарно различны. Каждому набору сопоставим обратную величину произведения всех чисел набора и просуммируем такие величины по всем наборам в каждой группе отдельно. Докажите, что полученные cуммы всегда будут равны.
Например, при $n=3$, $S=4$:

$$\frac 1 {1\cdot1\cdot1}+\frac 1 {1\cdot1\cdot2}+\frac 1 {1\cdot2\cdot1}+\frac 1 {2\cdot1\cdot1}=6\left(\frac 1 {1\cdot2\cdot3}+\frac 1 {1\cdot2\cdot4}+\frac 1 {1\cdot3\cdot4}+\frac 1 {2\cdot3\cdot4}\right).$$

[Dave]

Упрощу задачу. Докажите, что

$$\sum_{x_1+\ldots+x_n \leqslant S} \; {\frac 1 {\prod\limits_{i=1}^n {x_i}}}=\sum_{\substack{\max\limits_{i=1}^n {x_i} \leqslant S,\\ i \ne j \, \Rightarrow \, x_i \ne x_j}} \frac 1 {\prod\limits_{i=1}^n {x_i}}.$$

[maxal]

Dave в сообщении #738610 писал(а):

Пусть $n$ и $S$ - натуральные числа, $S \geqslant n$. Будем рассматривать упорядоченные наборы из $n$ натуральных чисел, не превосходящих $S$. В первую группу отнесём все такие наборы, в которых сумма чисел не превосходит $S$, но как минимум одно число повторяется, а во вторую - те, в которых, наоборот, сумма чисел строго больше $S$ и все числа попарно различны. Каждому набору сопоставим обратную величину произведения всех чисел набора и просуммируем такие величины по всем наборам в каждой группе отдельно. Докажите, что полученные cуммы всегда будут равны.

Одна сумма равна:

$$\sum_{s=1}^S [x^ny^s] \left( \left(\sum_{i=1}^{\infty} \frac{xy^i}{i}\right)^n - n! \prod_{i=1}^S \left(1+\frac{xy^i}{i}\right)\right)$$

Другая сумма:

$$\sum_{s=S+1}^{\infty} [x^ny^s] n! \prod_{i=1}^S \left(1+\frac{xy^i}{i}\right)$$

Таким образом, нужно доказать, что

$$\sum_{s=1}^S [y^s] \left(\sum_{i=1}^{\infty} \frac{y^i}{i}\right)^n = [x^n] n! \prod_{i=1}^S \left(1+\frac{x}{i}\right)$$

или

$$[y^S] \frac{\left(-\ln(1-y))^n}{1-y} = \frac{n!}{S!} \left[{S+1\atop n+1}\right]$$

Ну а чтобы получить последнее равенство, достаточно продифференцировать производящую функцию чисел Стирлинга 1-го рода:

$$\sum_{j=n}^\infty \left[{j\atop n+1}\right] \frac{y^j}{j!} = (-1)^{n+1} \frac{\left(\log (1-y)\right)^{n+1}}{(n+1)!}$$

по $y$ и взять коэффициент при $y^S$.

[Dave]

Как-то это слишком сложно. Хотя я и получил это тождество, когда крутил дзета-функцию Римана. Решение через производящие функции у меня тоже было, только чисел Стирлинга 1-го рода там, насколько я помню, не было (или я не обратил внимания, что это именно они).

А очень простое решение - двойная индукция. Утверждение для $(S,n)$ следует из утверждений для $(S-1,n)$ и $(S-1,n-1)$.

[maxal]

По индукции, может, и проще, но подноготную этого тождества не видно. Решение через производящие тоже не так уж сложно и позволяет понять природу тождества и его связь с классическими объектами (такими как числа Стирлинга 1-го рода).