[PDF] Partitions dun n-gone Dec 28 2019 culièrement





Previous PDF Next PDF



Polygones réguliers Définition Un polygone (non-croisé) est régulier

Définition. Un polygone (non-croisé) est régulier si : – tous ses côtés sont de la même longueur. – tous ses angles sont de la même mesure. Exemple.



Partitions dun n-gone

Dec 28 2019 culièrement des partitions non-croisées d'unn-gone



Les quadrilatères - Lycée dAdultes

Jun 27 2016 quadrilatère croisé. • Un polygone convexe est un polygone non croisé dont les angles formés par deux côtés consécutifs sont inférieurs.



Olympiades Mathématiques Paris 2022 : Sujet

Démontrer la formule de Pick pour les polygones non croisés quelconques. Exercice 2 : Pointe de Platon. Un polygone régulier est un polygone dont les côtés 



PII: 0012-365X(72)90008-8

titions en classes non-croisées de l'ensemble des sommets d'un cycle [3] et d'autre part les de- coupages d'un polygone convexe au moyen d'un système de 



Demi-plans convexité et polygones

Dec 19 2012 Cet article contient des remarques sur les polygones croisés et le ... Un quadrilatère non croisé ABCD possédant deux côtés opposés égaux et ...



Jeux de données SIG – Vérification et correction des géométries

Jun 26 2017 polygone à partir d'une limite non simple n'a pas de sens. ... aucun intérieur d'un polygone ne croise celui d'un autre.



POLYGONES RÉGULIERS

Si n est un entier supérieur ou égal à 3 un polygone à n côtés contient n segments et n sommets



Note mathématique Une formule générale pour laire dun polygone

entre le centre du polygone et le milieu d'un côté). D'autres s'appliquent dans le cas général d'un polygone simple (non croisé) mais dépendent.



Épreuve de mathématiques CRPE 2018 groupe 3.

2. Affirmation 2 : si un polygone non croisé A a un périmètre supérieur au périmètre du polygone non croisé B alors l'aire du polygone A est supérieure.



Formules du polygone régulier à n côtés

Un polygone non croisé est dit convexe si toutes ses diagonales sont à l’intérieur de la surface délimitée par le polygone Dans le cas contraire donc si au moins une diagonale est à l’extérieur du polygone (non croisé) il est dit non convexe ou encore concave



échanges - publimathuniv-iremfr

Prenons un polygone non croisé p Dire qu'il existe trois sommets consécutifs ABC tels que le polygone P -IBI soit lni aussi non croisé équivaut à dire que le segment lACI n'a pas d'intersection avec les autres côtés du polygone Supposons que IAC[ ait une intersection avec un autre côté [B"Cl



Espace et géométrie au cycle 3 Les polygones - Education

polygone est une surface délimitée par une ligne brisée fermée constituée de segments de droites La notion de convexité n’apparait pas dans les programmes de la scolarité obligatoire il n’est pas utile de parler de polygone convexe polygone concave ou de polygone croisé au cycle 3 Néanmoins lorsqu’un

Comment savoir si un polygone est croisé ?

Si nest un entier supérieur ou égal à 3, un polygone à ncôtéscontient nsegments et nsommets, qui sont les extrémités des segments, chaque sommet étant commun à exactement deux côtés parmi les n. On dit qu’il est croisési au moins deux côtés se coupent ailleurs qu’aux sommets. Sinon, il est dit non croisé.

Comment calculer l'aire d'un polygone non croisé?

L'aire d'un polygone non croisé est l'aire de la surface enclose par le polygone. Si le polygone est régulier, son aire A vaut : et R le rayon du cercle qui lui est circonscrit. Comme l'angle au centre vaut 2 ? / n radians, et que sin x ? x et cos x ? 1 quand x est voisin de 0, l'aire tend vers ? R2 quand n tend vers l'infini.

Qu'est-ce que le polygone régulier ?

On appelle polygone régulierun polygone dont les côtés sont de même longueur mais aussi tel que les sommets sont sur un même cercle (on dit que ces points sont cocycliques). Le cercle est donc circonscrit au polygone. Les polygones réguliers à 3 et 4 côtés s’appellent respectivement des triangles équilatérauxet des carrés.

C'est quoi circonscrire un polygone ?

Circonscrire un polygone Sens : Dessiner un polygone dont tous les côtés sont tangents à une courbe. Origine : Cette expression est empruntée au vocabulaire de la géométrie. Il s'agit de construire un polygone dont tous les côtés sont tangents à une courbe.

Partitions d"unn-gone

Thibault JUILLARD

28 décembre 2019

Résumé

Cet article est une étude assez générale des partitions d"un ensemble ?ni et plus parti-

[2]. On s"intéressera en particulier à la structure de treillis pour les partitions en général

et pour les partitions non-croisées. En nous reposant sur des formules établies dans un autre article de Kreweras [3], nous compterons comme cela a été fait dans l"article [2] les partitions non-croisées d"un type donné pour en déduire le nombre total de partitions non-croisées dun-gone.

Table des matières

1 Partitions d"un ensemble 1

1.1 Dé?nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Dénombrement des partitions . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3 Treillis des partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2 Petit intermède de combinatoire 3

2.1 Suites ?nies de somme ?xée . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.2 Identités multinomiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.3 Somme sur les partitions de taille ?xée . . . . . . . . . . . . . . . . . . . . . .

4

3 Partitions non-croisées d"un polygone 4

3.1 Dé?nition géométrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.2 Treillis des partitions non-croisées . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.3 Dénombrement des partitions non-croisées . . . . . . . . . . . . . . . . . . . .

6 1

Partitions d"un ensemble

Cette partie reprend la présentation classique du dénombrement des partitions d"un en- semble ?ni, que l"on peut par exemple retrouver ici [1]. 1.1

Dé?nition

On ?xenun entier non-nul. On considère un ensemble ànéléments que l"on noteEn. On

s"intéresse à la notion de partitions, c"est-à-dire que l"on cherche à regrouper les éléments de

E nen sous-ensembles. 1

Définition1.1 - Partition deEn.

qui recouvrentEn: E n=Ä i2IA i: On notePnl"ensemble des partions deEnetPnson cardinal : c"est lenèmenombre de Bell. Remarque 1.1.La donnée d"une partition équivaut à celle d"une relation d"équivalence sur P n: toute partition est l"ensemble des classes pour et une seule relation d"équivalence. 1.2

Dénombr ementdes partitions

On rappelle que

n k =n!k!¹nkº!est le nombre de parties àkéléments d"un ensemble

ànéléments. On s"intéresse dans cette partie au calcul dePn, le nombre de partitions d"un

ensemble ànéléments. On va pour cela chercher une relation de récurrence sur la suite des

¹Pnºn2N, puis en donner une formule explicite à l"aide de la série génératrice associée.

Proposition1.1 - Relation de récurrence sur¹Pnºn2N. ¹Pnºn2Nest donnée par la relation de récurrence :P0=1et8n2N;Pn+1=n k=0 n k P k: Démonstration:On écritEn+1=Ent fxn+1g. Construire une partition deEn+1c"est : choisir le nombrenkd"éléments qu"on met dans la partie contenantxn+1(nkétant le nombre d"éléments sans compterxn+1); choisir lesnkéléments de cette partie dansEn, ce qui faitn k

choix; en?n choisir les parties restantes de la partition dans leskéléments restant, ce qui fait

P

kchoix.Pour déterminer explicitementPnen fonction den2N, on peut introduire la série géné-

ratrice suivante :

G¹Xº=+1Õ

n=0P nn!Xn: On démontre queGvéri?e l"équation di?érentielle suivante.

Lemme 1.2.8x2R;G0¹xº=exG¹xº:

On en déduit donc que pour toutx2R,G¹xº=eex1. On développe cette fonction en série entière au voisinage de0et on en déduit, par identi?cation des coe?cients, la formule suivante.

Théorème1.3 - Nombre de partitions deEn.

On a pour tout entiern:

P n=cardPn=1e +1Õ k=0k nk!: Remarque 1.2.On retrouve la suite des moments d"une loi de PoissonP¹1º. 1.3

T reillisdes partitions

La présentation qui va suivre s"inspire de l"article de Kreweras sur les partitions d"un cycle [2]. 2 La dé?nition que l"on a donnée de la partition d"un ensemble ne nécessite pas que l"en- semble soit ?ni. On suppose à présent queEest un ensemble quelconque et on notePl"en- semble des partitions deE. On dé?nit surPune relation d"ordre4, dite relation de ra?ne- ment, que l"on dé?nit pour toutes partitionsfAigi2IetfBjgj2Jpar : fAigi2I4fBjgj2J()8i2I;9j2JjAiBj: Remarque 1.3.Lejtel queAiBjest nécessairement unique, s"il existe. ¹P;4ºest un ensemble partiellement ordonné. On va voir qu"il possède une structure riche, celle de treillis.

Définition1.2 - Treillis.

Un ensemble (partiellement) ordonné¹T;6ºest un treillis si toute pairefa;bgd"éléments deTadmet une borne inférieure et une borne supérieure, notéesa^beta_b. Exemples 1.1- Treillis.•Rpour l"ordre usuel sur les nombres. •L"ensemble des parties d"un ensemble pour l"inclusion, l"intersection et l"union étant les opérateurs de borne inférieure et supérieure. de l"union.

Proposition1.4 - Structure de¹P;4º.

¹P;4ºa une structure de treillis partiellement ordonné. Démonstration:Pour la borne inférieure : on pose fAigi2I^ fBjgj2J=fAi\Bj:¹i;jº 2IJ;Ai\Aj,œg: On poseAetBles relations d"équivalences associées aux deux partitions. On poseCla rela- tion d"équivalence engendrée parAetB: c"est la plus petite relation d"équivalence telle que xAyouxByimpliquexCy(cela revient à fusionner toutes les classes deA[Bayant des

points communs). On posefAigi2I_ fBjgj2Jla partition associéesC.Exemple1.2.Onconsidèrel"ensembleEdesentiersentre1et10.Onsedonnedeuxpartitions:

A=ff1;3;4;5g;f2;6;10g;f7;8;9gg;

B=ff1;3;4;5;9;10g;f2;6;7;8gg:

On calcule alors :

A^B=ff1;3;4;5g;f10g;f2;6g;f9g;f7;8gg;

A_B=fEg

2

Petit intermè dede combinatoir e

des formules suivantes, qui sont énoncées et démontrées par Kreweras dans [3]. On se place

dans une anneau¹A;+;ºcommutatif, donc on ?xee2A. Pour toutx2Aetq2N, on pose 3

2.1Suites ?nies de somme ?xé e

On posen;q2Ndeux entiers naturels.

Proposition2.1 .

Le nombre de suites¹i1;:::;inºd"entiers strictement positifs de somme égaleqestq1 n1

Corrolaire2.2 .

Le nombre de suites¹i1;:::;inºd"entiers positifs ou nuls de somme égaleqestn+q1 n1 2.2

Identités multinomiales

On posen2Netx1;:::;xn2A. On poseq2N. Pouri1;:::;iqdes entiers naturels de sommei1++ip=q,onposeq i

1;:::;in

=q!i

1!in!lacoe?cientmultinomialcorrespondant

au nombres de façons de composer un mot deqlettres contenantijfois la lettreajpour16 j6n. Proposition2.3 - Formule du multinôme généralisée.

¹x1++xnºq=Õ

i

1++in=q

q i

1;:::;in

¹x1ºi1¹xnºin.

Remarque 2.1.Il y an+q1

n1 termes dans la somme. Corrolaire2.4 - Formule du multinôme classique.

¹x1++xnºq=Õ

i

1++in=q

q i

1;:::;in

x

1i1xnin.

2.3

Somme sur les partitions de taille ?xé e

On posekun entier. SiI f1;2;:::;ng, on posexI=Õ i2Ix i. On peut montrer par récur- rence surnla formule suivante.

Proposition2.5 - Formule magique (Kreweras).

I=fI1;:::;Ikg

partition def1;:::;ngk j=1¹xIjºcardIj1=n1 k1

¹x1++xnºnk.

Remarque 2.2.Attention, il y a une coquille dans la formule (3) de l"article [3] : il faut rem- placerÍparÎ. 3

Partitions non-cr oiséesd"un p olygone

Ce qui va suivre puise son contenu dans l"excellent article de Kreweras sur les partitions non-croisées d"un cycle, à quelques arrangements près [2]. 4

3.1Dé?nition gé ométrique

On considère de nouveau l"ensemble ?niEn, qui contientn2Néléments. On réaliseEn

dans le plan euclidien comme l"ensemble des sommets du polygone régulier àncôté, orienté

dans le sens trigonométrique. C"est aussi le groupe multiplicatif engendré par la racinenèmede

l"unitéξ=exp¹2iπnº. SiAest une partie du planR2, l"enveloppe convexe deAest l"ensemble des combinaisons t

1x1++tkxkoùn2N,t1;:::;tn>0,x1;:::;xn2Aett1++tn=1. L"enveloppe

convexe est le plus petit ensemble convexe contenantA. Pour un ensemble ?ni de points du planp1;:::;pq, leur enveloppe convexe correspond à un polygone contenant tous les points et dont les sommets sont parmi ces pointsp1;:::;pq.

Définition3.1 - Partition non-croisée deEn.

On appelle partition non-croisée deEnune partitionfAigi2I2Pntelle que pour tous i;j2Idistincts, les enveloppes convexes deAietAjsont disjointes.

On notePn:c:nl"ensemble des partitions non-croisées etPn:c:nson cardinal.Figure1 - À gauche une partition non-croisée, à droite une partition croisée.

3.2

T reillisdes partitions non-cr oisées

La relation de ?nesse4fait dePn:c:nun ensemble partiellement ordonné. Nous allons voir que c"est lui aussi un treillis, mais que ce n"est pas un sous-treillis de¹Pn;4º. On commence à s"intéresser à la notion de fermeture non-croisée. Lemme 3.1.SoitA2Pnune partition deEn. On poseAla partition obtenue en fusionnant

deux à deux les parties dont les enveloppes convexes se croisent.Aest la plus ?ne parmi toutes les partitions non-croisées moins ?nes queA.

Démonstration:SoitBune partition non-croisée moins ?ne queA. Montrons queA4B. Soit A

1;:::;Ak2Atels queA1[[Ak2A. Il existeB1;:::;Bk2Btels queA1B1;:::;Ak

B k. SiAietAjont des enveloppes convexes qui se croisent, alors nécessairement celles deBi etBjaussi doncBi=Bj(vu queBest non-croisée). On en déduit queB1==Bket donc A

1[ [AkB1. Il vient que toutA2Aest contenu dans un certainB2B.Ce lemme permet alors de donner la dé?nition suivante.

Définition3.2 - Fermeture non-croisée.

SoitA2Pnune partition deEn. On appelle fermeture non-croisée deAla partitionA, qui est donc la borne inférieure des partitions non-croisée moins ?nes queA. 5 La notion de fermeture non-croisée nous permet d"établir sans plus de peine la proposition suivante.

Proposition3.2 - Structure de¹Pn:c:n;4º.

¹Pn:c:n;4ºest un treillis partiellement ordonné. Démonstration:SiA;Bsont deux partitions non-croisées alors on poseA^n:c:B=A^Bet

A_n:c:B=A_B. Ce sont les bornes inférieures et supérieures deA;BdansPn:c:n.Remarque 3.1.On remarque qu"une partieT0d"un treillisT, si a elle-même une structure de

treillis, ne conserve pas forcément les bornes inférieures et supérieures deT. 3.3

Dénombr ementdes partitions non-cr oisées

On introduit deux notions annexes qui serviront à compter les partitions non-croisées. oùx2Aetxξk+12A. Une lacune deAest donc un ensemble de points consécutifs sur len-goneEn, ces points étant dans le complémentaire deAet l"ensemble étant délimité par deux points (pas forcément distincts) qui eux sont dansA. •Un type de partitions®tdeEnest une suite d"entiers naturels¹tiºi2Ntelle que+1Õ i=1it i=n. Une partitionAest dite de typetsi pour touti2N,Acontienttiparties de taillei.

On note

®tle cardinal commun des partitions de type®t:®t=+1Õ i=1t i.

On note¹nºk=n!¹nkº!la factorielle tronquée denpark, qui désigne le nombre de listes

ordonnées dekéléments distincts deEn. Lemme 3.3.Soithun entier naturel etc1;:::;chdes entiers non-nuls. Le nombre de parties AdeEnayantklacunes de cardinaux respectifsc1;:::;ckest :n¹a1ºk1, aveca=n ¹c1+ +ckº=cardA.

du point " initial » (le premier dans le sens trigonométrique) deC1: il y ampossibilités. On

choisit dans quel ordre (toujours en suivant le sens trigonométrique) vont se placerC2;:::;Ch

aprèsC1: il y a¹k1º!possibilités. En?n on choisit la tailleai>0de l"espace laissé entreCiet

C i+1pouri0tels quea1++ak=a: il y aa1 k1 possibilités (proposition 2.1).

On a doncn¹k1º!a1

k1

=n¹a1ºk1possibilités.Remarque 3.2.Le nombre trouvé ne dépend pas des valeurs des cardinauxc1;:::;ck.

Proposition3.4 .

Soit ®tun type de partitions deEn. Le nombre de partitions non-croisées de type®test donné par la formule :¹nºj®tj1+1Ö i=11t i!. 6 Soit une partitionAde type®t. On remarque que chaque termeti!correspond à la donnée d"un ordre sur l"ensemblefA2AjcardA=ig, qui est de cardinalti. On va donc à présent

s"intéresser à des familles¹Aiº16i6hordonnées dans l"ordre croissant des¹cardAiº16i6h, telles

quefAig16i6hsoit une partition deEn. Une telle famille se quali?ée de partition ordonnée. Montrons le lemme suivante, qui est équivalent à la proposition 3.4. de partitions non-croisées ordonnées de type

®test¹nºj®tj1.

Démonstration:On procède par récurrence surn. Le résultat est évident pourn=1, cas pour

lequel on n"a qu"une seule partition possible. On suppose le résultat vrai pour des polygones ayant1;:::;n1côtés et on cherche à le montrer pourn>2. On veut trouver toutes les partitions non-croisées ordonnéesAdeEnde type®t. On note h=®tet on remarque que le type®tcorrespond à une suite croissante¹a16a266ahºqui est celles de cardinaux des classes d"une partition non-croisée ordonnée¹A1;A2;:::;Ahº. Chaque ensembleAi, pouri¹Aiºi2Ijest une partition non-croisée ordonnée de type®tjtel que®tj=cardIj.Cjest de cardinal

c j=Õ i2Ija i=aIj. choisit une partitionI=fI1;:::;Ikgdef1;:::;h1g, cette partition étant de taillek. On pose pour16j6k:cj=aIj=Õ i2Ija i. On choisit ensuiteAhune partie ayantklacunesC1;:::;Ck de cardinauxc1;:::;ck. On note®tile type induit par la sous-suite de cardinaux¹aiºi2Ijet on

construit une partition non-croisée ordonnée¹Aiºi2Ijde type®tjdeCj: on peut parler de parti-

tion non-croisée deCjsi on le voit, à déformation près, comme uncj-gone. La famille¹Aiº16i6h

ainsi construite est une partition non-croisée ordonnée deEnde type®t.

Le nombre de possibilités est donc

+1Õ k=1Õ

I=fI1;:::;Ikg

partition def1;:::;h1gn¹ah1ºk1k1Ö j=1¹aIjºcardIj1: En e?et le lemme 3.3 donne le nombre de parties ayantklacunes de cardinaux donnés et l"hy- pothèse de récurrence permet de compter les partitions dans chaque lacune. On utilise l"identité de Kreweras (proposition 2.5) pour calculer la somme interne :

I=fI1;:::;Ikg

partition def1;:::;h1gk1Ö j=1¹aIjºcardIj1=h2 k1

¹a1++ah1ºhk1=h2

k1

¹nahºhk1:

On utilise ensuite la formule 2.3 :

+1Õ k=1nh2 k1 On a donc la formule établie pourn, l"hérédité est établie. Par récurrence, la formule est démontrée.7 La proposition 3.4 découle de ce lemme. On peut maintenant s"intéresser au calcul du nombre de partitions non-croisée en un nombre ?xé de classes. On fait attention au fait qu"on s"intéresse de nouveau à des partitions non-ordonnées.

Proposition3.6 .

Soithun entier naturel. Le nombres de partitions non-croisées enhclasses deEnest n+1 h n1 nh Démonstration:On connait le nombre de partitions pour un type®t?xe,®t=h. Le nombre de partitions non-croisées enhclasses est donc la somme

¹t1;t2;:::;tnº

t

1+t2++tn=ht1+2t2++ntn=n¹nºh1t

1!t2!tn!=¹nºh1h!Õ

¹t1;t2;:::;tnº

t

1+t2++tn=ht1+2t2++ntn=nh!t

1!t2!tn!:

Pour conclure, il su?t donc de montrer l"identité suivante :

¹t1;t2;:::;tnº

t

1+t2++tn=ht1+2t2++ntn=nh!t

1!t2!tn!=n1

h1 Le terme de droite est le cardinal de l"ensembles des suites¹a1;:::;ahºd"entiers strictement ett1+2t2+:::ntn=n: il y ah t

1;t2;:::;tnfaçons de choisir une telle suite. En sommant, on a la

formule voulue.Pour obtenir le nombre total de partitions non-croisées, il nous reste à sommer la formule

pour toutes les valeurs dehpossibles. Avec la formule du multinôme généralisé (proposition

2.3), on obtient la formule suivante.

Théorème3.7 - Nombre de partitions non-croisées d"unn-gone.

Pour tout entiern:

P n:c:n=1n+1 2n n

On retrouve la suite des nombres de Catalan.

Références

[1] Wikip edia.Nombre de Bell. Disponible sur :https ://fr.wikipedia.org. [2] G. Kr eweras,On the noncrossing partitions of a cycle, 1972. [3] G. Kr eweras,Une famille d"identités mettant en jeu toutes les partitions d"un ensemble ?ni de variables en un nombre donné de classes, Comptes-rendus de l"Académie des Sciences de

Paris, t. 270, p. 1140, 5 janvier 1970.

8quotesdbs_dbs26.pdfusesText_32
[PDF] polygone convexe diagonales

[PDF] convexe concave définition

[PDF] polygone concave

[PDF] polygone définition

[PDF] population urbaine mondiale 2015

[PDF] evolution population urbaine mondiale

[PDF] population urbaine mondiale 2050

[PDF] population urbaine mondiale 2017

[PDF] ensemble formé par une grande ville et sa banlieue

[PDF] taux durbanisation par continent

[PDF] une personne qui vit en ville

[PDF] quel quelle quelle cm2 lecon

[PDF] quel quelle qu'elle pdf

[PDF] homophones quel quelle quelle exercices

[PDF] trace écrite quel quelle quelle cm2