Combinatoire : denombrement

[invite98d93111]

Bonjour,

Un chateau est construit sous la forme d`une grille nxn.
Il est compose de nxn chambres.
Chaque chambre possede 4 murs.
Certains murs donnent sur l`exterieur (le jardin) d`autres non. On peut ouvrir une porte donnant sur le jardin.
On exige exactement 2 portes par chambre. Un mur quelconque possede au plus une porte. On ne peut pas construire 2 portes sur le meme mur.

Combien de configurations sont possibles? A exprimer en fonction de la valeur de n.
Pour n=1 6 configurations sont possibles.
Qu`en est-il pour n>=2?
Peut-on trouver une formule donnant exatement le nombre de configurations possibles?
Partant de ces contraintes on souhaite connaitre pour chaque nxn le nombre de configurations avec un nombre minimal de portes.
Par exemple pour n=2 on a une seule configuration possible utilisant 4 portes. n=1 on a 6 configurations possibles et 2 portes comme minimum.

Merci
-----

[invite98d93111]

Denombrement pas facile on dirait.
Des qu`il y aura du neuf je repasserai.

[Médiat]

Bonjour,

Avez-vous déjà exploré quelques pistes ?

Avez-vous calculé le nombre de possibilités pour n=2 ? Comment ?

[invite98d93111]

Salut et merci.
Pour n=2 donc une grille 2x2 j`ai trouve 82 possibilites en les comptant.

[A voir en vidéo sur Futura]

[Médiat]

Pour n=3, je pense à 4374 possibilités :



[EDIT] Désolé : c'est faux.

[invite98d93111]

Pour n=3, je pense à 4374 possibilités :

Je trouve 2604 pour 3x3

Je ne suis pas programmeur mais j`ai un algorithme pour solutionner le probleme.
Le calcul deviendrait complexe au dela d`une certaine valeur de n
Complexite = 2^(2*n*(n+1))

Avec n=10 cela donnerait 2^220

[Médiat]

Peut-être 2176592549084872196370724 pour n=10

[invite98d93111]

Peut-être 2176592549084872196370724 pour n=10

Je ne sais pas. Si je pouvais avoir les configurations de n=2 a n=6 je pourrais chercher dans l`OEIS (Sloane) pour trouver une sequence similaire.
L`algorithme est simple mais l`optimisation reste un probleme de programmeur.
Une suite de variables 0 et 1 avec une verification de nxn sommes.
Pour n la longueur de la suite est = 2*n*(n+1)

[Médiat]

peut-être : https://oeis.org/A068253

[invite98d93111]

peut-être : https://oeis.org/A068253

J`ai deja trouve cette sequence mais comme je ne suis pas sur ne connaissant pas n=4, n=5,n=6, j`ecarte pour le moment.

[invite98d93111]

En fait, je cherche une formule generale ou plusieurs formules dependant de la parite de n (par exemple).
Pour l`instant personne n`arrive a trouver une formulation generale.
Je pense qu`elle existe et je finirai par la trouver

[invite98d93111]

Je pense avoir trouve la formule generale.

[Médiat]

Postez-là, je suis impatient

[PhilTheGap]

Bonjour Aracoco

Comme l'écrit Mediat, ce serait assez cool que vous donniez la formule - si vous l'avez trouvée - puisque vous avez sollicité notre aide...

[invite9dc7b526]

Sans le jardin le problème est beaucoup plus facile. Je pense qu'on peut montrer que dans ce cas il n'y a pas de solution pour n impair. Mais bon, il y a le jardin...