[PDF] Chapitre 4 Relations dordre R est appelée une





Previous PDF Next PDF



Untitled

2) La relation d'inclusion ICY est une relation d'ordre (chap. II. § 1 prop relation d'inclusion est une relation d'ordre entre parties d'un ensemble E ...



Chapitre3 : Relations dordre

relation ” définie par x ” y ðñ x ´ y est pair. ‚ Sur l'ensemble 乡(Ω) des parties d'un ensemble Ω on connaît la relation d'inclusion



1. Complexité des algorithmes 1. Complexité des algorithmes

23 sept. 2011 relation d'inclusion sur les parties d'un ensemble. - ∅ ⊆ {a}. - {a} ... Une relation d'ordre ≤ sur un ensemble est une relation. - Réflexive.



Chapitre 1 ENSEMBLES

L'ordre naturel ≤ sur l'ensemble des nombres réels est une relation d'ordre total. 2. La relation d'inclusion ⊂ sur 乡(E) est une relation d'ordre. Elle n 



Relation

Soit E un ensemble l'inclusion notée ⊆



CHAPITRE 2 RELATION DORDRE

— Soit E une collection d'ensembles. Alors la relation d'inclusion est une relation d'ordre sur E. 2.2.3. Notation. — Sauf mention au contraire 



1. Relations binaires 2. Relations déquivalence 3. Relations dordre

relations sur l'ensemble des droites du plan ou de l'espace. L'inclusion ⊂ est une relation sur P(X) où X est un ensemble quelconque. Définitions. Soit R 



Inclusion différentielle impulsive dordre fractionnaire

. . . . . . . . . . . . . . . . . 16. 2.4 Relation entre la dérivée de Caputo et la dérivée de Riemann-Liouville . . 20. 2.5 La transformée de Laplace 



Solution viable dune inclusion différentielle du premier ordre

2.3 Caractérisation d'une relation d'ordre par une multi-application 30. 2.4 inclusion différentielle du premier ordre. Depuis les années 80 s'est déve ...



Preuve et Notations asymptotiques [pf] Exercices de cours

Objectif. Cet exercice manipule le grand-Oh. Donnez les relations d'inclusion entre les ensembles suivants : O(nlog n) O(2n)



Chapitre3 : Relations dordre

d'un ensemble ? on connaît la relation d'inclusion



1. Relations binaires 2. Relations déquivalence 3. Relations dordre

relations sur l'ensemble des droites du plan ou de l'espace. L'inclusion ? est une relation sur P(X) où X est un ensemble quelconque. Définitions.



Relation

Soit E un ensemble l'inclusion notée ?



RELATIONS BINAIRES

La relation d'inclusion ? sur. (E) est réflexive transitive et antisymétrique. • La relation « avoir le même signe » sur ? est réflexive



1 Relations binaires 2 Majorant minorant

https://www.i2m.univ-amu.fr/perso/laurent.regnier/enseignement/LangageMath/TD4-relations-d_ordre.pdf



Chapitre 1 ENSEMBLES

La relation d'inclusion ? sur ?(E) est une relation d'ordre. Elle n'est pas d'ordre total. Test 1.4. La relation de divisibilité sur N.



Chapitre 4 Relations dordre

R est appelée une relation d'ordre ou un ordre partiel si les conditions l'ensemble de ses parties P(T) est partiellement ordonné par l'inclusion.



Relations dordre

Définition (relation binaire). Soit E un ensemble. Une relation binaire. R sur E est un sous-ensemble de E × E. On note xRy pour signifier que.



Liste des symboles mathématiques usuels (LATEX)

Vous trouverez ci-dessous la liste des commandes LATEX permettant de produire les symboles mathématiques les plus courants. Cette liste est loin d'être 



1. Complexité des algorithmes

23 sept. 2011 3 . Relations fonctions et ordres vendredi 23 septembre 11 ... relation d'inclusion sur les parties d'un ensemble. - ? ? {a}.



7 Relations and Partial Orders - MIT OpenCourseWare

A relation is a mathematical tool for describing associations between elements of sets Relations are widely used in computer science especially in databases and scheduling applications A relation can be de?ned across many items in many sets but in this text we will focus on binary relations which represent an association



Relation binaire relation d'ordre treillis

Une relation d'ordre sur E est dite totale si deux éléments quelconques de E sont toujours comparables : pour tout x;y 2E on a xRy ou yRx Dans le cas contraire on dit que l'ordre est partiel Exemples est un ordre total sur N Z et R En général l'inclusion est un ordre partiel



Relations binaires Relations d’équivalence et d’ordre

Visualisation d’une relation d’ordre : idée d’orientation • Lorsque la relation d’ordre est totale comme 6dans R On peut représenter R sur une droite ?? ?7 ?2 53 0 1 ? 20 3 +? e ? 17 • Ce n’est plus le cas lorsque la relation d’ordre est partielle comme par exemple la relation de divisibilité



Searches related to relation d+ordre inclusion PDF

* L’inclusion est une relation d’ordre partiel sur les parties d’un ensemble: X = {abc} * Les entiers naturels peuvent etre munis d’un ordre plus subtilˆ que l’ordre usuel q est plus grand que p si q est multiple de p D48 est un treillis J -L Baril Relation binaire relation d’ordre treillis

  • Cours

    Définition

  • Exemples

    Voici quelques exemples de relation d’ordre 1. L’ordre lexicographique qui est l’ordre “du dictionnaire”. 2. La relation classique ? sur les entiers ou les réels. 3. La relation < sur les réels n’est pas une relation d’ordre : on n’a pas x < x. 4. La relation d’inclusion pour les ensembles. On note A ? B si A est inclus dans B.

Comment définir une relation d’ordre?

Relation d’ordre De?nition:´ Une relation sur X ? qui est re?exive´ , antisymetrique et´ transitive est appelee une relation d’ordre.´ On dit alors que X est partiellement ordonnee´ et on note ? a` la place de ?. Si (x,y) ? X2, x et y seront comparables si x ? y ou y ? x.

Comment savoir si une relation d’ordre est totale ?

Cette page a pour but de présenter les relations d’ordre à l’aide d’une partie cours et de quelques exercices corrigés. Une relation ? sur un ensemble E est une relation d’ordre sur E si elle vérifie ces trois propriété : Si pour tout couple, on a x ? y ou y ? x, on dit que le relation d’ordre est totale.

Comment définir une relation d’ordre sur un ensemble ?

Une relation ? sur un ensemble E est une relation d’ordre sur E si elle vérifie ces trois propriété : Si pour tout couple, on a x ? y ou y ? x, on dit que le relation d’ordre est totale. On définit une relation d’équivalence sur l’ensemble des entiers naturels par Elle est bien réflexive. On a bien : D’où x = y.

Quelle est la différence entre inégalité et inclusion ?

L'inégalité est une relation d'ordre sur N, Z ou R. L'inclusion est une relation d'ordre. Définitions. Une relation d'ordre sur E est dite totale si deux éléments quelconques de E sont toujours comparables : pour tout x;y 2E, on a xRy ou yRx. Dans le cas contraire, on dit que l'ordre est partiel.

Chapitre 4

Relations d"ordre

Nous allons discuter dans ce chapitre d"un type particulier de relation, lesrelations d"ordre. De telles relations

apparaissent dans des domaines vari ´es des math´ematiques. Elles ont´egalement un grand nombre de propri´et´es combinatoires tr `es int´eressantes que nous allons voir.

4.1. Ensemble partiellement ordonn´e (poset)D

´efinition 4.1.SoitAun ensemble etRune relation sur cet ensemble.1.Rest appel´eeune relation d"ordreou unordre partielsi les conditions suivantes sont v´erifi´ees(a)Pour touta?Aon a(a,a)?R(r´eflexivit´e).(b)Pour touta,b?Asi(a,b)?Ret(b,a)?Ralorsa=b(antisym´etrie).(c)pour touta,b,c?Asi(a,b),(b,c)?R, alors(a,c)?R(transitivit´e).2.Rest appel´e unordre totalsi c"est un ordre partiel et si poura,b?Asoit(a,b)?R, soit(b,a)?R.3.SiRest un ordre partiel surA, alors on appelle la paireP= (A,R)unensemble partiellement ordonn´e

ou unposetet on dit queAest un ensemble partiellement ordonn´e par rapport`aR. SiRest un ordre total,

on sont ditcomparable. Il y a de nombreux exemples d"ensembles partiellements ordonn ´es que vous connaissez d´ej`a. En voici une

petite liste :Exemple 4.2.1.L"ensembleZmuni de l"ordre naturel est totalement ordonn´e.2.L"ensembleNest partiellement ordonn´e par la relation de divisibilit´e. On note ce poset par(N,|).3.L"ensembleZn"est pas partiellement ordonn´e par rapport`a la divisibilit´e. Soitaun´el´ement non nul. Alors

adivise-a, et-adivisea. Maisan"est pas´egal`a-a, et donc la propri´et´e d"antisym´etrie n"est pas valide.4.SiTest un ensemble, l"ensemble de ses partiesP(T)est partiellement ordonn´e par l"inclusion. On note ce

(a1,...,an)Cet ordre est appel

´ee l"ordrelexicographique.

32Math´ematiques discr`etes6.SoitAl"ensemble totalement ordonn´e de l"exemple pr´ec´edent. AlorsAnest partiellement ordonn´e par

l"ordre suivant :

Les posets peuvent

ˆetre repr´esent´e par un certain type de graphe.D

´efinition 4.3.Un cycle dans un grapheG= (V,E)est un chemin qui commence et se termine sur le mˆeme

sommet. Un grapheG= (V,E)est appel´eun graphe orient´e acycliqueou simplement unDAGsiGest un graphe

orient

´e qui n"a pas de cycle.

Il se trouve que les DAGs sont essentiellement

´equivalents aux posets, comme le montre la proposition sui-

vante :Proposition 4.4.SoitRun ordre partiel sur un ensembleA. Alors, le graphe deRest l"union d"un DAG clos

par transitivit ´e et du grapheG?= (A,E?)o`uE?={(a,a)|a?A}. R´eciproquement, l"union d"un DAG transitivement closG= (V,E)et de l"ensembleΔ :={(v,v)|v?V}est un poset.D ´emonstration.Le graphe deRest l"union du grapheD= (A,E)etG?= (A,E?), o`uE={(a,b)|(a,b)?

R?a?=b}. On doit montrer queDest un DAG transitivement clos. Pour cela, supposons qu"il existe un cycle

a

0≂Ra1≂R··· ≂Ram≂Ra0dansD. Alors la condition d"antisym´etrie deRimplique quea0=a1=···=

a

m, ce qui est une contradiction. Cela nous montre queDne contient pas de cycles. La closure deD?G?par

transitivit

´e d´ecoule de la transitivit´e deR.

R ´eciproquement, supposons queG= (V,E)est un DAG transitivement clos, et quePest l"union deGet de

Δ. On doit montrer que cette union est le graphe d"un ordre partiel. La r´eflexivit´e de la relation est claire car le

graphe contientΔ. La relation est antisym´etrique, car sinon il existeraitv,w?V,v?=w, tels que(v,w)?Vet

(w,v)?V. Mais cela impliquerais la pr´esence d"un cyclev→w→vdansG, une contradiction. Finalement, la

transitivit

´e de la relation est´equivalente`a l"hypoth`ese queGest transitivement clos.Quand on dessine un diagramme d"un poset, on omet usuellement la r

´eflexivit´e et donc on ne dessine pas des

boucles sur tous les sommets du graphe. L"exemple suivant illustre cela.Exemple 4.5.(1)SoitA={2,5,6,10,30}etRla relation de divisibilit´e surA. son DAG est donn´e ci-

dessous :2561030

(2)SoitA={1,2,3,5,6,10,15,30}etRla relation de divisibilit´e surA. La repr´esentation par DAG de ce

poset est donn

´e ci-dessous :12356101530

Chapitre 4: Relations d"ordre33(3)En g

´en´eral, soitnun entier positif. On note(Div(n),|)le poset dont les´el´ements sont tous les diviseurs de

n, et la relation est celle de divisibilit´e. La partie (2) de cet exemple est le DAG de(Div(30),|).

Le lecteur s"est peut-

ˆetre d´ej`a aperc¸u que la repr´esentation par un DAG d"un poset contient un grand nombre

de redondance. Par exemple, dans le DAG de la premi `ere partie de l"exemple pr´ec´edent, l"arˆete de2`a30est redondante puisqu"il y a d ´ej`a une arˆete de6`a30et une entre2et6. L"arˆete entre2et30est implicite. La d ´efinition suivante rend cela plus pr´ecis :D

´el´ements dea?Pest ditminimals"il n"a aucun pr´ed´ecesseur. Un´el´ement deb?Pest ditmaximals"il

´el´ements2et5n"ont pas de pr´ed´ecesseur, ils sont donc minimaux. L"

´el´ement30n"a pas de successeur, il s"agit donc d"un´el´ement maximal. Les´el´ements6, et10sont des

pr

´ed´ecesseurs imm´ediats de l"´el´ement30.(2)Dans l"exemple 4.5 (2) le poset a exactement un

´el´ement minimal1et exactement un´el´ement maximal30.

Les pr

´ed´ecesseurs imm´ediats n"existent pas dans tous les posets. Par exemple, aucun des´el´ements du poset

Les pr

´ed´ecesseurs imm´ediats existent de mani`ere´evidente pour les posets finis. Pour de tel posets, il y a une

repr

´esentation tr`es pratique qui utilise lesDiagrammes de Hasse. Comme pour la repr´esentation par DAG, on

dessine les

´el´ements du posets comme les sommets d"un graphe, mais on ne connecte l"´el´ementa`a l"´el´ementb

alors on dessine le sommet correspondant `aasous le sommet correspondant`ab. Le diagramme final est alors

equivalent a tout le poset.Exemple 4.8.Les diagrammes de Hasse des posets des exemples 4.5 (1) et (2) sont donn

´es ci-dessous :2561030

12356101530

4.2. Chaˆınes et Lemme de ZornD

Le lemme de Zorn, donn

´e ci-dessous, garantit l"existence d"´el´ements maximaux et minimaux d"un poset qui a certaines propri

´et´es. Malgr´e son nom de "Lemme", il s"agit en fait d"un axiome qui est´equivalent`a l"axiome de

bon ordre et `a l"axiome du choix (axiomes dont on ne discutera pas ici).Th ´eor`eme 4.10(Lemme de Zorn).Un poset pour lequel chaque cha ˆıne admet une borne sup´erieure contient au moins un

´el´ement maximal. De mani`ere´equivalente, un poset pour lequel chaque chaˆıne admet une borne

inf ´erieure contient au moins un´el´ement minimal.

34Math´ematiques discr`etesLe lemme de Zorn est un outil puissant pour prouver un bon nombre d"assertions que nous consid

´erons usuel-

lement comme donn

´ees. Par exemple, on montre que tout espace vectoriel admet une base.Exemple 4.11.SoitKun corps (par exempleR) et soitVun espace vectoriel surK. Un ensembleS?Vest dit

lin

´eairement ind´ependantsi pour tout nombresn?N, touta1,...,an?Knon tous nuls, et touts1,...,sn?S

distincts deux `a deux, on a?n i=1aisi?= 0. UnebasedeVest un sous-ensembleBlin´eairement ind´ependant tel que V=? a????n?N,a1,...,an?K,b1,...,bn?B:a=n? i=1a ibi? deVcontenantLest un posetGpar rapport`a l"inclusion. (C"est un sous-poset de(P(V),?).) Supposons que

Cest une chaˆıne dansG. Soit alorsT=?c?Cc. Notez queTest une borne sup´erieure deC(c"est clair) et que

T?G(pourquoi?). Ainsi, en utilisant le lemme de Zorn, le posetGadmet au moins un´el´ements maximalB. Par

d

´efinition,Best lin´eairement ind´ependant. On affirme, qu"il s"agit´egalement d"un ensemble de g´en´erateur pour

Vet donc d"une base. Supposons le contraire, et supposons queWest l"espace vectoriel g´en´er´e parB. Soit alors

xun´el´ement deV-W. Par maximalit´e deB, l"ensembleB? {x}n"est pas lin´eairement ind´ependant, donc il

existen?N,b1,...,bn?B, eta1,...,an,a?Knon tous nuls tel que a

1b1+···+anbn+ax= 0.

Clairement,a?= 0car lesbisont lin´eairement ind´ependant. Ainsi,xest une combinaison lin´eaire desbiet

appartient `aW, une contradiction.

4.3. TreillisD

La preuve de la remarque suivante est laiss

´e au lecteur.Remarque 4.13.SoitLun treilli. Alors le supremum et l"infimum de n"importe quelle paire d"´el´ements est unique.

Un treillis n"a pas n

´ecessairement un´el´ement maximal ou minimal, mais si c"est le cas alors ces´el´ements sont

uniques :Proposition 4.14.SoitLun treilli. AlorsLa au plus un´el´ement minimal et un´el´ement maximal.D

qui impliquec=a=b.

La preuve pour l"unicit

´e d"un´el´ement maximal est analogue.Exemple 4.15.(1)Consid ´erons l"ensemble totalement ordonn´eRavec l"ordre naturel. AlorsRest un treilli. L"infimum deaetbestmin(a,b), est le supremum deaetbestmax(a,b). N´eanmoinsRn"admet ni d" ´el´ements maximal, ni d"´el´ement minimal.(2)Consid

´erons le poset(N,|). Il n"est pas totalement ordonn´e mais c"est un treillis : L"infimum deaetbest

pgcd(a,b), et le supremum deaetbest ppcm(a,b). Ce treillis a un unique´el´ement minimal1, mais n"admet

pas d"

´el´ement maximal.(3)Soit le poset(N0,|). C"est un treilli, et il admet un unique´el´ement maximal,0. Mˆeme si ce treillis a un

el´ement maximal, il contient des chaˆınes de longueur arbitraire.

Chapitre 4: Relations d"ordre35∅{0}{1}{2}{3}{0,1}{0,2}{0,3}{1,2}{1,3}{2,3}{0,1,2}{0,1,3}{0,2,3}{1,2,3}{0,1,2,3}Figure 4.1- Diagramme de Hasse deB4.(4)Consid

´erons maintenant le poset(Div(n),|)introduit dans l"exemple 4.5 (3). C"est aussi un treillis avec

a?b=pgcd(a,b)eta?b=ppcm(a,b). Il admet un unique´el´ement minimal1, et un unique´el´ement

maximaln. Le diagramme de droite de l"exemple 4.8 est le diagramme de Hasse de(Div(30),|).(5)Le treillis(P(n),?)est appel´e letreillis bool´een d"ordren, et est usuellement not´eBn. Il admet un unique

el´ement maximal,n, et un unique ´el´ement minimal,∅.La figure 4.1 montre le diagramme de Hasse deB4.

4.4. La fonction de M¨obius

SoitLun treillis fini et soitgune fonctionL→R. On d´efinit la fonctionf:L→Rpar ?a?L:f(a) :=? Le but de cette section est de trouver une expression pourgen terme def.D

´efinition 4.16.SoitLun treillis fini. Lafonction de M¨obius bivari´eesurLest la fonctionμL:L×L→Z

caract

L(x,b) =?1sia=b

0sinon.

not ´e encoreμLest d´efinie parμL(a) :=μL(t,a), pour touta?L.

Commenc¸ons par voir pourquoi les propri

´et´es d´efinies plus haut d´efinisse de fac¸on unique la fonction de M

¨obius.Proposition 4.17.La fonction de M

¨obius d"un treillis finiLest d´efinie de mani`ere unique par les propri´et´es de la d

´efinition pr´ec´edente.D

´emonstration.Supposons qu"il existe deux telles fonctions de M

¨obiusμ1etμ2, et quea,b?Lsont tels que

fini, non vide (a?S), et admet donc un´el´ement maximal. Appelons lec. Notez quec

2(b,b) = 1. On sait par d´efinition deμque pouri= 1,2

i(c,b) =-? c< i(x,b).

36Math´ematiques discr`etesLe terme de droite de cette

´equation est le mˆeme pour les deux valeurs dei, carcest un´el´ement maximal deS.

Ainsi, le terme de gauche doit

ˆetre le mˆeme aussi, une contradiction.On peut maintenant ´enonc´e le th´eor`eme principal de cette partie :Th

´eor`eme 4.18(Inversion de M¨obius sur les treillis).SoitLun treillis fini, etg,f:L→Rdes fonctions telle

que pour touta?Lon af(a) =? g(a) =?

L(b,a)f(b).D

´emonstration.On a

L(b,a)f(b) =?

L(b,a)?

b

L(b,a))

)g(c) =g(a).

Ce qui prouve le th

´eor`eme.Des fois, il est utile de consid

´erer une description "duale" de la fonction de M¨obius. La d´efinition plus haut

utilise que la somme de tous lesμL(x,b)entreaetbdeLvaut 0. Dans la formulation duale, on montre que la

somme de tous lesμL(a,x)pourxentreaetbvaut´egalement 0.Proposition 4.19.Supposons queLest un treillis fini avec comme fonction de M¨obiusμL. Soitaetbdes´el´ements

L(a,x) =?1sia=b

0sinon.

De plus, si une fonctionμLsatisfait cette condition et v´erifie de plusμL(a,a) = 1pour touta?LetμL(a,b) = 0

pour touta,b?Lnon comparables, alorsμLest la fonction de M¨obius deL.D

´emonstration.(Id

´ee.) Consid´erons une matriceMdont les lignes et les colonnes sont index´ees par les´el´ements

deL, et telle queMa,b=μL(a,b). De plus, consid´erons la matriceZdont les lignes et les colonnes sont aussi

index sous-jacent.) On laisse en exercice la preuve que l" ´enonc´e de l"inversion de M¨obius est´equivalent`a dire queZM est la matrice identit

´e. C"est`a dire queMest l"inverse deZ, mais alorsMZest aussi la matrice identit´e. L"entr´ee

(a,b)de ce produit est nulle sia?=b, et vaut1sia=b. Cette entr´ee est´egale`a x?LM a,xZx,b=?

L(a,x) =?

L(a,x).

Ce qui termine (l"id

´ee de) la preuve.L"existencedelafonctiondeM

cette forme duale. Pour calculerμL(a,b), on commence parμL(a,a) = 1. Ensuite, si on connaˆıt tout lesμL(a,c)

el´ementsxdans ce treillis et pour cela on va utiliser la proposition pr´ec´edente. Premi`erement il est clair que

L(1,1) = 1. Ensuite, supposons quexest un nombre premier (Dans ce cas, soit2,3, ou5). Alors en utilisant

la proposition 4.19 On a0 =? y|xμL(1,y) =μL(1,1) +μL(1,x), et doncμL(1,x) =-1. Ensuite, on calcule L(1,4) :on a0 =μL(1,1) +μL(1,2) +μL(1,4), et doncμL(1,4) = 0.

Le dessin suivant montre le diagramme de Hasse de ce treilli, et les valeurs deμL(1,x)Pour tous les´el´ements

du treillis :

Chapitre 4: Relations d"ordre3713515

261030

4122060

0000

Ici, "+" veut dire1, et "-" veut dire-1.?

De mani

`ere similaire, on peut calculer la valeur de la fonction de M¨obius sur nos deux treillis favoris :Th

´eor`eme 4.21.(1)SoitLle treilli(Div(n),|). Alors on a pour des nombres naturelsa,baveca|b|n: μ(a,b) =?(-1)tsib/aest le produit detnombres premiers distincts,

0sinon.(2)SoitSun ensemble fini, etLle treilli(P(S),?). Alors on a pour des sous-ensemblesX?Y?S:

μ(X,Y) = (-1)|Y-X|.D

´emonstration.(1)

Pour prouver le th

´eor`eme, on utilise l"unicit´e de la fonction de M¨obius (cf proposition 4.17). Il nous suffit

donc de montrer que la fonction donn

´ee dans l"´ennonc´e satisfait les trois propri´et´es de la d´efinition 4.19. Les deux

premi

`eres sont trivialement v´erifi´ees donc on se concentre sur la troisi`eme. On doit donc montrer que

d a|d|bμ

L(d,b) = 0.

Mais les nombresdtels quea|d|bsont en bijection avec les diviseursδdeb/aen´ecrivantaδ=d. Il faut donc

montrer que pourm?N(qui correspond`ab/a) on a

δ|mμ

L(1,δ) = 0.

Pour cela, supposons quem=?t

i=1peiio`u lespisont des nombres premiers etei≥1pour touti. Ainsi tout

δ|mest de la forme?t

i>1. On doit donc monter que L? 1,t? i=1p

εii?

= 0.

En utilisant encore une fois la d

´efiniton deμdu th´eor`eme, on voit que dans cette somme,μL(1,?t i=1pεii) =

(-1)so`usest le nombre deεinon nuls. L"ensemble des vecteurs(ε1,...,εt)qui ontscomposantes non nulles

est de cardinal?t s?. On en d´eduit L? 1,t? i=1p

εii?

=t? s=0? t s? (-1)s= (1-1)t= 0, et on a terminer. (2) On raisonne par r ´ecurrence surn=|Y-X|. On commence avecn= 0, ce qui est trivial. Supposons utilise maintenant le fait que?

X?Z?Yμ

L(Z,Y) = 0.

38Math´ematiques discr`etesMais

X?Z?Yμ

L(Z,Y) =μL(X,Y) +?

X?Z?Yμ

L(Z,Y)

=μL(X,Y) +n+1? i=1? n+ 1 i? (-1)n+1-i. Pour voir cela, supposons queY-X={b1,...,bn+1}. Alors tous les ensembles possiblesZsont obtenu comme

Z=X?To`uTest un sous-ensemble non-vide deY-X. Le nombre de tels sous-ensembles`ai´el´ements est?n+1

i?, et siZest un tel sous-ensemble, on aμL(Z,Y) = (-1)n+1-ipar hypoth`ese de r´ecurrence.

En continuant avec la derni

`ere expression, notez que n+1? i=0? n+ 1 i? (-1)n+1-i= (1-1)n+1= 0, ainsiμL(X,Y) = (-1)n+1, et le r´esultat en d´ecoule.D

´efinition 4.22.Comme la fonction de M

¨obius sur le treilli(Div(n),|)ne d´epend que du quotient de ses argu- ments, et en particulier ne d ´epend pas den, on d´efinit la fonction de M¨obius`a une variable (c"est la fonction originale)μdeNdans{-1,0,1}par μ(x) :=?(-1)tsixest le produit detnombres premiers distincts,

0sinon.

Ainsi,μ(x) =μL(1,x)o`uμLest la fonction de M¨obius de(Div(n),|), pour unnmultiple dex.

La preuve de la remarque suivante est laiss

´e en exercice.Remarque 4.23.La fonction de M

¨obiusμestfaiblement multiplicative: sinetmsont des entiers tels que

pgcd(n,m) = 1, alorsμ(nm) =μ(n)μ(m).Corollaire 4.24(Inversion de M¨obius originelle).Soitf,g:N→Rdes fonctions telles que pour toutn?Non

ag(n) =? d|nf(d). Alors on a pour toutn?N: f(n) =? d|nμ?nd g(d).D ´emonstration.SoitμLla fonction de M¨obius du treilli(Div(n),|). On af(n) =? d|nμL(d,n)g(d). Notez que L(d,n) =μL(1,n/d) =μ(n/d).4.5. Exemple : La fonction?d"Euler On donne dans cette section une application de la formule d"inversion de M

¨obius. Pour un entiern?Non

d"Euler. Par exemple,?(10) = 4, car les seuls entiers plus petit que10qui sont premier avec10sont1,3,7,9.

On commence par montrer que

n=? d|n?(d).(4.1)

Pour cela, on d

clair que les ensemblesFdsont disjoints. De plus l"ensemble{0,1,...,n-1}est´egal`a l"union desFd: sixest

un ´el´ements de l"ensemble pr´ec´edent, alorsx?Fdavecd=pgcd(x,n). On en d´eduit quen=? d|n|Fd|. On montre maintenant que|Fd|=?(n/d). Pour cela, remarquez quex?Fdssigcd(x/d,n/d) = 1. Ce qui prouve (4.1).

En appliquant la formule d"inversion de M

¨obius du corollaire 4.24 a (4.1), on voit que

?(n) =? d|nμ(n/d)d.

De cette formule, on peut facilement en d

´eduire les faits suivants :

Chapitre 4: Relations d"ordre391.sinest un nombre premier, alors?(n) =n-1: Dans ce cas les seuls diviseur sontnet1, et comme

μ(n) =-1, le r´esultat en d´ecoule.2.Sin=ptpour un nombre premierp, alors?(n) = (p-1)pt-1: Dans ce cas les diviseurs densont

1,p,...,pt, etμ(n/d)?= 0seulement sid=pt-1oud=pt; Dans le premier casμ(n/d) =-1, est dans

le second cas c"est1.3.Sin=PQo`u pgcd(P,Q) = 1, alors?(n) =?(P)?(Q): dans ce cas, tout diviseurddenpeut s"´ecrire

de mani `ere unique commed=d1d2avecd1un diviseur dePetd2un diviseur deQ(preuve?). Ainsi ?(n) =? d

1|P,d2|Qμ?PQd

1d2? d 1d2.

CommeP/d1etQ/d2sont premier entre eux et queμest une fonction faiblement multiplicative d"apr`es la

remarque 4.23, la derni `ere expression est´egale`a( d

1|Pμ?Pd

1? d 1) d

2|Qμ?Qd

2? d 2) =?(P)?(Q).

4.6. Exemple : Nombre de d´erangements

Und´erangementsurnest une application bijective densur lui m ˆeme qui ne fixe aucun´el´ements den. Par exemple les applications suivantes sont toutes des d

´erangements de4:

33221100

33221100

33221100

33221100

33221100

33221100

33221100

33221100

33221100

Dans cette section, on va calculer le nombre de d

´erangements denen utilisant la formule d"inversion de M

¨obius

surBn. SoitSun sous-ensemble den, et soitpn(S)le nombre d"application qui fixe tous les´el´ements deS, et

aucun des

´el´ements hors deS. De plus, soitqn(S)le nombre d"applications qui fixes tous les´el´ements deS(Mais

n"a pas de contrainte sur les ´el´ements hors deS). Clairement,qn(S) = (n- |S|)!, puisqu"une application fixant les ´el´ements deSpeutˆetre une permutation quelconque hors deS. De plus, on a q n(S) =? S?Tp n(T),

car les applications fixantSpeuventˆetre partitionn´ees en celles fixantTet celles ne fixant aucun´el´ements hors

deT, pour toutTcontenantS. Par application de la formule d"inversion de M¨obius, on obtient p n(S) =?

S?Tμ

Bn(S,T)qn(T)

S?T(-1)|T-S|(n- |T|)! (par le th´eor`eme 4.21 (2)) n? ?=|S|(-1)?-|S|?n- |S| ?- |S|? (n-?)!.

40Math´ematiques discr`etesLa derni

`ere´etape est obtenue en choisissant?:=|T|et en remarquant que le nombre d"ensemble contenantSest?n-|S|

?-|S|?. On est int´eress´e dans la valeur de cette expression pourS=∅, puisque dans ce caspn(∅)nous donne le

nombre de d

´erangements. On obtient

p n(∅) =n!?12! -13!

± ···+ (-1)n1n!?

=?n!e avece?2.7182818···qui est le nombre d"Euler. En particulier, quandn= 4, on obtient p

4(∅) =4!2!

-4!3! +4!4! = 12-4 + 1 = 9.

4.7. D´ecomposition en chaˆınes, Antichaˆınes, et LargeurD

´efinition 4.25.SoitPun poset. UneantichaˆınedePest une s´equencec1,c2,...,cmd"´el´ements dePtelle que

pour touti,j,i?=j,cietcjne sont pas comparable dansP. LaLargeurd"un poset finiPest la longueur maximale

d"une anticha

ˆıne deP.Exemple 4.26.1.Consid

´erons le poset((10),|). Les s´equences(1,2,4,8),(3,6),(5,10),(7), et(9)forment des cha

ˆınes disjointes de ce poset. L"ensemble{5,6,7,8,9}est une antichaˆıne de ce poset.2.Consid

´erons le treilliB4. Voici une liste des chaˆınes disjointes de ce poset : (∅,{0},{0,1},{0,1,2},{0,1,2,3}) ({1},{1,2},{1,2,3}) ({2},{2,3},{0,2,3}) ({3},{1,3},{0,1,3}) ({0,2}) ({0,3}).

L"ensemble suivant est une anticha

ˆıne :

{{0,1},{0,2},{0,3},{1,2},{1,3},{2,3}}.

SoitPun poset. Un ensemble{C1,...,Cm}de chaˆınes disjointes dePtel queP=?mi=1Ciest appel´eune

d

´ecomposition en chaˆınesdeP. Uned´ecomposition minimale en chaˆınesdePest une d´ecomposition pour laquelle

le nombre de cha ˆıne est minimal.Lemme 4.27.SoitPun poset.(1)Alors le cardinal de la d

´ecomposition minimale en chaˆınes dePest au moins´egal`a la largeur deP.(2)Siwest la Largeur deP,C1,...,Cwest une d´ecomposition en chaˆınes deP, etAest une antichaˆıne qui

comportew´el´ements, alors|A∩Ci|= 1pour touti= 1,...,w.D

´emonstration.(1) SoitAune antichaˆıne deP, etC1,...,Ctdes chaˆınes disjointes couvrantP. Alors pour tout

appartenir tout deux `aA, une contradiction. Comme lesCisont disjoints, on a|A|=?t i=1|A∩Ci|et ce dernier nombre est au plust. (2) sit=w, alorsw=|A|=?w |A∩Ci|= 1pour touti.En fait, le th

´eor`eme de Dilworth montre que le cardinal d"une d´ecomposition minimale en chaˆınes et la largeur

d"un poset sont les m

ˆemes. La preuve, donn´e ci-dessous, construit une d´ecomposition en chaˆınes du poset et une

anticha

ˆıne qui sont tout deux de mˆeme taille. En utilisant le lemme pr´ec´edent, il est alors possible de conclure

l"

´egalit´e de la largeur du poset avec le cardinal d"une d´ecomposition minimale en chaˆınes.Th

´eor`eme 4.28(Th´eor`eme de Dilworth).SoitPun poset fini. La largeur dePest´egale au cardinal d"une

quotesdbs_dbs35.pdfusesText_40
[PDF] relation d'ordre majorant minorant

[PDF] le representant permanent du royaume du maroc aupres de l onu est

[PDF] le developpement durable au maroc

[PDF] le développement durable au maroc définition

[PDF] conseil supérieur de l'éducation de la formation et de la recherche scientifique maroc

[PDF] rapport du conseil supérieur de l'enseignement maroc 2016

[PDF] vision stratégique 2015 2030 ppt

[PDF] montrer qu'une suite est décroissante par récurrence

[PDF] un+1 suite

[PDF] montrer qu'une suite géométrique est croissante

[PDF] la charte nationale de l'éducation pdf

[PDF] comment montrer qu'une suite est convergente

[PDF] suite de cauchy exemple

[PDF] montrer qu'une suite est de cauchy pdf

[PDF] suite de cauchy exercices