Polygones à p côtés
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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si dans la réponse, $p$ n'intervient pas, c'est bizarre.
Moi non plus je ne suis pas très sûr de ce qu'il faut comprendre par "polygone".
- 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.
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.
Ç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 ?
Merci mais je n'arrive pas à comprendre comment obtenir $X_p$.
Voir OEIS https://oeis.org/A001710.
Bonne journée.
Fr. Ch.
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 ?
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.
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)
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.
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.
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.
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é.
Dans le premier exercice, pour $p=3$ les 3 quadrilatères sont ceux là ? Deux croisés et un non croisé ?
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$.
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.
Du coup je crois que je vais laisser tomber cette méthode je n'ai jamais vu ça. Ca m'a l'air compliqué.
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.
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.
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 !
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é.
Quel est l'énoncé exact ?