ax+by=N Как найти количество решений в целых неотрицательных

[Tereha]

Кто нибудь может подсказать где можно посмотреть как определить количество решений в целых неотрицательных числах уравнения вида ax+by=n (или для 3 переменных). Из разряда сколькими способами можно разменять n монетами заданных номиналов. Примерные ответы
для случая двух номиналов
hN = N/ab + (a+b)/2ab + period (=переодич. ф-я с периодом ab и
нулевым сред. знач.)
1, p - номиналы
N = x1+px2; hN=1 + [N/p]
Пример (2,3):
N = 2x1+3x2;
hN = 1 + [N/2] - [(N+2)/3]
hN = 1 + [2N/3] - [(N+1)/2] (- одинаковые реш-я?)
Формула разложения суммы N на монеты 5 и 3. Сколькмими
способами можно разложить?
hN = 1 + [2N/5] - [(N+2)/3]
p,p+1 - номиналы:
N = px1+(p+1)x2;
3 монеты: 1, p, pq
N = x1 + px2 + pqx3, x1,x2,x3 >0
hN = [N/p]+1+[[N/p]/q]([N/p] + 1 - q/2 -q/2[[N/p]/q])
Пример: 1,3,5:
N = x1 + 3x2 + 5x3
hN = N+1+N(N-1)/4 -(...

[Joker_vD]

Линейные диофантовы уравнения. Насчет конкретно $ax+by=n$ — оно равносильно решению сравнения $ax \equiv n \pmod{b}$. Легко показывается, что оно либо имеет бесконечно много решений при $(a,b) \mid n$ и не имеет решений вовсе, если $(a,b) \nmid n$

Есть книга Серпинского "О решении уравнений в целых числах", посмотрите ее.

[Tereha]

1. В Серпинском ответа на мой вопрос нет.
2. Диафантово уравнение решается просто в целых числах. А в данном случае - неотрицательные. И там дается просто решение, а мне нужна оценка количества решений.
Скажем для двух монет номиналами 2 и 3. Решение приведено в первом сообщении. Пока не могу понять как его получить - кажется можно просто догадаться, но не получается

[Leox]

Tereha в сообщении #426377 писал(а):

1. В Серпинском ответа на мой вопрос нет.
2. Диафантово уравнение решается просто в целых числах. А в данном случае - неотрицательные. И там дается просто решение, а мне нужна оценка количества решений.
Скажем для двух монет номиналами 2 и 3. Решение приведено в первом сообщении. Пока не могу понять как его получить - кажется можно просто догадаться, но не получается

В принципе можно показать, что количество решений $2x+3y=n$ равно

$$ 1/3\,\cos \left( 2/3\,\pi \,n \right) -1/9\,\sqrt {3}\sin \left( 2/3\, \pi \,n \right) +1/6\,n+1/4\,\cos \left( \pi \,n \right) +{\frac {5}{ 12}} $$

а $3x+5y=n$ равно
\begin{gather*} 1/3\,\cos \left( 2/3\,\pi \,n \right) -1/9\,\sqrt {3}\sin \left( 2/3\, \pi \,n \right) +1/15\,n+1/20\,\sqrt {10-2\,\sqrt {5}}\sin \left( 4/5 \,\pi \,n \right) +{\frac {3}{100}}\,\sqrt {5}\sqrt {10-2\,\sqrt {5}} \sin \left( 4/5\,\pi \,n \right) -\\-{\frac {3}{100}}\,\sqrt {5}\sqrt {10 +2\,\sqrt {5}}\sin \left( 2/5\,\pi \,n \right) +1/20\,\sqrt {10+2\, \sqrt {5}}\sin \left( 2/5\,\pi \,n \right) +1/5\,\cos \left( 2/5\,\pi \,n \right) +1/5\,\cos \left( 4/5\,\pi \,n \right) +{\frac {4}{15}} \end{gather*}
хотя ето мало что даст :)

[Sonic86]

Если уравнение $ax+by=N$ разрешимо, то оно имеет общее решение вида $x=x_0+tk, y=y_0-tk, t=\frac{ab}{\gcd (a;b)}, k \in \mathbb{Z}$, а решение $x_0,y_0$ находится алгоритмом Евклида. Это решение в целых числах. Затем надо ограничить $x \geq 0, y \geq 0$ и уже вычислить число решений. Это в каждом конкретном случае. В общем случае кроме того, что Вы сказали, я не скажу.
Еще, помнится, число решений с помощью ТФКП как-то находится...

[AKM]

Тема перемещена из "Помогите решить (М)" в карантин для исправления написания формул в первом сообщении.

Tereha, здесь рассказано, как набирать формулы.
Используйте кнопку для редактирования своего сообщения.
Как исправите - пишите сюда, чтобы тему вернули.