Equazione Diofantea con limitazione sulle incognite

[thebon90]

Ciao a tutti, il mio problema è il seguente:
preso \(s\in\mathbb{N}\) trovare quante sono delle soluzioni intere positive dell'equazione
\[x_1+x_2+\dots+x_n=s\]
tali che
\[x_1\le{}w\quad\forall{}i\in\{1,\dots,n\}\]
con \(w\in\mathbb{N}\) fissato.

Ovviamente bisogna porre \(w\ge\frac{s}{n}\) altrimenti non vi sono soluzioni, però non riesco proprio a contare quante esse siano(se la disuguaglianza invece fosse al contrario non sarebbe un problema in quanto potrei "traslare" il problema).

Inoltre trovare la cardinalità delle soluzioni dell'equazione singola è anch'esso semplice, infatti sono \(\binom{n+s-1}{s}\) visto che si può ricondurre il problema a trovare le combinazioni con ripetizione di \(n\) elementi di lunghezza \(s\).

[robbstark]

Penso si possa risolvere immaginando il problema al contrario, cioè partendo da
$x'_1 = x'_2 = ... = x'_n = w$
$x'_1 + x'_2 = ... + x'_n = nw$
Se $nw < s$ non ci sono soluzioni, come giustamente osservato. Se $nw=s$ c'è 1 sola soluzione.
Se $nw - s = t>0$ il problema diventa di trovare $y_1$, $y_2$, ... $y_n$ tali che
$y_1 + y_2 + ... + y_n = t$
Infatti se poniamo $x_i = x'_i - y_i = w - y_1$ per tutti gli indici, avremo
$x_1 + x_2 + ... + x_n = nw - (y_1 + y_2 + ... + y_n) = nw - t = s$
e $x_i <= w$.
La risposta sarebbe quindi:
\( \binom{n+t-1}{t} \) con $t= nw-s$.

[thebon90]

Grazie ! Non avevo pensato a guardare il problema sotto questo punto di vista!

[thebon90]

Penso si possa risolvere immaginando il problema al contrario, cioè partendo da
$x'_1 = x'_2 = ... = x'_n = w$
$x'_1 + x'_2 = ... + x'_n = nw$
Se $nw < s$ non ci sono soluzioni, come giustamente osservato. Se $nw=s$ c'è 1 sola soluzione.
Se $nw - s = t>0$ il problema diventa di trovare $y_1$, $y_2$, ... $y_n$ tali che
$y_1 + y_2 + ... + y_n = t$
Infatti se poniamo $x_i = x'_i - y_i = w - y_1$ per tutti gli indici, avremo
$x_1 + x_2 + ... + x_n = nw - (y_1 + y_2 + ... + y_n) = nw - t = s$
e $x_i <= w$.
La risposta sarebbe quindi:
\( \binom{n+t-1}{t} \) con $t= nw-s$.

Ora che ci penso meglio però c'è un problema: impostando il tutto in questa maniera non è detto che le \(x_i\) siano positive, infatti basta prendere la soluzione dell'equazione in \(y_i\) formata da \(y_1=t=nw-s\quad\,y_i=0\forall{}i\neq{}1\).

[robbstark]

Lo stesso vale per il problema di partenza, basta fare un esempio con $n=2$ per convincersene.
Probabilmente basta traslare il problema in entrambi i casi?

[thebon9001]

Ho fatto una ricerca più accurata e la risposta si può trovare qui:
http://www331.jpl.nasa.gov/wuism/documents/random/NumberOfBoundedCompositions_WilliamWu.pdf