Noeud celtique
Bonjour
Tout le monde a déjà vu un nœud celtique comme celui ci-joint.
Plus précisément, un nœud celtique rectangulaire (n, m) peut se construire de la façon suivante.
On trace les frontières d'un rectangle de coté 2n et 2m (dans un repère orthonormée, les cotés reposent sur les droites x = 0, x = 2n, y = 0 et t = 2m
Ensuite on trace des barrières (à l'intérieur des frontières), c'est-à-dire des segments horizontaux, ou verticaux, commençant en (x0, y0) et finissant en (x1, y1) tels que x0+y0 et x1+y1 soient pairs, et telles que 2 barrières ne peuvent se croiser qu'en un point (x, y) tel que x + y soit pair.
Je note $K_{n, m}$ le nombre de nœuds celtiques dans un rectangle (n, m) (2 nœuds identiques par symétrie, ou rotation compte pour 1)
Certains cas sont évidents : $K_{n, m} = K_{m, n}$, $K_{0, 0} = 1$, $K_{1, 1}=1$
J'ai pu calculer $K_{1, m}$, mais pas $K_{2, 2}$, si quelqu'un a des idées ...
Tout le monde a déjà vu un nœud celtique comme celui ci-joint.
Plus précisément, un nœud celtique rectangulaire (n, m) peut se construire de la façon suivante.
On trace les frontières d'un rectangle de coté 2n et 2m (dans un repère orthonormée, les cotés reposent sur les droites x = 0, x = 2n, y = 0 et t = 2m
Ensuite on trace des barrières (à l'intérieur des frontières), c'est-à-dire des segments horizontaux, ou verticaux, commençant en (x0, y0) et finissant en (x1, y1) tels que x0+y0 et x1+y1 soient pairs, et telles que 2 barrières ne peuvent se croiser qu'en un point (x, y) tel que x + y soit pair.
Je note $K_{n, m}$ le nombre de nœuds celtiques dans un rectangle (n, m) (2 nœuds identiques par symétrie, ou rotation compte pour 1)
Certains cas sont évidents : $K_{n, m} = K_{m, n}$, $K_{0, 0} = 1$, $K_{1, 1}=1$
J'ai pu calculer $K_{1, m}$, mais pas $K_{2, 2}$, si quelqu'un a des idées ...
504, c'est trop !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Seul un algorithme peut te donner la réponse. Le nombre de combinaison est très grand…
Et c'est cet algorithme que je cherche, et pas de "force brute".
Cherche sur le net. Des algorithmes sont disponibles. Ils traces les noeuds et donnent leurs caractéristiques.
Grâce à l'aide d'un participant sur stackoverflow, j'ai pu résoudre le problème.