Число целых неотр. решений системы диофантовых уравнений

[Leox]

Хорошо известно что число целых неотрицательных решений линейного уравнения вида
\alpha_1 a_1+\alpha_2 a_2+\cdots \alpha_n a_n= N где все a_i,N \in \mathbb{Z}_{+} равно коэффициенту при N в разложении ряда

$$ \frac{1}{(1-x^{a_1}) (1-x^{a_2})\cdots (1-x^{a_n})}. $$

Можно ли подобным образом найти количество решений системы таких уравнений, например

$$ \left \{ \begin{array}{l} \alpha_1 a_1+\alpha_2 a_2+\cdots + \alpha_n a_n= N_1 \\ \beta_1 b_1+\beta_2 b_2+\cdots +\beta_n n_n= N_2 \end{array} \right. $$

Имеется ввиду - есть рациональная функция, возможно от двух переменных, скажем x,y, такая что коэффициент возле x^{N_1} y^{N_2} и есть число решений?

[maxal]

Leox писал(а):

Можно ли подобным образом найти количество решений системы таких уравнений, например

$$ \left \{ \begin{array}{l} \alpha_1 a_1+\alpha_2 a_2+\cdots + \alpha_n a_n= N_1 \\ \beta_1 b_1+\beta_2 b_2+\cdots +\beta_n n_n= N_2 \end{array} \right. $$

Имеется ввиду - есть рациональная функция, возможно от двух переменных, скажем x,y, такая что коэффициент возле x^{N_1} y^{N_2} и есть число решений?

Наверное, имеется в виду система

$$\begin{cases} \alpha_1 a_1+\alpha_2 a_2+\cdots + \alpha_n a_n= N_1 \\ \beta_1 a_1+\beta_2 a_2+\cdots +\beta_n a_n= N_2 \end{cases}$$

Если так, то количество ее неотрицательных решений - это коэффициент при $x^{N_1} y^{N_2}$ в разложении

$$\frac{1}{(1-x^{\alpha_1} y^{\beta_1})\dots (1-x^{\alpha_n} y^{\beta_n})}.$$

[Leox]

Да, именно это я имел ввиду, извините за несколько сумбурную постановку задачи. Большое спасибо.


А где можно об этом можно почитать?

[maxal]

Leox писал(а):

А где можно об этом можно почитать? Меня интересует техника манипуляций с такого рода выражениями - пусть \omega_n(N_1,N_2) -- количество решений указанного уравненния.
Нужно найти значения выражений вида, например \omega_n(N_1,N_2)-\omega_n(N_1-1,N_2)+\omega_n(N_1,N_2+1), не используя три различных разложения. Более точно -- нужно найти рациональную функцию, числитель которой возможно уже не равен 1, такую что в ее разложении некоторый коэфициент равен указанному выражению \omega_n(N_1,N_2)-\omega_n(N_1-1,N_2)+\omega_n(N_1,N_2+1) .

Ну так это коэффициент при $x^{N_1} y^{N_2+1}$ в

$$\frac{y-xy+1}{(1-x^{\alpha_1} y^{\beta_1})\dots (1-x^{\alpha_n} y^{\beta_n})}.$$

Почитать можно любую книжку, где учат обращаться с производящими функциями. В данном случае весь трюк основан на том, что коэффициент при $x^m$ в функции $f(x)$ равен коэффициенту при $x^{m+1}$ в $x\cdot f(x)$.

[Leox]

Еще раз спасибо

[eugrita]

А меня интересует похожая тема о числе решений сравнения с 2 неизвестными вида $ax+by \equiv c (\mod m)$
где $x_1 \le x \le x_2,y_1 \le y \le y_2 $
(в частности это могут быть ограничения для 10-ичных цифр
$0 \le x,y \le 9 $
я так понимаю ,1й шаг сведение к диофантовому уравнению с 3 переменными
$a x+by+mz=c$

[maxal]

eugrita в сообщении #767886 писал(а):

А меня интересует похожая тема о числе решений сравнения с 2 неизвестными вида $ax+by \equiv c (\mod m)$
где $x_1 \le x \le x_2,y_1 \le y \le y_2 $
(в частности это могут быть ограничения для 10-ичных цифр
$0 \le x,y \le 9 $
я так понимаю ,1й шаг сведение к диофантовому уравнению с 3 переменными
$a x+by+mz=c$

Не совсем. Вам нужно рассмотреть ряд

$$(t^{ax_1}+t^{a(x_1+1)}+\dots+t^{ax_2})\cdot(t^{by_1}+t^{b(y_1+1)}+\dots+t^{by_2}) = t^{ax_1+by_1}\frac{(1-t^{a(x_2-x_1+1)})(1-t^{b(y_2-y_1+1)})}{(1-t^a)(1-t^b)}$$

и просуммровать коэффициенты при степенях вида $t^{c+mz}$, где $z$ пробегает целые числа.
Это делается с помощью мультисекции.