Product of Generating Functions + Complexity

[inviteec9c3db3]

Bonjour,

Je bloque totalement sur cette question de fonction génératrice et complixité:



J'ai d'abord commencé par écrire explicitement le produit de fonctions génératrices pour pouvoir l'encadrer par la suite:

F(x) = 1/(1-x) * 1/(2-x)² *...* 1/(5-x)⁵

Je pense qu'il faut écrire cette expression sous la forme: 1 + x + x² + x³ + ...
En sachant que 1/(1-ax) = 1 + ax + a²x² +a³x³ + ...

Ceci m'aiderait à pouvoir encadrer la fonction génératrice initiale pour trouver teta.
Je n'est rien trouvé concernant la facon de faire cela, peut être suis je sur la mauvaise piste?

Merci pour toute aide.
-----

[invite179e6258]

cet énoncé est un peu sybillin : qu'est-ce qu'une "theta-approximation" ? est-ce que tu cherches un équivalent en x->0 ?

[inviteec9c3db3]

Une teta approximation est une fonction f(x) qui respecte la relation: C|f(x)| <= F(x) <= C|f(x)|

[invite179e6258]

avec des C différents à gauche et à droite j'imagine, et f qui doit appartenir à une certaine classe de fonctions (polynômiales?)

[A voir en vidéo sur Futura]

[inviteec9c3db3]

Oui c'est bien des C différents et f peut appartenir à n'importe quelle classe de fonctions. La plupart du temps c'est une fonction de la même classe que F(x) différant à quelques détails près.