Aquitaine-Poitou-Charente-Limousin
En juillet dernier, Antoine Planchot, sur Twitter, proposait aux matheux le défi suivant :
Combien y a-t-il de cartes possibles pour la #RéformeTerritoriale ? On ne souciera pas de la cohérence économique ou culturelle. /3
— Antoine Planchot (@APlanchot) 16 Juillet 2014
Quand on me pose, directement ou indirectement, ce genre de question, je réagis toujours plus ou moins de la même façon
- je lis l'énoncé en me disant que cela n'a pas l'air si difficile, et je retourne vaquer à mes occupation,
- je libère 10 minutes de mon planning pour y réfléchir un peu plus précisément,
- deux heures plus tard, j'enrage de ne pas encore avoir trouvé,
- trois jours plus tard, je résous enfin le problème, maugréant qu'en fait, c'était trivial !
Pour ce problème de #RéformeTerritoriale, je suis toujours bloqué dans la phase 3, mais je suis persuadé qu'un lecteur bien plus malin que moi trouvera l'idée qui m'a échappé. Je ne suis donc pour l'instant pas encore en mesure d'aider François Hollande et son gouvernement, mais on va quand même essayer pour aujourd'hui de trouver une borne supérieure satisfaisante du nombre de cartes à envisager !
Si je compte bien, la France compte 26 régions (métropolitaine ou d'outre-mer), ainsi qu'une collectivité métropolitaine (la Corse) et 5 d'outre-mer.
Je ne crois pas qu'il ait été à un moment donné question de fusionner la Martinique avec la Franche-Compté, donc on ne prendra pas en compte les régions et collectivités d'outre-mer dans le problème. Puisque l'idée que la Corse puisse fusionner avec la région PACA a été étudiée, on prendra en compte dans le calcul 22 régions françaises.
La France de la #RéformeTerritoriale : 22 régions, 44 frontières, 23 points triples
Les nombres de Bell
Première idée naïve : combien existe-t-il de façon de partionner un tel ensemble de 22 éléments ? De toutes ces partitions, on aura par exemple l'actuel projet de réforme territoriale :
Une carte de France à 13 régions, dont la future Aquitaine-Poitou-Charente-Limousin, qu'il faudra renommer au plus vite.
Ou bien, la partition correspondant aux différents indicatifs téléphoniques locaux :
Une carte de France à 5 régions
Mais il y aura également cette partition des régions Françaises en 3, en fonction du nombre de voyelles et consonnes dans leur nom. Cette dernière ne répond pas au problème initial, puisque les régions formées ne sont pas d'un seul tenant ("connexe"). Pas grave, on cherche pour l'instant une estimation haute du nombre de carte que l'on pourrait faire.
Un redécoupage à exclure
(En bleu, les régions comptant plus de consonnes que de voyelles, en rouge les régions comptant plus de voyelles que de consonnes, et en blanc les régions égalitaires)
Le nombre de façons de partionner un ensemble à n éléments porte un nom, ce sont les nombres de Bell (du nom de Eric Temple Bell, mathématicien célèbre autant pour ses travaux en combinatoire que pour ses livres d'histoire des mathématiques ou de science-fiction). Le n-ième nombre de Bell, noté Bn, représente donc le nombre de partitions différentes d'un ensemble à n éléments.
B0 = 1 : il n'y a qu'une seule (non) façon de découper un ensemble vide.
B1 = 1 : il n'y a qu'une seule façon de découper un ensemble à 1 élément.
B2 = 2 : dans un ensemble à 2 éléments, on peut soit regrouper les deux éléments (première partition), soit ne pas les regrouper (seconde partition).
B3 = 5 : 1 partition en une seule région, 3 partitions en deux régions et 1 partition en trois régions.
5 façons de redécouper le grand Ouest
B4 = 15. Pour trouver cette valeur, procédons méthodiquement, en rajoutant la haute-Normandie dans le grand Ouest. Après un redécoupage, 4 cas différents peuvent se produire, suivant le nombre de régions pouvant être annexées à la Haute-Normandie.
- zéroième cas : toutes les régions sont liées à la HN → 1 découpage
- unième cas : une région (parmi les 3 du grand Ouest) n'est pas annexée à la HN → 3 découpages
- deuxième cas : deux régions ne sont pas fusionnées à la HN, soit 3 paires possibles. Chacune de ces paires admet 2 découpages. Au total, on a donc 3 × 2 = 6 découpages
- troisième cas : aucune région n'est accolée à la HN. On ne compte donc que les découpages à 3 régions, soit B3 → 5 découpages.
On a bien B4 = 1 + 3 + 6 + 5 = 15.
On peut déterminer les valeurs plus grande de Bn en suivant la même trame, en fonction du nombre de région k qui ne seront pas annexées à une n+1-ième région. Parmi les n premières régions, il y a 
façons de choisir ces k régions. Ces k régions admettant Bk découpages, on a donc, pour chaque k, ×Bk découpages.
Les valeurs suivantes de Bn se calculent par récurrence
Au final, les valeurs plus grandes des Bn sont donc données par la formule de récurrence :
Ainsi, B5 = 1×B0 + 4×B1 + 6×B2 +4×B3 + 1×B4 = 52
Cette formule nous permet alors de savoir que, pour 22 régions, on peut compter
B22 = 4 506 715 738 447 323 (=4,5×1015) (=4,5 billiards de) partitions !
Les nombres de Bell ont des tas de propriétés fascinantes (par exemple, le n-ième nombre de Bell est la valeur en 0 de la n-ième dérivée de la fonction f(x) = exp(exp(x)-1)), mais il est inutile d'en parler davantage ici, puisque n'est de toutes évidence pas une bonne modélisation ; le nombre de partitions est bien supérieur au nombre de redécoupages.
Passage au dual
Plutôt que de chercher à fusionner les régions, cherchons donc plutôt à retirer les frontières entre régions. Ainsi, il n'y a plus aucun risque de fabriquer des régions non connexes.
La France (métropolitaine) compte 43 frontières, auquel on peut ajouter une 44e frontière P.A.C.A./Corse. Un redécoupage territorial consiste alors à choisir, pour chacune des 44 frontières, si il faut la garder ou non.
Avec cette approche, on peut donc donner une nouvelle estimation (haute) du nombre de partitions. Il y a donc (au plus) 244 = 17 592 186 044 416 (=1,8 ×1013) (=18 billions de) redécoupages !
Le problème de cette approche, c'est que plusieurs choix différents de frontières à retirer donnent un même redécoupage.
Autour du tripoint Haute-Normandie/Picardie/Île-de-Frane, 4 choix différents des frontières à retirer aboutissent à la fusion des mêmes régions
Ce problème apparaît pour chacun des tripoints (point où trois frontières se rejoignent), lorsque sur les trois frontières, une seule est gardée (la région formée est alors mal délimitée). Et des tripoints régionaux, il y en a 23 en France (sur les 44 frontières, 42 sont ratachées à au moins un tripoint).
Autour d'un tripoint, 3 frontières se rejoignent, ce qui devrait donner 23=8 redécoupages. Mais sur ces 8 redécoupages, 5 sont vraiment différents.
Pour dénombrer les découpages, on va partir d'un premier tripoint (par exemple, le tripoint Bretagne/Pays-de-la-Loire/Basse-Normandie), qui donne naissance à 5 découpages. On choisit ensuite un deuxième tripoint tel qu'il existe une frontière la reliant au premier tripoint (par exemple, le tripoint Pays-de-la-Loire/Basse-Normandie/Centre). On a alors deux nouvelles frontières que l'on peut garder ou non, ce qui multiplie par 2²=4 le nombre de découpages possibles. En regardant d'un peu plus près, on peut remarquer que multiplier par 3 à chaque nouveau tripoint suffit :
-
Si la frontière liant les deux tripoints est gardée, alors il faut qu'au moins une des deux nouvelles frontières soit gardée. On exclut donc un des 4 découpages, celui où les deux nouvelles frontières ne sont pas gardées.
-
Si la frontière liant les deux tripoints n'est pas gardée, il n'y a que deux possibilités pour créer des régions bien délimitées : soit on garde les deux nouvelles frontières, soit on en garde aucune.
Dans certains cas, on multiplie par 3, dans d'autres, on multiplie par 2. Pour avoir une estimation haute, on multipliera toujours par 3.
A chacun des 22 tripoints suivant, on mutlipliera donc par 3 le nombre de découpages. Le résultat sera à multiplier par 2², pour prendre en compte les frontières sans tripoints (PACA/Corse et Nords-Pas-de-Calais/Picardie). On a donc au total :
5 × 322 × 4 = 627 621 192 180 (=6,3 × 1011) (=627 milliards de) découpages
Encore une fois, cette estimation est trop haute, pour plusieurs raisons. La première, c'est qu'on a supposé que chaque tripoint apporte deux nouvelles frontières, ce qui n'est pas toujours le cas. Suivant la façon dont on choisit le tripoint suivant, on peut avoir qu'une seule nouvelle frontière, voire aucune. Si seule une nouvelle frontière se présente, on ne multipliera le nombre de découpage que par 2 ; si un tripoint n'apporte pas de nouvelle frontière, on multipliera par 1.
La deuxième, c'est que la multiplication par 3 n'est pas optimale (on multiplie par 3 si la frontière est gardée (62% des découpages), et par 2 sinon. Un meilleur coefficient multiplicateur serait de 2,61). Les multiplicateurs 2 et 1 du paragraphe précédent ne sont eux non plus pas optimaux.
En prenant ceci en compte, cela donne * (environ) 2 000 000 000 (=2 milliards de) découpages. Cette dernière estimation a elle aussi été faite à la hache, d'autant qu'il y a encore d'autres points à prendre en compte pour parfaire le calcul. En effet, il est possible que les régions formées ne sont pas simplement connexes (si une région est enclavée à l'intérieur d'un autre), ce qui diminue encore une fois le nombre de redécoupages possibles.
En fait, la seule façon de connaître le nombre exact de redécoupages possibles serait d'écrire un programme informatique qui les énumère tous... Mais en attendant, j'estime le nombre de découpages à un milliard, et c'est mon dernier mot.
Pour les besoins des illustrations de l'article, j'ai fabriqué un petit script pour fabriquer de *jolies* cartes pour tester des réformes territoriales, disponibles sur eljjdt. En fouillant le script, vous y trouverez les données utiles pour faire un programme compteur.