Savoir & Culture

je crois avoir trouvé aussi
Déjà n pour le nombre de choix pour le premier point.
Ensuite, si il ne reste qu'un point, on le relie.
Sinon, s'il en reste plusieurs, alors en fait on s'aperçoit qu'on a toujours le choix qu'entre 2 points : les deux points adjacents à l'ensemble des points reliés jusqu'à présent.

En effet, si on suppose que les points reliés jusqu'à présent sont adjacents (ce qui est le cas après le choix du premier point...) alors l'ensemble des points non reliés forme un polygone convexe. Si on relie le chemin actuel à un point non adjecent, on coupe ce polygone en deux, et on appelle S le segment qui coupe le polygone. Il va tôt ou tard falloir relier ces deux parties pour compléter le chemin, on va donc intersecter S (pour le justifier clairement il doit y avoir un argument de convexité, que je ne vois pas forcément...), donc absurde.

Ainsi, on a à chaque fois 2 choix de points à l'étape k, où k<=n-2.

À l'étape n-1, il ne reste qu'un point.

Ainsi, au total, ça fait n*2^(n-2) chemins possibles, mais des chemins orientés car dans mon raisonnement, le sens départ->arrivée est important. Il suffit de diviser par 2 en considérant qu'un chemin et son chemin inverse sont en fait les mêmes.

Ça fait n*2^(n-3)

J'ai pas été super rigoureux, notamment à l'étape de l'hérédité de ma recurrence, mais bon ça fait des années que j'ai pas fait des maths comme ça si quelqu'un a une explication plus rigoureuse je suis preneur