Combinatoire, nombre de solutions

ompak
ompak
dans Arithmétique
Bonjour,
quelle formule (coefficient multinomiaux, partitions, autres) donnerait svp, le nombre de solutions d'une inéquation linéaire en entiers naturels (x1, x2, ..., xn) du type :
a1x1 + a2x2 + ... + an xn =< p,
où les ai sont des coefficients entiers naturels donnés ainsi que p ?
Merci d'avance de vos éclairages.

Réponses

  • gb
    gb
    Bonjour
    As-tu essayé d'étudier le problème pour \(n=2\) et \(n=3\) afin de tester des méthodes susceptibles d'en venir à bout.

    On peut commencer par résoudre l'équation, car l'ensemble des solutions de ton problème est la réunion des ensembles de solution des équations obtenues en faisant varier le second membre de 0 à \(p\), ensembles qui sont disjoints.

    Combien l'équation $ax_1+bx_2=p$ a-t-elle de solutions entières ?
  • ompak
    ompak
    Bonsoir
    Quelle formule donnerait, svp le nombre de solutions dans [N][/k] (entiers naturels) de l'inéquation linéaire à coefficients entiers naturels ai : ]a1.x1 + a2.x2 + ....+ an.xn <= p (p est aussi un entier naturel donné) ?

    Faut -il utiliser les coefficients multinomiaux, les partitions, les coefficients binomiaux, autres ?
    Merci de votre éclairage.

    [Ne pas ouvrir deux discussions avec la même question ! AD]
  • noix de totos
    noix de totos
    En toute généralité, ce nombre est égal à :
    $$\sum_{k=0}^p D_{a_1,\dotsc,a_n} (k)$$
    où $D_{a_1,\dotsb,a_n} (k)$ désigne le dénumérant associé à l'équation diophantienne $a_1 x_1 + \dotsb + a_n x_n = k$.

    Dans le cas général, il n'y a pas de formule simple pour ce dénumérant. On en connaît pour $n=2$, également pour $n=3$ dans certains cas. Le cas général est compliqué, mais il existe :

    (i) Des majorations et minorations de ce nombre ;

    (ii) Des formules asymptotiques lorsque les entiers $a_1,\dotsc,a_n$ sont premiers entre eux dans leur ensemble.

    Edit : je viens de voir que le demandeur avait déjà ouvert un autre fil sur le même sujet, obtenant déjà une réponse de gb.
  • ompak
    ompak
    Merci de vos réponses ; j'avais besoin d'une approximation du nombre de solutions de ce type d'inéquations (ou d'équations, en rajoutant une inconnue) pour obtenir une minoration dans un problème de théorie (analytique des nombres) que voici (peut-être avez-vous une solution plus simple que celle-ci pour résoudre ce problème).

    "Montrer qu'il existe une constante c > 0 et un réel x0 dépendant de l'ensemble P de k nombres premiers {p1, p2, ..., pn} tels que NP(x) >= c (ln(x)^k) pour tout réel x>x0, où NP(x) désigne le cardinal de l'ensemble (fini) des entiers n inférieurs ou égaux à x qui ne s'écrivent dans leur décomposition en facteurs premiers qu'avec des nombres premiers éléments de P".

    NB : a) obtenir une majoration de NP (x) est aisé, une minoration, moins !
    b) Désolé pour le double -post.
  • ompak
    ompak
    Existe t-il des minorations du dénumérant en fonction de (ln k) ^n, svp ?
  • reuns
    reuns
    Ecris en Mathjax si tu veux qu'on continue de te répondre.

    Tu as essayé une récurrence sur le nombre de variables ?

    $f(m,k)$ le nombre de solutions à $\sum_{j=1}^m a_j x_j\le k$ alors $$f(m,k) = \sum_{x_m\le k/a_m} f(m-1,k-x_m a_m)$$ $$\text{ Si } f(m-1,k) \sim C_m k^{m-1} \text{ alors }f(m,k)\sim \sum_{x_m\le k/a_m} C_m (k-x_m a_m)^{m-1} \sim \int_0^{k/a_m} C_m (k-ta_m)^{m-1}dt= C_m \frac{ k^m}{a_m m}$$
    De manière équivalente, quand $k$ est grand le nombre de points entiers dans le tétraèdre des solutions réelles c'est son volume plus $O(k^{m-1})$.
  • ompak
    ompak
    Vu, merci Reuns.
  • noix de totos
    noix de totos
    De manière plus explicite, il existe la minoration suivante, valide lorsque $a_1 = 1$ : $$

    D_{1,a_2,\dotsc,a_n} (k) \geqslant \frac{1}{a_2 \dotsb a_n} {n+k-1 \choose n-1}.

    $$ Si $\textrm{pgcd} \left( a_1, \dotsc , a_k \right) = 1$, alors on a l'estimation classique $$
    D_{a_1,\dotsc,a_n} (k) = \frac{k^{n-1}}{a_1 \dotsb a_n (n-1)!} + O \left( k^{n-2} \right).

    $$ Merci au modérateur qui a fusionné les deux sujets.
    [:-) AD]
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 31

CidrolinMatricule_63biguine_equationgerard0pldx1stfjtotocovzestezorg +22 Invités