Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
163 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Polygones à p côtés

Envoyé par OShine 
Polygones à p côtés
il y a quatre mois
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.


Re: Polygones à p côtés
il y a quatre mois
avatar
Dans la question, il y a 2 variables $n$ et $p$.
Si dans la réponse, $p$ n'intervient pas, c'est bizarre.
Re: Polygones à p côtés
il y a quatre mois
C'est quoi un polygone ? (La question est moins naïve qu'il n'y paraît.)
Re: Polygones à p côtés
il y a quatre mois
$\binom{n}{p}$ ?

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



Edité 2 fois. La dernière correction date de il y a quatre mois et a été effectuée par AD.
Re: Polygones à p côtés
il y a quatre mois
avatar
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.
Re: Polygones à p côtés
il y a quatre mois
avatar
...polygone...
Re: Polygones à p côtés
il y a quatre mois
Ah oui, "polygone" s'écrit comme "hormone", bien qu'il se prononce comme "cône".
Re: Polygones à p côtés
il y a quatre mois
avatar
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..



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Chaurien.
Re: Polygones à p côtés
il y a quatre mois
Est-ce que $ABCD$ est le même polygone que $ADCB$ ?
Re: Polygones à p côtés
il y a quatre mois
avatar
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.
Re: Polygones à p côtés
il y a quatre mois
C'est une figure géométrique formée d'une ligne brisée fermée.
Re: Polygones à p côtés
il y a quatre mois
avatar
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.
[www.youtube.com]



Edité 2 fois. La dernière correction date de il y a quatre mois et a été effectuée par Chaurien.
Re: Polygones à p côtés
il y a quatre mois
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 ?



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par AD.
Re: Polygones à p côtés
il y a quatre mois
@Chaurien
Merci mais je n'arrive pas à comprendre comment obtenir $X_p$.
Re: Polygones à p côtés
il y a quatre mois
avatar
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 winking smiley.
Voir OEIS [oeis.org].
Bonne journée.
Fr. Ch.



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Chaurien.
Re: Polygones à p côtés
il y a quatre mois
avatar
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 ?



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par lourrran.
Re: Polygones à p côtés
il y a quatre mois
avatar
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.



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Chaurien.
Re: Polygones à p côtés
il y a quatre mois
@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 spinning smiley sticking its tongue out

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 thumbs down



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par OShine.
Re: Polygones à p côtés
il y a quatre mois
avatar
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.
Re: Polygones à p côtés
il y a quatre mois
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.
Re: Polygones à p côtés
il y a quatre mois
avatar
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.



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Chaurien.
Re: Polygones à p côtés
il y a quatre mois
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é.



Edité 2 fois. La dernière correction date de il y a quatre mois et a été effectuée par OShine.
Re: Polygones à p côtés
il y a quatre mois
avatar
Bravo ! Encore un petit effort. Deux diagonales, c'est 4 sommets, non ?
Re: Polygones à p côtés
il y a quatre mois
Oui deux diagonales sont forcément liées à $4$ sommets.
Re: Polygones à p côtés
il y a quatre mois
@Lourran

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


Re: Polygones à p côtés
il y a quatre mois
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$.



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Math Coss.
Re: Polygones à p côtés
il y a quatre mois
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.
Re: Polygones à p côtés
il y a quatre mois
Je n'ai pas compris à quoi correspond votre schéma avec les nombres.
Re: Polygones à p côtés
il y a quatre mois
avatar
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.
Re: Polygones à p côtés
il y a quatre mois
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é.
Re: Polygones à p côtés
il y a quatre mois
avatar
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.
Re: Polygones à p côtés
il y a quatre mois
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.
Re: Polygones à p côtés
il y a quatre mois
avatar
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.
Re: Polygones à p côtés
il y a quatre mois
avatar
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 !
Re: Polygones à p côtés
il y a quatre mois
avatar
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é.

A demon wind propelled me east of the sun



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par AD.
Pièces jointes:
ouvrir | télécharger - differences successives.pdf (1.07 MB)
Re: Polygones à p côtés
il y a quatre mois
J'ai proposé un exercice comme ça à mes terminales...
Re: Polygones à p côtés
il y a quatre mois
@Kioups

Quel est l'énoncé exact ?
Re: Polygones à p côtés
il y a quatre mois
C'est un exercice d'un concours qui n'est pas encore clos.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 690, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page