Au sujet d'un problème de dénombrement
Bonjour à tous
J'ai une question de curiosité.
En travaillant sur un sujet de modélisation avec un ami nous nous sommes heurtés à une question qui sort un peu du cadre et nous ne savons pas vraiment comment y répondre.
Le cadre est le suivant.
--------------
On se place sur le quadrillage $X = \{1, \dots, N^2\}$. Sur chacun des points du quadrillage on peut placer soit un composé chimique $\alpha$, soit un composé chimique $\beta$, soit laisser le point vide.
Si on les identifie respectivement aux nombres $-1$, $1$ et $0$, on se retrouve alors avec l'ensemble de configuration $\{-1,0,1\}^X$.
On dit qu'une configuration est autorisée si un composé $\alpha$ n'est jamais à côté d'un composé $\beta$ (Par "à côté" j'entends sur un point voisin horizontalement ou verticalement parlant, pas en diagonale).
--------------
On aimerait dénombrer le nombre de configuration autorisées. Il existe un grand nombre de configurations qui s'élève à $(N^2)^3$. Nous n'arrivons pas à aboutir à un résultat.
Pour le cas $X = \{1,2\}$ on a compté 42 configurations autorisées sur les 64 possibles. Pour cela on a compté le nombre de configurations où l'on rejette en essayant de trouver une intuition de généralisation mais en vain.
Pour une configurations à $N^2$ points on a constaté que :
- $4$ points ont deux voisins (les coins de quadrillage)
- $4(N-2)$ points ont trois voisins (les points des arêtes du quadrillage dans les coins)
- $N^2 - 4(N-1)$ points ont quatre voisins (les points restants)
Mais nous ne savons pas si c'est utile
J'en appelle donc à votre aide, je ne sais pas si cela a déjà été fait quelque part.
J'ai une question de curiosité.
En travaillant sur un sujet de modélisation avec un ami nous nous sommes heurtés à une question qui sort un peu du cadre et nous ne savons pas vraiment comment y répondre.
Le cadre est le suivant.
--------------
On se place sur le quadrillage $X = \{1, \dots, N^2\}$. Sur chacun des points du quadrillage on peut placer soit un composé chimique $\alpha$, soit un composé chimique $\beta$, soit laisser le point vide.
Si on les identifie respectivement aux nombres $-1$, $1$ et $0$, on se retrouve alors avec l'ensemble de configuration $\{-1,0,1\}^X$.
On dit qu'une configuration est autorisée si un composé $\alpha$ n'est jamais à côté d'un composé $\beta$ (Par "à côté" j'entends sur un point voisin horizontalement ou verticalement parlant, pas en diagonale).
--------------
On aimerait dénombrer le nombre de configuration autorisées. Il existe un grand nombre de configurations qui s'élève à $(N^2)^3$. Nous n'arrivons pas à aboutir à un résultat.
Pour le cas $X = \{1,2\}$ on a compté 42 configurations autorisées sur les 64 possibles. Pour cela on a compté le nombre de configurations où l'on rejette en essayant de trouver une intuition de généralisation mais en vain.
Pour une configurations à $N^2$ points on a constaté que :
- $4$ points ont deux voisins (les coins de quadrillage)
- $4(N-2)$ points ont trois voisins (les points des arêtes du quadrillage dans les coins)
- $N^2 - 4(N-1)$ points ont quatre voisins (les points restants)
Mais nous ne savons pas si c'est utile
J'en appelle donc à votre aide, je ne sais pas si cela a déjà été fait quelque part.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Il faudrait peut-être utiliser des astuces du genre de celles utilisées pour le modèle d'Ising en physique statistique.
Edit : En fait, je n'obtiens que $|A| \geqslant 2^{N^2 + 1} + 2^{3 N-4} - 1$. Le $3^{(N-2)^2}$ était dû à une erreur.
C'est un problème extrêmement difficile, et il me semble impossible de calculer explicitement (même numériquement avec une bonne précision) le $c$ tel que $|A_N|\sim c^{N^2+o(N^2)}$.
Il reste donc à compter : les configurations avec uniquement $\alpha$, uniquement $\beta$, ou les deux. J'obtiens
$$2^4+2^4 -1 \ \text{ (la config vide comptée deux fois)} +4 \ \text{(les configs spéciales)}=35.$$
En recollant tous mes mini-carrés j'ai peut-être une configuration qui marche, ou peut-être pas. Cela me donne une borne supérieure :
1 -> 3 et 3.0
2 -> 35 et 2.4322992790977875
3 -> 2021 et 2.329620320987932
4 -> 536453 et 2.2808447746115874
5 -> 661407975 et 2.2532987567868705
1 -> 3 et 1.3160740129524924
2 -> 35 et 1.4844415983612418
3 -> 2021 et 1.6091550576738098
4 -> 536453 et 1.6950451358446328
5 -> 661407975 et 1.7579763962116806
$$|A_N|\leq 1858...33755^{\lfloor N/10\rfloor ^2}\approx 2.20136...^{N^2+o(N^2)}$$