POLYNOMES MULTIVARIES ET COMBINATOIRE

Publié par

Niveau: Supérieur, Bac+8
POLYNOMES MULTIVARIES ET COMBINATOIRE O. Marguin — 18 mai 2011 Par son efficacite, le calcul formel sur les polynomes multivaries permet de resoudre de fac¸on spectaculaire certains problemes combinatoires. Avant d'en voir des exemples, nous rappelons quelques proprietes des series generatrices. Ce chapitre est accompagne d'une feuille d'illustrations en Maple. 1 Series generatrices 1.1 Cas d'une variable Soit u = (un)n>0 une suite d'elements d'un corps K (dans tout ce qui suit, K sera le corps des rationnels). Nous noterons U(X) sa serie generatrice, c'est-a-dire la serie formelle de K[[X]] definie par : U(X) = +∞∑ n=0 unX n. Par exemple, la suite constante egale a 1 a pour serie generatrice : 1 + X + X2 + · · · = 1 1?X 1.2 Recurrences lineaires Supposons que la suite (un) verifie une recurrence lineaire d'ordre k de la forme : un = a1 un?1 + a2 un?2 + · · ·+ ak un?k (n > k). Alors U verifie : U(X) = P (X) + U(X)(a1 X + a2 X 2 + · · ·+ ak X k) ou P (X) est un polynome de degre k ? 1 dependant des ai et des valeurs initiales u0, u1, .

  • calcul formel

  • feuille d'illustration

  • recherche du coefficient de c1c2

  • resoudre de fac¸on spectaculaire

  • developpement brutal de pn

  • maple possede


Publié le : dimanche 1 mai 2011
Lecture(s) : 17
Tags :
Source : math.univ-lyon1.fr
Nombre de pages : 6
Voir plus Voir moins
POLYNOMES MULTIVARIES ET COMBINATOIRE
O. Marguin — 18 mai 2011
Parsonecacite´,lecalculformelsurlespolynˆomesmultivarie´spermetdere´soudredefa¸conspectaculaire certainsprobl`emescombinatoires.Avantdenvoirdesexemples,nousrappelonsquelquesproprie´te´sdes s´eriesge´n´eratrices.Cechapitreestaccompagn´edunefeuilledillustrationsenMaple.
1S´eriesge´ne´ratrices 1.1 Casd’une variable Soitu= (un)n>0counsrpnemedstdet´le´seiunuK(dans tout ce qui suit,Ksera le corps des rationnels). Nous noteronsU(X) sag´ieers´ciearrtnee´m´eelrlieelfaors-diretd-e`acse,K[[Xneid]e´]ap:r +X n U(X) =unX . n=0 Parexemple,lasuiteconstante´egale`a1apourse´riege´ne´ratrice: 1 2 1 +X+X+∙ ∙ ∙= 1X 1.2Re´currencesline´aires Supposons que la suite (unueire´v)inelncreurecr´nerordee´iaerdkde la forme : un=a1un1+a2un2+∙ ∙ ∙+akunk(n>k). AlorsU:eriv´e 2k U(X) =P(X) +U(X)(a1X+a2X+∙ ∙ ∙+akX) o`uP(Xopyltsnudedeˆnmor´ege)ekedtn1sepd´daenaiet des valeurs initialesu0, u1, . . . , uk1(cf [3], p.542). Ainsi : P(X) U(X) =. 2k 1a1Xa2X− ∙ ∙ ∙ −akX Parexemple,las´erieg´ene´ratriceF(Xeiaprccdie´nFidenaboaselteuid)f0= 0,f1= 1 etfn= fn1+fn2pourn>2v´eritaoi:nele´uq X F(X) = 2 1XX i`eme ce qui permet, avec Maple, de calculer sonntnrsparte`reemtxfeusdLet.enemidosse´lc-snoitcno seriesetcoeffX(e)naFte´em´nleimplntsses:.Rappelonsqueletegemr´ne´larebosentindteco´eosmp   1 11 F(X) =√ − 5 1ϕX1ϕX ou`ϕtlue:sre,dbOroo`mden   1 n n fn=ϕϕ . 5 Mapleposs`ede´egalementlafonctionrsolveriae´nilsecnerruecr´estlouesr´ui,itnotsarliulledeuiloirfes:vq section 1. Remarquemiˆoynolr´tie(alce´redelpecnerruensDafelalluiied.ion2,ilyaunexempllsurttaoi,nestc de[2],p.177)ou`onutiliselafonctionguessgf.ceriatern´urtrpogee´e´irlrsauoev
1
Agr´egationdemathe´matiquesoptionC:alg`ebreetcalculformel
Polynˆomesmultivarie´setcombinatoire
1.3 Casde plusieurs variables Si (ui1,...,iknesuestuultiitemcie´i-dn),easg´ie´eentrraeic´sreU(X1, . . . , Xks´erieformelledee)alts K[[X1, . . . , Xk:rapei]n]´ed X i1ik U(X1, . . . , Xk) =.. . . X ui1,...,ikXk 1 i1,...,ik>0 Par exemple (cf [1] p.58 et p.99) :   n lasuitedoubledescoecientsdubinˆomeapours´erieg´en´eratrice: k  n X XX X n n1 n kn kn n X Y=X Y=X(1 +Y) =, k k1X(1 +Y) n,k>0n>0k=0n>0 lase´rieg´ene´ratriceduminimumdekentiersui1,...,ik= min(i1, . . . , ik)estdonn´eepar: X1X2. . . Xk U(X1, . . . , Xk) =. (1X1)(1X2). . .(1Xk)(1X1X2. . . Xk) La fonctionmtaylorlove´e(dtdenemppelpaMedluapeusiayeTr`lo)selmrepavsrbairnirlesetdobte premierstermesdunes´erieg´ene´ratricemultivarie´e.Silonchercheuncoecientbienpr´ecis,ilest souventplusecaceded´evelopperlas´erieg´en´eratriceparrapport`alunedesvariablesavecseries, extrairelecoecientdudegr´esouhaite´aveccoeff, puis recommencer avec une autre variable, etc.
2De´nombrement 2.1 Premierexemple Decombiendefac¸onspeut-onviderunfˆutdebie`rede100litresenutilisantundemi(re´cipientdun quartdelitre),unse´rieux(undemi-litre)etunformidable(unlitre),sanstenircomptedelordredes op´erations? Pourn>0, notonsunredenomblerenuvedinodsafc¸utfˆdenquarts de litres. Alorsunest le nombre de triplets d’entiers naturels (d, s, ft:anire´v) d+ 2s+ 4f=n, n doncunest le coefficient enXpoleemepedtn:dad´evnsle 2 24 48 U(X) =(1 +X+X+∙ ∙ ∙)(1 +X+X+∙ ∙ ∙)(1 +X+X+∙ ∙ ∙) 1 =.(1) 2 4 (1X)(1X)(1X) On trouveu400ov:1alriiuefdellllitrusioatsen,=1020el3nO.tcoirr´aynevemenegalxemptune d’utilisation de la fonctionrgf findrecur´einreaireurelncelenia,uqisuipermetquren´rceedediven calcul de l’expression deund’abord sansrsolve, puis avec. 2.2Deuxie`meexemple:partitionsdentiers Soitnun entier naturel>1. Unepartition dendeestunse´rperenoitatnenen somme d’entiers>1, qu’on appelle lessommantsde la partition (cf [1], p.104). Soientpnle nombre de partitions denetpn,m le nombre de partitions denenmsommants. On a par exemple :
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1
doncp5= 7, p5,1=p5,4=p5,5= 1,p5,2=p5,3= 2. Si on notexilnemorbdeseommants´egaux`ai, il est clair que :
2
Agre´gationdemath´ematiquesoptionC:alg`ebreetcalculformel
Polynˆomesmultivari´esetcombinatoire
ladonn´eedunepartitionden´erbmonnesreitnesune´eedtionsoluavtuqeiuodnna`alxi>0 de : x1+ 2x2+∙ ∙ ∙+n xn=n, – sien plus on veutmsommants, il faut ajouter la condition : x1+x2+∙ ∙ ∙+xn=m. Parconse´quent,lase´riege´n´eratricede(pn,m) est : X n m P(X, Y) =1 +pn,mX Y 16m6n 1 = (2) 2 3 (1XY)(1X Y)(1X Y). . . puisque   Y YX X 1 ixixix1+2x2+∙∙∙x1+x2+∙∙∙ =X Y=X Y i 1X Y i>1i>1xi>0x1,x2,...>0 etlas´erieg´en´eratricede(pn) s’obtient en faisantYlapr´ec´=1dansdeneet: 1 .(3) 2 3 (1X)(1X)(1X). . . 2.3Structuresde´composables Lescoecientsdesse´riesge´ne´ratrices(1),(2),(3)donnentlenombredede´compositionsdunentier donn´e,respectantunecertainestructure.Dunemani`erege´n´erale,siAest une structure pour laquelle estde´nieunefonctiontailletne(sii`ere)etanest le nombre d’objets de taillende cette structure, la P n se´riege´ne´ratriceA(X) =anXs’appellenemu´dtne´ardeA. n Il arrive qu’une structure soitmpcoaboslee´desurctrustdeirrt,cste`--aideruqopniusselobtenir`apa plussimplesenappliquantdesconstructionscombinatoirescomme:r´eunion,produitcarte´sien,s´equence (´eventuellementvide).Pourcestroistypesdeconstruction,onpeutappliquerletableaudecorrespon-dances suivant (cf [2], p.111) : structurede´num´erant ABA(X) +B(X) A×BA(X)B(X) 1 Se´q.deA 1A(X) Pour illustrer ceci, reprenons l’exemple 2.1 en nommant les structures :A,sim=´dsipoomecdeenonti se´rieuxetformidables,D=ce´d,senonmidepoomtisiSmoopisit=´dceieux,onens´erFnoit=idsopmoce´ en formidables. Alors il est clair queA=D×S×F. D’autre part,D(resp.S,F)tues´seneuqeecn dede´compositionsenundemi(resp.uns´erieux,unformidable).Nommons:D1posiecomention´d= un demi,S1ux,ree=inu´smnooonpei´sdciteF1posiecom=d´oprunssoisn´etd,elebadimrofnunenoit toutescesde´compositionslafonctiontaillesuL.tbnesertsdequaresoelitomenedbrete´tlanmmoc de´num´erantscorrespondantssontalors: 2 4 D1(X) =X , S1(X) =FX ,1(X) =X etlesre`glesci-dessusconduisent`a: 1 11 11 1 D(X=) =, S(X=) =, F(X=) = 2 4 1D1(X) 1X1S1(X) 1X1F1(X) 1X puis`alaformule(1)pre´c´edente: 1 1 11 A(X) =× ×=. 2 4 D1(X)S1(X)F1(X) (1X)(1X)(1X)
3
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi

suivant