Examen du cours de “Combinatoire algébrique, énumérative et fonctionnelle”. Madacascar 2007-2008.

Seules les notes manuscrites, le support de cours et la calculette sont autorisés. Le candidat s’efforcera de rédiger lisiblement et avec soin sa copie. En particulier, les réponses doivent être justifiées et les résultats clairement dégagés. Le sujet est (en principe) trop long pour le temps imparti, il est donc conseillé de traiter en priorité les questions que l’on sait faire en en indiquant clairement la référence.

I) Question de Cours:

1) Les séries sont des fonctions, donner le cadre général de leur définition.

2) Rappeler les deux formules de produit (Hadamard et Cauchy) et leurs propriétés.

3) a) Donner les formes des trois types d’expression des fonctions rationnelles de ℂ[[z]] (rat, coeff, rec).

b) Décrire comment on passe de l’une à l’autre.

c) Qu’est-ce qu’une famille (de séries) sommable ? Application. — Montrer que ((z+z^{2})^{n})_{n∈ℕ} est sommable. En déduire une expression de F_{n} (nième nombre de Fibonacci) sous forme d’une somme de binomiaux. II) Exercices A) 1) Développer les séries suivantes :

a) \frac{1}{1−z^{3}} b) \frac{1−z}{1+z} c) \frac{1−\sqrt{1+z^{2}}}{z}

2) Sommer :

a) ∑_{n≥0} nz^{3}n b) ∑_{n≥0} n(n − 1)z^{n} c) ∑_{n≥0} n^{2}z^{n}

B) On rappelle que le produit de Hadamard de deux séries A = ∑_{n≥0} a_{n}z^{n} et B = ∑_{n≥0} b_{n}z^{n} est défini par A ⊙ B = ∑_{n≥0} a_{n}b_{n}z^{n}.

1) Soit ϕ(z) = ∑_{n∈ℕ} a_{n}z^{n}. Pour quels nombres complexes α ∈ ℂ les égalités suivantes sont-elles vraies ?

a) \frac{1}{1−z^{5}} ⊙ ϕ(z) = \frac{1}{5}(ϕ(z) + ϕ(αz) + ϕ(α^{2}z) + ϕ(α^{3}z) + ϕ(α^{4}z)) b) \frac{1}{1−αz} ⊙ = ϕ(αz)

2) Application. — Calculer

a) \frac{1}{1−z^{3}} ⊙ ( ∑_{n∈ℕ} F_{n}z^{n}) b) \frac{1}{1+z} ⊙ ( ∑_{n∈ℕ} F_{n}z^{n})

3) Donner une règle dans le style de (A)1)a) pour \frac{z}{1−z^{4}} ⊙ ϕ(z) et en déduire

\frac{z}{1−z^{4}} ⊙ ( ∑_{n∈ℕ} F_{n}z^{n}). B) 1) Les nombres de Fibonacci sont donnés par la récurrence

F_{0} = 0; F_{1} = 1; F_{n+2} = F_{n} + F_{n+1}  (1)

a) Redémontrer que la série génératrice des nombres de Fibonacci est S(z) = \frac{z}{1−z−z^{2}} .

b) Décomposer la fraction précédente en éléments simples et en déduire (justifier) que

F_{n} = \frac{1}{\sqrt{5}}(ϕ^{n} − ϕ̄^{n})  (2)

c) Déduire du (b) une expression, sous forme de fraction rationnelle, de la série ∑_{n=0}^{∞} F_{n}^{2}z^{n}.

Indication: On évitera au maximum les calculs à l’aide des relations ϕϕ̄ = −1 et ϕ + ϕ̄ = 1.

d) En calculant F_{n+3}^{2} − F_{n+2}^{2} trouver une relation de récurrence entre les a_{n} = F_{n}^{2}. Recalculer la fraction rationnelle ∑_{n} F_{n}^{2}z^{n}.

2) On considère une suite satisfaisant une relation de récurrence d’ordre deux

x_{n+2} = a_{0}x_{n} + a_{1}x_{n+1}.

a) En s’inspirant de la question (4d) et en développant x_{n+3}^{2} − a_{0}x_{n+2}^{2}, trouver une relation de récurrence satisfaite par la suite x_{n}^{2}.

b) Donner la fraction rationnelle ∑_{n=0}^{∞}(x_{n})^{2}z^{n} sous la forme \frac{P (z)}{1−zQ(z)}; P, Q ∈ C[z].

c) Montrer que ((zQ(z))^{n})_{n∈ℕ} est sommable et en déduire une nouvelle expression de x_{n}^{2}.

3) Soit α = 1 + \sqrt{2}; ᾱ = 1 − \sqrt{2}.

a) Donner une relation du type

α^{2} = uα + v , u, v ∈ ℤ  (3)

b) Les coefficients u, v ∈ ℤ sont-ils uniques ?

c) Montrer, en utilisant (??), que la suite g_{n} = \frac{1}{\sqrt{2}}(α^{n} − ᾱ^{n}) vérifie

g_{n+2} = g_{n} + 2g_{n+1}.

et en déduire que g_{n} ∈ ℕ.

d) À l’aide de (2), calculer

S_{1} = ∑_{n=0}^{∞} g_{n}z^{n} et S_{2} = ∑_{n=0}^{∞} g_{n}^{2}z^{n}

III. Problème On construit une suite de ℤ^{2} par le procédé suivant

• ← • ← • ← • ← •
↓  ↑
•  • ← • ← •  •
↓  ↓  ↑  ↑
•  ∘ → •  •
↓  ↑
• → • → • → •

c’est une suite de couples (c_{n}), le point de départ (∘) étant l’origine (c_{0} = (0, 0)).

a) Soit d_{1}(n), l’indice du n^{ième} passage de c_{n} sur la première demi-diagonale x = y; x > 0. On a

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 \\ d_{1}(n) & 2 & 12 & 30 & 56 & 90 \end{matrix}

montrer que a_{1}(n) = d_{1}(n + 1) − d_{1}(n) vérifie a_{1}(n + 1) − a_{1}(n) = 8 (on pourra donner une preuve “picturale”, sinon il est conseillé d’admettre le résultat et de continuer).

b) Déduire de la question précédente que a_{1}(n) = 8n + 2.

c) Donner les séries génératrices ∑_{n≥0} a_{1}(n)z^{n} puis ∑_{n≥0} d_{1}(n)z^{n}.

d) Déduire de ce qui précède que d_{1}(n) = (2n)^{2} − 2n.

3) Montrer que les indices du n^{ième} passage de c_{n} sur 3 autres demi-diagonales sont respectivement (en tournant dans le sens trigonométrique)

d_{2}(n) = (2n)^{2}; d_{3}(n) = (2n)^{2} + 2n; d_{4}(n) = (2n)^{2} + 4n = (2n + 1)^{2} − 1

donner les séries génératrices (en z) de d_{i}; i = 1..4.

4) Selon la position de k par rapport à d_{1}(n) < d_{2}(n) < d_{3}(n) < d_{4}(n) donner la valeur de c_{k} = (x_{k}, y_{k}) et montrer que k → c_{k} est une bijection entre ℕ et ℤ^{2}.

3) Reprendre le problème précédent avec le bijection ℕ → ℕ^{2} définie par le diagramme suivant :

•
↑ ↘
•  •
↖  ↘
•  •  •
↑ ↘  ↖  ↘
•  •  •  •
↖  ↘  ↖
∘ → •  • → •