Eléments de combinatoire by Daniel Krob

By Daniel Krob

Show description

Read Online or Download Eléments de combinatoire PDF

Similar french_1 books

Hélène Cixous: Writing the Feminine

Born in Algeria in 1937, Hélène Cixous accomplished international reputation for her brief tales, feedback, and fictionalized autobiography (Dedans, 1969). Her paintings quick turned arguable since it frankly validated a contrast among female and male writing. Her literary experiments and her conclusions make her probably the most stimulating and such a lot elusive feminist theorists of our time.

Blindés en Normandie: Les Britanniques

Blindes en Normandie: Les Britanniques

Extra resources for Eléments de combinatoire

Example text

8 Soit L un langage algebrique engendre par une grammaire non am- bigue. La serie generatrice d(L; t) des distributions de longueur du langage L est alors une serie algebrique sur Z(t). Autrement dit, il existe des polyn^omes (pi (t))i ;N dans Zt] tels que l'on ait =0 N X i pi(t) d(L; t)i = 0 : =0 Lorsque l'on etudie la serie d(L; t) associee a un langage algebrique, la question principale sera souvent de reussir a calculer son polyn^ome minimal. Nous allons terminer par un exemple de ce type de probleme.

La proposition precedente montre en e et que c'est toujours possible. 3 (nous ne redonnons pas ici les hypotheses sous lesquelles ils interviennent). Ces expressions recursives permettent donc clairement de calculer d(L; t) des que l'on connait une expression rationnelle non ambigue pour L. Elles montrent aussi non moins clairement que d(L; t) est une fraction rationnelle de Z(t). 5 Considerons le langage rationnel L forme des mots sur l'alphabet A = fa; bg qui ont un nombre pair de a. Il est facile de veri er que E = (b + ab a) est une expression rationnelle non ambigue qui represente L.

1 1 48 Chapitre 1. Elements de combinatoire enumerative et bijective Distributions de longueur d'un langage algebrique non ambigu Soit maintenant G une grammaire non ambigue. Notons V ; : : :; Vn les di erentes variables de G (de sorte que la variable initiale de G soit S = V ). Si Vi ! wj;i (avec j dans 1; ni]) forme l'ensemble des regles de G faisant intervenir la variable Vi, ecrivons alors les regles de G sous la forme condensee : Vi ! w ;i + : : : + wni ;i ; pour i variant de 1 a n. Considerons alors le systeme d'equations algebriques (SA) a coe cients dans N t] de ni par ni X (wj;i) Xi = 4 1 1 1 j =1 ou designe ici le morphisme de mono des qui envoie chaque lettre a 2 A sur t et chaque variable Vi sur la variable commutative Xi .

Download PDF sample

Rated 4.67 of 5 – based on 49 votes