Farey et le cercle, segments et cordes

Si « figures géométriques » signifie « régions », autrement dit « composantes connexes », c'est un résultat classique et amusant. Les premières valeurs sont les suivantes :

• pour $0$ droite, $1$ région ;
• pour $1$ droite, $2$ régions ;
• pour $2$ droites, $4$ régions ;
• pour $3$ droites, $8$ régions ;
• pour $4$ droites, $16$ régions ;
• pour $5$ droites... $31$ régions !

Voici une référence : http://images.math.cnrs.fr/Demarrage-trompeur.html.

Le dénombrement de ces régions offre un exemple remarquable de tentation de fausse conjecture. J'ai traité cette question il y a longtemps alors plutôt que de retaper ma solution je préfère la joindre.
Il manque le dessin, mais je ne puis le transmettre pour l’instant, et chacun peut le faire selon les indications.
L'idée est de calculer l'augmentation du nombre de régions quand on ajoute un point. C'est une idée qui s'applique à plusieurs problèmes de Combinatoire.
Mille excuses pour la vieille notation des combinaisons, c'est dû à l'ancienneté de ce texte.
Bonne soirée.

Bonsoir:
sur un sujet connexe le cercle au lieu du plan

Bon alors, je donne ma version puisqu'elle ne semble pas avoir été signalée :
Ce résultat est une conséquence directe de la formule d'Euler sur les graphes planaires. La démonstration qui suit montre la nature "topologique'' du résultat et comment on peut le généraliser en choisissant les points ailleurs que sur un cercle ou que dans le plan, du moment que l'on utilise la formule d'Euler adaptée à la situation considérée.

Rappelons que la relation d'Euler établit que, pour tout graphe planaire, on a $S+F-A=1$,

où $S,F,A$ désigne respectivement le nombre de sommets, de faces (face infinie non comptée) et d'arêtes du graphe.

En effet, la configuration obtenue en traçant toutes les cordes et la circonférence du cercle est clairement la représentation d'un graphe planaire dont les sommets sont les $n$ points de départ ainsi que les points d'intersection des cordes, et les arêtes sont tous les "segments élémentaires'' (c.à.d. non subdivisés par d'autres cordes. En particulier, les arcs de cercle qui joignent deux points consécutifs) qui les relient. L'objectif est donc de calculer $F$.

Dans ce graphe, chacun des $n$ points de départ est de degré $n+1$ (il est l'extrémité de $n-1$ cordes et de deux arcs de cercle), alors que chaque point d'intersection de cordes est de degré $4$ (puisqu'il n'y a pas trois cordes concourantes). Il est bien connu que le nombre d'arêtes est la moitié de la somme des degrés, donc $A=\dfrac{n(n+1)}{2}+2I$, où $I$ est le nombre de points d'intersection de cordes.

Clairement, on a aussi $S=n+I$, et il reste donc à évaluer $I$.

Or, tout point d'intersection de deux cordes détermine $4$ des $n$ points (les extrémités des deux cordes) et, réciproquement tout choix de $4$ des $n$ points sur le cercle détermine un et un seul point
d'intersection (l'intersection des diagonales du quadrilatère convexe dont les $4$ points choisis sont les sommets). Ainsi, il y a autant de points d'intersection de cordes que de choix de $4$ points parmi les $n$ initiaux, soit donc $I=\binom{n}{4}.$

Il vient alors $F=1+A-S=1+\binom{n}{2}+\binom{n}{4}= \dfrac{n^{4}-6n^{3}+23n^{2}-18n+24}{24}$.


On peut noter que la démonstration ci-dessus permet d'obtenir un résultat un peu plus général que celui demandé, dans le cas où on ne tracerait pas toutes les cordes, mais seulement $C$ d'entre elles et qu'elles détermineraient $I^{\prime }$ points d'intersection (elles ne sont pas obligés de se croiser). Dans ces conditions, on aurait $R_{n}^{\prime }=1+C+I^{\prime }$ et l'exercice n'est alors que le cas particulier $C=\binom{n}{2}$.

Pierre.

Ah non, mais il l'air bien.
L'approche ci-dessus, c'est la solution que j'avais écrite pour Quadrature (n°78, p.35-36, Oct.-Déc 2010).

Pierre.

Une réflexion me vient à l'esprit:
dans un espace de dimension $n$
le nombre de région sera $n+2$polynomiale par dénombrement de $n$-simplexes
en admettant que ce soit polynomial en dimension supérieure.

Mon cher Math Coss
Tu viens de faire connaissance avec Callipiger qui n'est pas plus mathématicien que tu n'es un joueur de bandonéon!
Amiclement
[small]p[/small]appus

Un argument géométrique comme quoi la croissance du nombre de régions ne peut pas être exponentielle ?