Le plan suivant est celui d’une ligne de métro. Le tarif est uniforme quelle que soit la distance parcourue, à condition de ne parcourir aucune section de la ligne deux fois au cours du même trajet. Un certain passager, pas très pressé, va chaque jour de A à F.
Il peut emprunter la voie directe la plus courte, ABCDEF, en ligne droite ; mais il peut aussi opter pour un trajet plus long, comme ABDCBCEDEF, sans emprunter deux fois une même section de la ligne.
Combien d’itinéraires différents peut-il prendre ?