Забавная комбинаторика

[Dave]

Пусть $a$ и $n$ - некоторые натуральные числа. Для любого $i=0,1,\ldots,n$ обозначим через $S_i$ количество решений уравнения

$$x_1+x_2+\ldots+x_n=a$$

в целых числах $x_1,x_2,\ldots,x_n$, таких, что

$$0 \leqslant x_1 \leqslant x_2 \leqslant \ldots \leqslant x_i \, ,$$

$$0<x_{i+1}<x_{i+2}< \ldots <x_n \, .$$

Докажите, что

$$S_0+S_2+S_4+\ldots=S_1+S_3+S_5+\ldots$$

[VoloCh]

Извините, а можете пояснить что такое $S_0$?

[Dave]

$S_0$ - это количество решений уравнения

$$x_1+x_2+\ldots+x_n=a$$

в целых числах $x_1,x_2,\ldots,x_n$, таких, что

$$0<x_1<x_2< \ldots <x_n \,,$$

$S_n$ - это количество решений того же уравнения в целых числах $x_1,x_2,\ldots,x_n$, таких, что

$$0 \leqslant x_1 \leqslant x_2 \leqslant \ldots \leqslant x_n \, .$$

К примеру, при $a=3$, $n=2$: $S_0=1,S_1=3,S_2=2$.

[VoloCh]

и все таки я не въехал... 3=0+3=1+2
Строим сумму двух неотрицательных целых чисел, образующих неубывающую последовательность... Как получается 3 решения? ($S_2=3$)?

[maxal]

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

Пусть $a$ и $n$ - некоторые натуральные числа. Для любого $i=0,1,\ldots,n$ обозначим через $S_i$ количество решений уравнения

$$x_1+x_2+\ldots+x_n=a$$

в целых числах $x_1,x_2,\ldots,x_n$, таких, что

$$0 \leqslant x_1 \leqslant x_2 \leqslant \ldots \leqslant x_i \, ,$$

$$0<x_{i+1}<x_{i+2}< \ldots <x_n \, .$$

Докажите, что

$$S_0+S_2+S_4+\ldots=S_1+S_3+S_5+\ldots$$

Имеем:

$$S_i = [y^a] \left([z^i] \prod_{j=0}^{\infty} (1 - y^j z)^{-1}\right) \cdot \left( [z^{n-i}] \prod_{j=1}^{\infty} (1 + y^j z)\right).$$

Соответственно

$$\sum_{i=0}^{\infty} (-1)^i S_i = [y^a] \sum_{i=0}^{\infty} \left([z^i] \prod_{j=0}^{\infty} (1 + y^j z)^{-1}\right) \cdot \left( [z^{n-i}] \prod_{j=1}^{\infty} (1 + y^j z)\right) = [y^a z^n] (1+z)^{-1}.$$

Последнее выражение равно нулю для $a>0$.

[Dave]

maxal, здесь некоторые люди двойку с тройкой путают, а Вы сразу за производящие взялись .
Есть и очень простое комбинаторное решение.