Nombres de zones (maximum 3x3) dans une grille

PetitLutinMalicieux

Bonjour
Soit n et m 2 entiers supérieurs ou égaux à 3. Dans une grille rectangulaire composée de $n \times m$ cases, combien y a-t-il de zones ? Sachant qu'une "zone" est n'importe quelle association de cases qui tient dans un carré de taille 3x3. Pour illustrer, voici quelques exemples de zones valides (non exhaustifs) : chaque couleur est une possibilité.

Attention de ne pas compter 2 fois la même zone par translation.

PS : ceci n'est pas un exercice mais une quantité dont j'ai eu besoin. J'aimerais comparer avec les amateurs de dénombrement. Je repasserai poster ma réponse.

Médiat_Suprème

Bonjour
Par translation, ou pour toutes les symétries ? Si j'étais vous je regarderais du côté du lemme de Burnside. 

Heuristique

Bonjour
Ce n'est pas très élégant mais, comme il y a $2^9 = 512$ possibilités, rien n'empêche de toutes les énumérer et les comparer avec un programme. Mais ce genre de technique s'arrêtera vite en augmentant la taille de la grille...

LOU16

Bonjour,

J'ai cru comprendre qu'une "zone" est une partie non vide  de l'ensemble des $mn$ cases susceptible d'être "contenue dans un  carré $3\times 3$".

Je dis qu'une zone est "de format $x \times y$"( $(x,y)\in[\![1;3]\!]^2$) si le rectangle de dimensions minimales qui la contient est un rectangle $x\times y. $

Pour un rectangle $x\times y$, je note $N_{x\times y}$ le nombre de zones de format $x\times y$ qu'il contient. Ainsi:

$N_{1 \times1} =N_{1\times 2} =N_{2\times 1}=1, \quad N_{1\times 3} =N_{3\times 1}=2, \quad N_{2\times 2} =7,\quad N_{2\times 3} =N_{3\times 2} =32,\quad N_{3\times3}  =322.$

Le nombre de rectangles $x\times y$ contenus dans un rectangle $m\times n $ est $ (m+1-x) (n+1-y). \:\:$Le nombre de "zones" est donc:

$$\boxed{\mathcal N_{m\times n}=\displaystyle\sum_{1\leqslant x,y\leqslant 3}(m+1-x)(n+1-y)N_{x\times y}=400mn-752(m+n)+1423.}$$

PetitLutinMalicieux

Bravo Lou16. Tu es toujours au top. J'ai fait le même raisonnement, et obtenu le même résultat.

Si m=n, alors le premier terme ressemble à un carré parfait, et le second terme à un double produit. Pourtant, cela ne coïncide pas. Et dans le même temps, les valeurs sont suffisamment proches pour que les nombres de la formule finale soient petits :

$\mathcal N_{n\times n}= (20n)^2-2*752*n+1423 = (20n-38)^2+16n-21$.

Application numérique : $\mathcal N_{50\times 50}= 926223$, soit un petit million de zones, manipulables par un ordinateur moderne.