Réponse sur deux plans différents :
- comme vous l'avez suggéré : toute la question est de savoir ce que l'on compte ; c.-à-d. qu'est-ce qu'un « itinéraire » ? Est-ce que A-B-C-D est pareil que D-C-B-A ?
Et l'on pourrait même, du coup, pousser plus loin : est-ce pareil que C-B-A-D ou B-A-D-C, etc. (même « cycle ») ?
Dans cet exercice nous concidérons, de façon similaire au problème précédent (comme suggéré), que tous ces itinéraires sont différents (ce n'est pas le même itinéraire pour venir de chez vous à l'EPFL que pour rentrer).
La notion sous-jacente est la notion de graphe ORIENTÉ (ou non) : on considère ici que les chemins ont un sens (graphe orienté).
Dans ce cas, le nombre d'itinéraires est bien N! - A un autre niveau : est-ce que vraiment ce coefficient une-demi change quelque chose sur le FOND ? Est-ce que cela change les conclusions vus les ordres de grandeurs impliqués ?
Justement non : est c'est pour cela que l'on utilise la notation O(.) (notation de Landau) que je vais vous présenter aujourd'hui (il n'est donc, évidemment, pas question que vous trouviez cela tout seul la semaine passée ; je profite juste de l'occasion pour illustrer concrètement pourquoi on utilise cette notation).