Répondre

Michel Coste · 25-02-2022 10:07:32

Bonjour,

Pour le réseau tétraédral 3d on obtient sans trop de peine les nombre de circuits de longueur [tex]n[/tex]. Il suffit, en poursuivant l'idée que j'ai piquée sur OEIS, de calculer le terme constant de

[tex]\left( x+\dfrac1x+y+\dfrac1y + z+\dfrac1z + \dfrac{x}{y}+\dfrac{y}{x} + \dfrac{y}{z} + \dfrac{z}{y} + \dfrac{z}{x} + \dfrac{x}{z}\right)^n[/tex].

En 494 millisecondes, SageMath me calcule :
[1,
0,
12,
48,
540,
4320,
42240,
403200,
4038300,
40958400,
423550512,
4434978240,
46982827584,
502437551616,
5417597053440,
58831951546368,
642874989479580,
7063600894137216,
77991775777488144,
864910651813116480]
Tiens, celle-ci n'est pas dans OEIS.

bridgslam · 25-02-2022 08:19:55

Bonjour Michel

Michel Coste a écrit :

J'ai un peu de mal à voir exactement ce qui se passe sur ton dessin GeoGebra, mais poui c'est ça.

Je ne suis pas du tout un virtuose des logiciels de graphisme, hélas.
J'ai voulu représenter la projection sur un plan adéquat pour un bout de trajet ( pas un circuit ici) par des arêtes de cubes, de façon à n'avoir qu'un réseau de triangles équilatéraux dans ce plan.
La normale au plan ( bleu clair ) a pour direction un axe passant par deux coins d'un même cube complètement opposés.
C'est la seule idée que j'aie eue.

Pour la suite, si on considère un réseau 3D tétraédral j'espère juste qu'il suffira de projeter des hypercubes en 4D pour s'en sortir...
sans doute plus difficile à visualiser.

Bonne journée
Alain

Michel Coste · 24-02-2022 20:31:42

Une idée vachement plus efficace, que j'ai piochée sur OEIS, pour calculer le nombre de circuits de longueur [tex]n[/tex] sur le réseau hexagonal : calculer le terme constant de [tex]\left( x+\dfrac1x+y+\dfrac1y + \dfrac{x}{y}+\dfrac{y}{x}\right)^n[/tex].

Michel Coste · 24-02-2022 16:27:01

J'ai un peu de mal à voir exactement ce qui se passe sur ton dessin GeoGebra, mais poui c'est ça.
J'ai fait un petit programme pour calculer le nombre de circuits de longueur donnée dans le réseau hexagonal plan (ou triangulaire plan). Ça me donne
[1,
0,
6,
12,
90,
360,
2040,
10080,
54810,
290640,
1588356,
8676360,
47977776,
266378112,
1488801600,
8355739392,
47104393050,
266482019232,
1512589408044,
8610448069080]
ce qui m'a permis de retrouver cette suite dans OEIS : A002898

bridgslam · 24-02-2022 10:21:56

Bonjour,

En prenant un plan normal à la direction de la droite joignant deux coins opposés des cubes je pense?

Merci, je n'avais pas pensé à cette possibilité.

Par exemple: https://www.geogebra.org/3d/drg8addy

La projection sur le plan bleu normal à la droite noire passant par deux coins de cube opposés d'un bout de trajet cubique ( non fermé ici) donne un trajet triangulaire plan.

Alain

Michel Coste · 24-02-2022 10:04:34

Bonjour,

Pour le réseau cubique dans l'espace, le nombre de circuits de longueur 2n se calcule assez facilement et on trouve la suite 1, 6, 90, 1860, 44730, 1172556, 32496156, 936369720 ... qui figure dans OEIS : A002896. Il semble bien par contre qu'il n'y a pas de jolie formule close du genre [tex]\binom{2n}{n}^2[/tex].

Pour le réseau triangulaire plan, on peut le voir comme projection du réseau cubique dans l'espace pour faire le comptage.

bridgslam · 24-02-2022 09:59:31

Bonjour,

Avec ce procédé, avec un calcul rapide ( que j'espère juste) , pour un maillage plan équi-triangulaire on a au moins $3\binom{2n}{n}\{ \binom{2n}{n} -1\}$ trajets linéaires ou à deux directions, auxquels il faudrait encore rajouter les trajets utilisant toutes les 3 directions ( et pas seulement 2).

Je ne sais pas si des techniques plus élaborées ( théorèmes à l'appui ) existent dans ce genre de questions ni si la théorie des graphes peut venir à la rescousse... en tous cas ce ne doit pas être de la tarte.

A.

bridgslam · 24-02-2022 08:50:35

Et encore, c'est pas sûr il y a des trajets communs à différents types de trajets ( par exemple ceux en ligne avec aller et retour) , qu'on va alors compter... deux fois,
... effectivement pas simple du tout.

Une démarche possible (?) pour minorer le nombre de chemins sur mailles triangulaires (de côtés égaux):

- compter à part les trajets en lignes ( dans une des 3 directions possibles)
- pour les autres , par catégories de deux directions réellement utilisées , on se ramène donc à des trajets carrés , déjà évalués mais auxquels il faut retrancher les "en-ligne"...

Compliqué.

A.

bridgslam · 24-02-2022 08:39:02

Bonjour,

Oui c'est faisable aussi avec une maille cubique. C'est la même idée, il faut faire jouer cette fois $\alpha$, $\beta$, $\gamma$
(pour rajouter la profondeur) avec leur somme égale à n (pour un trajet de longueur 2n).
Sauf erreur on obtient une expression en somme indicée analogue au grillage plan.
Je n'ai pas regardé plus, mais l'expression doit sans doute se simplifier aussi.

Par-contre avec un maillage plan en forme de triangles équilatéraux, c'est effectivement très difficile (puisqu'on peut parfois court-circuiter en diagonale, mais pas toujours selon les arêtes successives empruntées...).
En empruntant seulement deux directions parmi trois dans tous les trajets, je pense ( en faisant pivoter légèrement le système de coordonnées pour être // aux mouvements élémentaires à deux directions) , que le nombre de trajets sera au moins égal à 3 fois celui qu'on a dénombré précédemment.
Je dis ça à la louche.

A.

Michel Coste · 23-02-2022 19:23:05

Oui, tu as raison, j'ai écrit [tex]\mathbb Z^2[/tex] alors que je voulais écrire [tex]\mathbb Z^3[/tex].
Il vaut mieux que je zoome, sinon j'ai du mal à lire les exposants.

Bernard-maths · 23-02-2022 19:17:33

J'ai hésité, mais comme j'ai vu Z², j'ai poussé mes précisions ... no problem !

Michel Coste · 23-02-2022 18:51:27

Moi je voyais ça dans l'espace 3D, en ne considérant que les points de coordonnées entières

Autrement dit dans [tex]\mathbb Z^3[/tex], comme je l'ai écrit. ;)

Bernard-maths · 23-02-2022 18:19:19

Ok !

Moi je voyais ça dans l'espace 3D, en ne considérant que les points de coordonnées entières pour un cube de côté entier n par ex, ou n/2, n/3 ... selon les contraintes sur la longueur du parcours ...

Soit dans le volume, soit en restant en surface du cube ... Il faut fixer le début O !

Mais ce ne sont que des variantes possibles au problème de départ !

B-m

Michel Coste · 23-02-2022 18:10:43

Quand je parle d'un réseau cubique, ça veut dire qu'on se déplace dans [tex]\mathbb Z^2[/tex] et on change une et une seule coordonnée de [tex]\pm1[/tex] à chaque pas.
Comme le quadrillage plan, mais en 3d.
Je ne comprends pas ça :

Alors on pourrait aussi rester en surface du cube ... dans ce cas ne pourrait-on pas projeter sur les faces un chemin interne ?

Bernard-maths · 23-02-2022 17:34:22

Bonjour à tous deux !

Je vois que vous vous amusez beaucoup, et moi je regarde de loin ...

Michel, quand tu parle de réseau cubique ... s'agit-il bien d'un cube 3D ?

Alors on pourrait aussi rester en surface du cube ... dans ce cas ne pourrait-on pas projeter sur les faces un chemin interne ?

Juste pour un peu de sel ...

B-m

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Pied de page des forums