Polygones à p côtés

OShine · December 2020

Bonsoir,

On se donne $n$ points du plan, trois à trois non alignés.

Combien existe-t-il de polygones à $p$ côtés dont les sommets soient $p$ de ces points ?

Pour $n=3$ je trouve $1$ polygone.

Pour $n=4$ je trouve $5$ polygones.

Il faut pas rajouter l'hypothèse polygone convexe ? Car ça m'a l'air bizarre. Je ne vois pas comment compter dans le cas général. 113894

lourrran · December 2020

Dans la question, il y a 2 variables $n$ et $p$.
Si dans la réponse, $p$ n'intervient pas, c'est bizarre.

Math Coss · December 2020

C'est quoi un polygone ? (La question est moins naïve qu'il n'y paraît.)

marsup · December 2020

$\binom{n}{p}$ ?

Moi non plus je ne suis pas très sûr de ce qu'il faut comprendre par "polygone".

lourrran · December 2020

La bonne réponse à cette question 'qu'est ce qu'un polygone', c'est de faire l'exercice 2 fois, avec les 2 différentes options :
- si on considère qu'un polygone est 'orienté', le nombre de polygones est de xxx ,
- et si on considère que l'orientation ne doit pas être prise en compte, alors le nombre de polygones est de yyy

Trouver la 2ème réponse quand on a trouvé la 1ère, ce n'est pas trop compliqué.

Mais effectivement, quand on s'attaque à l'exercice, c'est une des questions qu'on doit très vite se poser.
Si on fonce dans l'exercice, sans avoir vu qu'à un moment, cette question-là va se poser, c'est mal parti.

Chaurien · December 2020

...polygone...

marsup · December 2020

Ah oui, "polygone" s'écrit comme "hormone", bien qu'il se prononce comme "cône".

Chaurien · December 2020

On pourrait dire qu'un polygone à $p$ côtés est défini par une suite de $p$ points parmi les $n$, deux telles suites définissant le même polygone si elles se déduisent l'une de l'autre par permutation circulaire ou inverse, pour ainsi dire..

Math Coss · December 2020

Est-ce que $ABCD$ est le même polygone que $ADCB$ ?

Chaurien · December 2020

Avec mon interprétation, $ABCD$ est le même polygone que $ADCB$ car ils ont les mêmes côtés, mais ce n'est pas le même que $ABDC$. À moins de définir des « polygones orientés », ce qui serait possible aussi.

OShine · December 2020

C'est une figure géométrique formée d'une ligne brisée fermée.

Chaurien · December 2020

Il me semble que pour $ p \ge3$ le nombre de polygones « non orientés » à $p$ côtés qu'on peut former avec $p$ points du plan est $X_p=\frac 12 (p-1)!$. Ce sont les cycles hamiltoniens d'un graphe complet.
Si $ n \ge p\ge 3$, le nombre de polygones à $p$ côtés qu'on pourra former avec $n$ points du plan sera donc $(_p^n)X_p$.
Bonne nuit.
Fr. Ch.

OShine · December 2020

C'est un exercice de combinatoire de MPSI dans les exercices d'applications.
Ça ne doit pas être trop compliqué.

À mon avis, il n'y a pas d'orientation dans cet exercice.

Dans ce cas la réponse c'est juste $p$ parmi $n$ comme l'a suggéré Marsup ?

OShine · December 2020

@Chaurien
Merci mais je n'arrive pas à comprendre comment obtenir $X_p$.

Chaurien · December 2020

Soient $p$ points du plan, $ p \ge 3$, numérotés $1,2,...,p$. Une permutation $(a_1,a_2,...a_p)$ de ces numéros définit un polygone de côtés successifs $a_1a_2$, $a_2a_3$, ...$a_{p-1}a_p$, $a_pa_1$. Ce même polygone est défini par les $p$ permutations circulaires $(a_2,a_3,...a_p,a_1)$, ... , $(a_p,a_1,...a_{p-1})$, et les $p$ permutations circulaires inverses de $a_p,a_{p-1},...a_2,a_1$, soit au total $2p $ permutations de $1,2,...,p$. Ainsi on peut répartir les $p!$ permutations de $1,2,...,p$ en $X_p$ classes, chacune d'elles définissant un polygone et comprenant $2p$ permutations. Le nombre de ces classes est donc $X_p= \frac {p!}{2p}=\frac12 (p-1)!$. C'est le principe des bergers, d'où la chanson de Jacques Brel ;-).
Voir OEIS https://oeis.org/A001710.
Bonne journée.
Fr. Ch.

lourrran · December 2020

Pour les non-matheux comme OOShine ou moi :

A partir de $p$ points, on a $p!$ façons de les classer, donc $p!$ polygones.
Mais dans ces $p!$ polygones, il y a plein de doublons.
Quand j'ai un polygone, il est dessiné, il est concret. Ce polygone est constitué des sommets A,B,C,D,E,F dans cet ordre. Mais je peux choisir n'importe quel sommet comme point de départ. Les polygones (A,B, C,D,E,F) et (B,C,D,E,F,A), c'est le même polygone.

Dans le cas de polygones à 6 sommets (hexagones), il faut donc diviser le comptage précédent par 6. Et dans le cas plus général de polygones à p sommets, il faut diviser le résultat précédent par $p$ car il y a $p$ façons de choisir le sommet de départ
On arrive à $(p-1)!$

Idem, pour mon hexagone de tout à l'heure, quand je veux le décrire et que j'ai choisi le 1er sommet, je peux tourner dans un sens ou dans l'autre.
En effet, (A,B,C,D,E,F) ou (A,F,E,D,C,B) , c'est le même polygone.
Il faut donc encore diviser par 2 le résultat ci-dessus.

A partir de p points , le nombre de polygones qu'on peut former est donc $\frac{(p-1)!}{2}$

On vérifie que pour 3 points, cette formule dit qu'on peut former 1 seul triangle, et pour 4 points, on peut former 3 quadrilatères... ça paraît correct.

Reste une dernière étape pour répondre à l'exercice. Quand on a $n$ points, combien de polygones à $p$ côtés peut-on constituer ?

Chaurien · December 2020

Lourran exprime les mêmes idées que moi sous une autre forme, avec le même résultat, ce qui est rassurant.
Pour sa dernière question, pour avoir le nombre de polygones à $p $ côtés qu'on peut constituer avec $n$ points, on choisit d'abord les $p$ sommets parmi les $n$ points, ce qui peut se faire de $(_p^n)$ façons, et pour chacun de ces choix on a $X_p= \frac12(p-1)!$ polygones.
La réponse est donc : $(_p^n)\cdot \frac12(p-1)!$.
J'ai expliqué tout ça hier soir, il y a neuf heures.

OShine · December 2020

@Chaurien
Je n'ai pas compris à la méthode avec les permutations, trop technique pour moi.
Par contre la deuxième partie de votre message j'ai compris avec le $2$ parmi $n$.

@Lourran
Merci c'est très clair. Votre explication est parfaite (:P)

J'avais raisonné un peu différemment au départ avant de poster sur le forum. J'avais fixé le premier point donc il me restait $p-1$ choix pour le deuxième point etc et j'obtenais $(p-1)!$.
Je n'ai pas pensé à diviser par $2$ et encore moins à multiplier par le $\binom{n}{2}$.

Mais c'est clair pour moi maintenant (tu)

lourrran · December 2020

C'est clair pour toi maintenant.
Mais le problème, c'est que tu devrais pouvoir résoudre ce genre d'exercice tout seul. Il n'y a rien de compliqué, si on prend son temps.

A partir de n points dans le plan, je dois en choisir p : nombre de choix possibles : c'est FACILE.
Quand j'ai choisi p points, combien de polygones je peux faire avec ces p points : c'est FACILE.
C'est FACILE, à une condition, c'est d'avancer lentement. Décomposer en questions plus simples. toujours décomposer en petits problèmes plus simples.

OShine · December 2020

Oui c'est vrai, je vais reprendre un exercice du style pour voir si je m'en sort mieux.

Exercice :

Quel est le nombre de diagonales d'un polygone strictement convexe de $n$ côtés ?
En combien de points intérieurs au polygone ces diagonales se coupent-elles ? On pourra considérer que les points d'intersections sont distincts deux à deux.

1) Je propose :
Il y a $\binom{n}{2}=\dfrac{n(n-1)}{2}$ couples de points dans le polygone.
On enlève les $n$ côtés ce qui donne :

$\boxed{N=\dfrac{n(n-1)}{2}-n}$

2) Je n'ai pas réussi.

Chaurien · December 2020

Une méthode de recherche c'est de faire la figure pour $n:=4,5,6,7$, et plus si nécessaire, et de faire une conjecture très simple, et puis de la démontrer.
Une autre méthode pourrait être de regarder comment le nombre $I_n$ d'intersections évolue lorsque l'on rajoute un point, mais ce n'est peut-être pas nécessaire ici.

Bêtise de l'énoncé. Il ne faut pas écrire : « on pourra considérer que les points d'intersections sont distincts deux à deux », ce qui ne veut pas dire grand'chose, mais : « on supposera que que jamais trois diagonales ne concourent », ce qui s'exprime aussi en disant que les $n$ sommets sont en position générale.

A contrario, le même problème pour un polygone régulier, malgré son énoncé des plus élémentaires, est resté ouvert depuis l'Antiquité jusqu'à l'aube du XXIème siècle, et a été résolu par Claude Morin et Dominique Roux, que je salue à cette occasion, et indépendamment par deux mathématiciens des États-Unis.

Bonne soirée.
Fr. Ch.

OShine · December 2020

Ok Chaurien merci. J'ai fait ça.

Pour $n=3$ je trouve $0$.

Pour $n=4$ je trouve $1$.

Pour $n=5$ je trouve $5$

Pour $n=6$, je trouve $15$.

Pour $n=7$ je trouve $35$

En faisant le dessin pour $n=7$ je crois avoir trouvé, chaque point d'intersection est lié à 4 points. Donc c'est le nombre de façon de prendre $4$ points parmi les $n$.
Il y a une sorte de bijection entre 4 sommets du polygone et un point un d'intersection des diagonales.

Donc $N'=\binom{n}{4}=\dfrac{n(n-1)(n-2)(n-3)}{24}$

Mais difficile de conjecturer directement à partir des valeurs de $n$ non ? Puis comment faire une récurrence ? Ca me semble compliqué pour $n$ fixé.

Chaurien · December 2020

Bravo ! Encore un petit effort. Deux diagonales, c'est 4 sommets, non ?

OShine · December 2020

Oui deux diagonales sont forcément liées à $4$ sommets.

OShine · December 2020

@Lourran

Dans le premier exercice, pour $p=3$ les 3 quadrilatères sont ceux là ? Deux croisés et un non croisé ? 113920

Math Coss · December 2020

Pour deviner une formule polynomiale quand on a assez de termes, c'est-à-dire le polynôme $P$ tel que $u_n=P(n)$ à partir des premières valeurs de la suite, on peut calculer les différences successives et recommencer jusqu'à trouver une suite constante. \[\begin{array}{ccccccccccccccccccccccccccccc}
0&&1&&5&&15&&35&&70&&126&&210&&330&&495&&715&&1001\\
&1&&4&&10&&20&&35&&56&&84&&120&&165&&220&&286\\
&&3&&6&&10&&15&&21&&28&&36&&45&&55&&66\\
&&&3&&4&&5&&6&&7&&8&&9&&10&&11\\
&&&&1&&1&&1&&1&&1&&1&&1&&1\end{array}\]Tu peux te demander pourquoi on est sûr que ça finit par arriver – que la suite devienne constante – et en combien de coups, puis comment remonter et retrouver ainsi $P$.

OShine · December 2020

Maths Coss je n'ai pas tout compris mais à partir de n=8 ça devient très compliqué de tracer tous les points d'intersection des diagonales.

OShine · December 2020

Je n'ai pas compris à quoi correspond votre schéma avec les nombres.

lourrran · December 2020

Quand on a une fonction polynomiale, on met sur la première ligne f(1), f(2), f(3), f(4) , etc etc
Puis sur la 2ème ligne f(2)-f(1), f(3)-f(2) etc etc
Puis sur la 3ème ligne, pareil, chaque terme est la différence des 2 termes au-dessus
Et ainsi de suite.

A un moment, on a l'assurance d'obtenir une ligne où tous les nombres sont les mêmes.

Sur la première ligne on a un polynôme P de degré n.
Sur la 2ème ligne, à partir de P(i) et P(i+1) , on a la dérivée de P : P' (i+0.5) (pas totalement sûr, pas vérifié, mais ça doit être ça). Donc on a un polynôme de degré n-1
Puis à partir de P'(i+0.5) et P'(i+1.5), on obtient P''(i+1)
Et ainsi de suite.
Et donc forcément, à un moment on a une fonction constante.

Ceci-dit, même si on se doute que le nombre de points d'intersection des diagonales, c'est une fonction polynomiale P(n), ça reste à démontrer.

OShine · December 2020

Je n'ai jamais vu cette technique.

Du coup je crois que je vais laisser tomber cette méthode je n'ai jamais vu ça. Ca m'a l'air compliqué.

lourrran · December 2020

Comme toi, je n'avais jamais vu cette technique dans les cours. Ce n'est pas quelque chose qu'on apprend à l'école.
N'empêche qu'un jour, je suis tombé dessus, en jouant avec des nombres. Et je trouve que c'est une propriété simple, très intéressante sur les polynômes. Ca pourrait certainement être le thème d'un beau problème.

Ca ressemble un peu au triangle de Pascal, c'est une propriété bien sympa.

Remplis la ligne du bas avec plusieurs fois le même nombre.
Remplis la ligne au dessus : tu choisis un nombre quelconque pour la 1ère position, et les autres s'en déduisent. Un peuExactement comme quand on recherche une primitive : toutes les primitives de f sont égales, à une constante près. On retrouve ça ici ... moi je trouve ça beau.

gerard0 · December 2020

Lourran,

ce ne sont pas des dérivées, simplement P(X+1)-P(X) se simplifie par le degré maximal de P, donc on perd au moins un degré.

Cordialement.

Chaurien · December 2020

On appelle ça différences finies, et ça s'étudiait en parallèle avec les dérivées, au XIXème siècle. Bravo Lourran, ça c'est le vrai esprit mathématique.

lourrran · December 2020

Merci Chaurien.

Sur le parallèle avec les dérivées, je n'avais pas de doutes. Il suffit de remplacer les nombres 1,2,3 ... par $ \epsilon, 2*\epsilon, 3*\epsilon ... $, c'est à dire faire un changement de variable adéquat, et on arrive à la définition de la dérivée (parce qu'on parle de fonctions qui ont toutes les bonnes propriétés ...)
Par contre, je disais qu'on tombait 'probablement' sur le dérivée au point 'milieu' , et ce n'est pas le cas. On tombe sur la dérivée en un point intermédiaire entre les 2 points étudiés, pas au point milieu.

Et, je le jure, je ne suis pas né au XIXème siècle.

PS : je viens de lire en diagonale l'article sur les différences finies sur Wikipedia, et ça me rappelle quelques cours de calculs numériques (cul-nu pour reprendre l'abréviation qu'on employait).
Finalement, peut-être que c'est dans ces cours de cul-nu que j'ai vu cette propriété pour la première fois.

Mais on s'éloigne beaucoup de cet exercice osté par OOShine, où il fallait compter les points d'intersection d'un polygône convexe !

gilles benson · December 2020

Bonjour, si $\Delta _n (u) := u_{n+1} - u_n$ pour une suite $u = (u_n)_{n \in \mathbb{N}}$, on a quelques propriétés simples:

1) en utilisant la formule de Pascal: $\binom{n}{k} = \binom{n-1}{k-1} +\binom{n-1}{k}$, on obtient si $u_n = \binom{n}{k}$,
$\Delta _n (u) = \binom{n}{k-1}$.

2) la formule de Gregory-Newton: on part d'une suite $x_i = x_0 + ih$ avec débutant en $x_0$ avec pour pas $h > 0$; pour une fonction $f$ évaluée en $x_i$, on note $f_i := f(x_i)$. Donc $\Delta f_i = f_{i+1} - f_i$.

Si $t = \dfrac{x-x_0}{h}$, on a, en notant $\Delta ^n $ l'itéré de rang $n$ de $\Delta$:
$$
f(x) \; = \; f(x_0) + t \Delta f_0 + \dfrac{t(t-1)}{2!}\Delta f_0 ^2 + \dfrac{t(t-1)(t-2)}{3!} \Delta f_0 ^3 + \dots

$$ Si on arrête la somme à l'ordre $n$ (troncature), on obtient le polynôme de Lagrange qui interpole $f$ sur les valeurs considérées et si $f$ est un polynôme de degré $n$, il y a identité.