Home

cours

1. num rant est donc P 1 X j La s rie g n ratrice de toutes les dispositions possibles est donc le polyn me n variables P G x 4 1 lt i j lt n R soudre le probl me pos revient d velopper P et ne garder que les bons mon mes Agr gation de math matiques option C alg bre et calcul formel Polyn mes multivari s et combinatoire 3 2 Mod lisation d apr s 2 p 113 Introduisons 4n 2 ind termin es cj dx ex pour repr senter respectivement les lignes colonnes diagonales montantes et diagonales descendantes num rot es dans l ordre sch matis sur la figure 2 pour n 4 C1 C2 C3 Ca d h d d A LEA l e5 N h S Ve B a Ne A Se 7 Z Xe d a a a F1G 2 Mod lisation pour n 4 Dans 4 on remplace X j par le mon me 4 c di j 1 i j n qui code la ligne la colonne et les deux diagonales passant par la case i j Chaque terme du d veloppement de P est alors un mon me en les l i cj dk en Par exemple les deux configurations de la figure 1 sont repr sent es par le m me mon me licod2e3 lcad5e2 l3C1d3e6 laczd es Les bons mon mes sont alors ceux qui contiennent les variables 1 h 1 n chaque ligne ou colonne est occup e au moins une fois et qui ne contiennent aucune variable avec un exposant gt 1 chaque ligne colonne ou diagonale n est occup e qu une seule fois Le nombre de solutions est la somme des coeffici
2. coefficient du degr souhait avec coeff puis recommencer avec une autre variable etc 2 D nombrement 2 1 Premier exemple De combien de fa ons peut on vider un f t de bi re de 100 litres en utilisant un demi r cipient d un quart de litre un s rieux un demi litre et un formidable un litre sans tenir compte de l ordre des op rations Pour n gt 0 notons un le nombre de fa ons de vider un f t de n quarts de litres Alors un est le nombre de triplets d entiers naturels d s f v rifiant d 2s 4f n donc Un est le coefficient en X dans le d veloppement de U X 1 X X X X NUE XL X8 1 X 1 X2 1 X4 0 On trouve u400 10201 voir la feuille d illustration section 3 On y verra galement un exemple d utilisation de la fonction rgf findrecur qui permet de deviner une r currence lin aire ainsi que le calcul de l expression de un d abord sans rsolve puis avec 2 2 Deuxi me exemple partitions d entiers Soit n un entier naturel gt 1 Une partition de n est une repr sentation de n en somme d entiers gt 1 qu on appelle les sommants de la partition cf 1 p 104 Soient pn le nombre de partitions de n et Pam le nombre de partitions de n en m sommants On a par exemple 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 donc ps 7 p51 P5 4 D5 5 1 ps 2 D5 3 2 Si on note x le nombre de sommants gaux i il est clair que Ag
3. 1 le nombre b d arbres binaires n feuilles appel n nombre de Catalan cf 2 p 112 On peut montrer cf 1 p 66 ou 3 p 524 que nel l n n i 2 5 D compositions de Lagrange Voir la feuille d illustration section 4 Etant donn un entier naturel n il s agit de trouver le nombre qn de quadruplets a b c d d entiers gt 0 tels que a b c d n cf 2 p 112 La structure de ces quadruplets est gale x x x k gt 0 Ek est la structure r union des carr s de l entier k En prenant pour taille d un entier sa valeur il vient C X X 4 donc qn est le coefficient en X dans gt X r voir la feuille d illustration section 5 k gt 0 3 Probl me des reines Il s agit de disposer n reines sur un chiquier n x n de mani re ce qu aucune reine ne soit en prise avec une autre Combien y a t il de solutions Gauss a montr que pour n 8 il y en a 92 Pour n 4 il y a en a deux repr sent es sur la figure 1 FIG 1 Les deux solutions pour n 4 3 1 Principe Envisageons toutes les mani res de disposer des reines sur un chiquier n x n Une disposition de reines est une structure d composable produit cart sien des n dispositions individuelles sur chacune des cases Pour une case donn e i j il y a deux dispositions possibles pas de reine ou une reine En prenant pour fonction taille le nombre de reines le d
4. En X 107 1 Sn k 9n k 7 k 0 Pour n gt 1 on a la formule de r currence 9 Sn k S 10 Sn 1 k r T In 1 k r 8 r 0 Notons G et S les s ries g n ratrices deux variables G X Y X gna X Y S X Y X sna XY n gt 1 n gt 1 k20 k20 et posons galement 9 9 VY X Y WY rY r 0 r 0 Le coefficient en Y dans 1 Y Y Y est le nombre de n uplets de chiffres dont la somme vaut k Donc 2 nan VOIX G X Y 27 X VOX 9 De plus X s XY XW Y 10 k20 En sommant pour n gt 1 k gt 0 et avec 8 9 et 10 il vient S X Y XW Y 10XV Y S X Y XW Y G X XW Y XW Y X Y 1 X Y _ EWP XWM GA _ ywy GAY 1 10XV Y 1 10XV Y E XW Y A XV A 10XV Y S X Y et G X Y une fois calcul es la formule 7 donne Ep In En 10 1 5 coefficient en X YF dans S X Y coefficient en X YF dans G X Y k 0 D o le programme de la feuille d illustration section 7 R f rences 1 L Comtet Analyse combinatoire P U F 1970 2 C Gomez B Salvy P Zimmermann Calcul formel mode d emploi Masson 1995 3 C Froidevaux M C Gaudel M Soria Types de donn es et algorithmes Ediscience 1993 4 http en wikipedia org wiki Generating function
5. POLYNOMES MULTIVARIES ET COMBINATOIRE O Marguin 18 mai 2011 Par son efficacit le calcul formel sur les polyn mes multivari s permet de r soudre de fa on spectaculaire certains probl mes combinatoires Avant d en voir des exemples nous rappelons quelques propri t s des s ries g n ratrices Ce chapitre est accompagn d une feuille d illustrations en Maple 1 S ries g n ratrices 1 1 Cas d une variable Soit u un n gt 0 une suite d l ments d un corps K dans tout ce qui suit K sera le corps des rationnels Nous noterons U X sa s rie g n ratrice c est dire la s rie formelle de X X d finie par 00 GONE un X n 0 Par exemple la suite constante gale 1 a pour s rie g n ratrice 1 1 X X E 1 X 1 2 R currences lin aires Supposons que la suite u v rifie une r currence lin aire d ordre k de la forme Un Q1 Un 1 a2 Un 2 akUn k nk Alors U v rifie U X P X U X a X a2 X ag X o P X est un polyn me de degr k 1 d pendant des a et des valeurs initiales uo u1 ug 1 cf 3 p 542 Ainsi P X 1 a X a2 X2 ak XF Par exemple la s rie g n ratrice F X de la suite de Fibonacci d finie par fo 0 f 1 et fn fn 1 fn 2 pour n gt 2 v rifie quation U X X R X S 2 1 X X2 ce qui permet avec Maple de calculer son n terme tr s rapidement Les deux fon
6. ctions cl s sont series et coeff Rappelons que le terme g n ral s obtient en d composant F X en l ments simples AAS AG nae f g 7 Maple poss de galement la fonction rsolve qui r sout les r currences lin aires voir feuille d illustration section 1 o y est le nombre d Or d o Remarque Dans la feuille d illustration section 2 il y a un exemple de r currence polyn miale tir de 2 p 177 o on utilise la fonction guessgf pour trouver la s rie g n ratrice Agr gation de math matiques option C alg bre et calcul formel Polyn mes multivari s et combinatoire 1 3 Cas de plusieurs variables 2 a est une suite multi indic e sa s rie g n ratrice U X1 X est la s rie formelle de K LX Xx d finie par DORE Sr AU SEA Par exemple cf 1 p 58 et p 99 la suite double des coefficients du bin me C a pour s rie g n ratrice gt a nra n a n gt 0 la s rie g n ratrice du minimum de k entiers u i min i est donn e par RATE Ras U X1 Xk X X2 1 Xk 1 X1Xo Xk La fonction mtaylor de Maple d veloppement de Taylor plusieurs variables permet d obtenir les premiers termes d une s rie g n ratrice multivari e Si l on cherche un coefficient bien pr cis il est souvent plus efficace de d velopper la s rie g n ratrice par rapport l une des variables avec series extraire le
7. ents des bons mon mes dans le d veloppement de P G cdi 1e 5 1 lt i j lt n Mais le d veloppement brutal de P n est pas envisageable car il comporte 2 termes c est dire de l ordre de 10 pour n 8 3 3 Mise en uvre Pour viter l explosion combinatoire on extrait successivement de 5 les coefficients de 41 l2 Zn Le calcul est ramen la recherche du coefficient de c1C2 ch dans P X G 6 i 1 j 1 On extrait les coefficients de c1 C2 Cn et il reste liminer les mauvais mon mes voir la feuille d illustration section 6 Le probl me des reines est r solu en cinq lignes de programme La feuille d illustration contient aussi une proc dure plus classique bas e sur un autre algorithme backtracking 4 Somme des entiers n balanc s 4 1 Enonc Nous dirons qu un entier naturel est n balanc s il comporte 2n chiffres d cimaux compris entre 0 et 9 et si la somme de ses n premiers chiffres est gale celle de ses n derniers chiffres par exemple 761428 est 3 balanc de m me que 6123 puisqu il s crit 006123 Il s agit de calculer la somme En de tous les entiers n balanc s cf 4 Agr gation de math matiques option C alg bre et calcul formel Polyn mes multivari s et combinatoire 4 2 Solution Soient gn k le nombre des entiers n chiffres dont la somme des chiffres vaut k et Sn la somme de ces entiers Par d finition 9n
8. num rant AUB A X B X A x B A X B X 1 1 A X S q de 2 Pour illustrer ceci reprenons lexemple 2 1 en nommant les structures A d composition en demis s rieux et formidables D d composition en demis d composition en s rieux d composition en formidables Alors il est clair que A D x G x 3 D autre part D resp F est une s quence de d compositions en un demi resp un s rieux un formidable Nommons D d composition en un demi G d composition en un s rieux d composition en un formidable et d finissons pour toutes ces d compositions la fonction taille comme tant le nombre de quarts de litres obtenus Les d num rants correspondants sont alors Di X X S1 X X F X X et les r gles ci dessus conduisent 1 1 1 1 1 1 D X S X F X 9 1 D X Lex x sA e 5 1 A X 1 X puis la formule 1 pr c dente e EE E E 1 D X XV AX 0 X 0 X X4 Agr gation de math matiques option C alg bre et calcul formel Polyn mes multivari s et combinatoire 2 4 Arbres binaires La structure B d arbre binaire est d composable de fa on r cursive B FU B x B o est la structure feuille En prenant pour fonction taille le nombre de feuilles il vient B X X B X d o en r solvant l quation du second degr le d num rant B X la v1 2 On en tire pour n gt
9. r gation de math matiques option C alg bre et calcul formel Polyn mes multivari s et combinatoire la donn e d une partition de n quivaut la donn e d une solution en nombres entiers x gt 0 de Ti 2 2 NTn N si en plus on veut m sommants il faut ajouter la condition tittat Tn m Par cons quent la s rie g n ratrice de Dm est P X Y 1 5 Dam X YT ISm lt n 1 NS Te GTS e 2 puisque 1 iTi V Ti x t2r2 yri r2 ie a a De i gt l i gt l x gt 0 1 2 20 et la s rie g n ratrice de p s obtient en faisant Y 1 dans la pr c dente 1 a X0 XU X3 2 3 Structures d composables Les coefficients des s ries g n ratrices 1 2 3 donnent le nombre de d compositions d un entier donn respectant une certaine structure D une mani re g n rale si est une structure pour laquelle est d finie une fonction taille enti re et si a est le nombre d objets de taille n de cette structure la s rie g n ratrice A X an X s appelle d num rant de A Il arrive qu une structure soit d composable c est dire qu on puisse l obtenir partir de structures plus simples en appliquant des constructions combinatoires comme r union produit cart sien s quence ventuellement vide Pour ces trois types de construction on peut appliquer le tableau de correspon dances suivant cf 2 p 111 structure d

cours

Contents

Download Pdf Manuals

Related Search

Related Contents