DM2 : Problème des anniversaires, Séries génératrices, Arbres aléatoires

Maths Discrètes : DM 2

Énoncé

http://younesse.net/Maths-discretes/DM2/

Younesse Kaddar

EX 1

1.

Soient $p, r$ des entiers naturels non nuls.

On pose $E ≝ ⟦1, pr⟧$, et note $𝒫$ l’ensemble des partitions de $E$.

Sans perte de généralité : on va calculer $\vert 𝒫 \vert$.

On appelle

“partition ordonnée” en $r$ parties de cardinal $p$ de $E$ :

un $r$-uplet $(E_1, ⋯, E_r)⊆E^r$ tel que :

• $\bigsqcup\limits_{i=1}^r E_i = E$
• $∀i≠j∈⟦1,r⟧, E_i ∩ E_j = ∅$
• $∀i∈⟦1,r⟧, \vert E_i \vert = p$

On note $𝒫_o$ l’ensemble des partitions ordonnées de $E$.

Méthode 1 : Plus concise et expéditive

Étape 1 : Montrons que $\vert 𝒫_o \vert = \frac{(rp)!}{(p!)^r}$

$\vert 𝒫_o \vert$ est le nombre d’orbites $\vert 𝕾_{rp}/𝕾_{p}^r\vert$ de $𝕾_{rp}$ sous l’action de $𝕾_{p}^r$, définie par :

\[∀(𝛾_1, ⋯, 𝛾_r)∈𝕾_p^r, ∀𝜎∈𝕾_{rp}, (𝛾_1, ⋯, 𝛾_r)\cdot 𝜎 = 𝜎'\]

où

\[∀i∈⟦1,p⟧, ∀j∈⟦1,r⟧, \\ 𝜎'(i+p(j-1)) ≝ 𝜎(p(j-1)+𝛾_j(i))\]

Or, pour tout $(𝛾_1, ⋯, 𝛾_r)∈𝕾_p^r$, le fixateur $Fix((𝛾_1, ⋯, 𝛾_r))$ de $(𝛾_1, ⋯, 𝛾_r)$ vaut :

• $𝕾_{rp}$ si $(𝛾_1, ⋯, 𝛾_r) = (id, ⋯, id)$
• $∅$ sinon

(l’action est dite libre)

Donc, d’après la formule (qui n’est pas) de Burnside :

\[\vert 𝒫_o \vert=\vert 𝕾_{rp}/𝕾_{p}^r\vert = \frac{1}{\vert 𝕾_{p}^r \vert} \sum_{𝛾∈𝕾_{p}^r} \vert Fix(𝛾) \vert \\ = \frac{(rp)!}{(p!)^r}\]

Étape 2 : Montrons que $\vert 𝒫 \vert = \frac{\vert 𝒫_o \vert}{r!}$

De manière analogue, $\vert 𝒫 \vert$ est le nombre d’orbites $\vert 𝒫_o/𝕾_{r}\vert$ de $𝒫_o$ sous l’action de $𝕾_{r}$, définie par :

\[∀𝜎∈𝕾_r, ∀(E'_1, ⋯, E'_r)∈𝒫_o, \\ 𝜎\cdot (E'_1, ⋯, E'_r) ≝ (E'_{𝜎(1)}, ⋯, E'_{𝜎(r)})\]

Or, pour toute $𝜎∈𝕾_r$, le fixateur $Fix(𝜎)$ de $𝜎$ vaut :

• $𝒫_o$ si $𝜎=id$
• $∅$ sinon

Donc, d’après la formule (qui n’est pas) de Burnside :

\[\vert 𝒫 \vert= \vert 𝒫_o/𝕾_{r}\vert = \frac{1}{\vert 𝕾_{r} \vert} \sum_{𝜎∈𝕾_r} \vert Fix(𝜎) \vert \\ = \frac{\vert 𝒫_o \vert}{r!} = \frac{(rp)!}{r!(p!)^r}\]

Méthode 2 : Plus détaillée

Étape 1 : Montrons que $\vert 𝒫_o \vert = \frac{(rp)!}{(p!)^r}$

La fonction

\[𝜑 ≝ \begin{cases} 𝕾_{rp} ⟶ 𝒫_o \\ 𝜎 \mapsto \Big(\lbrace 𝜎(1), ⋯, 𝜎(6) \rbrace, ⋯, \lbrace 𝜎(rp-5), ⋯, 𝜎(rp) \rbrace \Big) \end{cases}\]

est surjective.

---

En effet :

Pour toute “partition ordonnée” $\Big(E_1 ≝ \lbrace e_i^{(1)} \rbrace_{i∈⟦1,p⟧}, ⋯, E_r ≝ \lbrace e_i^{(r)} \rbrace_{i∈⟦1,p⟧}\Big)$,

\[(E_1, ⋯, E_r) = 𝜑(𝜎)\]

où $𝜎∈𝕾_{rp}$ est telle que $∀i∈⟦1,p⟧, ∀j∈⟦1,r⟧$ :

\[𝜎(i+p(j-1)) ≝ e_i^{(j)}\]

---

On note $\sim$ la relation d’équivalence

\[𝜎 \sim 𝜎' ⟺ 𝜑(𝜎) = 𝜑(𝜎')\]

La fonction $\widetilde{𝜑} : 𝕾_{rp}/\sim ⟶ 𝒫_o$ est injective, donc

\[\vert 𝕾_{rp}/\sim \vert = \vert 𝒫_o \vert \hspace{1em}⊛\]

Or, pour toutes $𝜎, 𝜎’∈𝕾_{rp}$,

\[\begin{align*} & \hspace{1em} 𝜎 \sim 𝜎' \\ ⟺ & \hspace{1em} 𝜑(𝜎) = 𝜑(𝜎') \\ ⟺ & \hspace{1em} \Big(\lbrace 𝜎(1), ⋯, 𝜎(6) \rbrace, ⋯, \lbrace 𝜎(rp-5), ⋯, 𝜎(rp) \rbrace \Big) = \Big(\lbrace 𝜎'(1), ⋯, 𝜎'(6) \rbrace, ⋯, \lbrace 𝜎'(rp-5), ⋯, 𝜎'(rp) \rbrace \Big) \\ \end{align*}\]

Donc pour toute $𝜎∈𝕾_{rp}$, on remarque que la classe d’équivalence $\overline{𝜎}$ de $𝜎$ pour la relation d’équivalence $\sim$ est l’orbite $𝜔_𝜎$ de $𝜎$ pour l’action du groupe $G ≝ 𝕾_p^r$ sur $𝕾_{rp}$ définie par :

\[∀(𝛾_1, ⋯, 𝛾_r)∈𝕾_p^r, ∀𝜎∈𝕾_{rp}, (𝛾_1, ⋯, 𝛾_r)\cdot 𝜎 = 𝜎'\]

où

\[∀i∈⟦1,p⟧, ∀j∈⟦1,r⟧, \\ 𝜎'(i+p(j-1)) ≝ 𝜎(p(j-1)+𝛾_j(i))\]

Comme, pour toute $𝜎∈𝕾_{rp}$, le stabilisateur $H_𝜎$ de $𝜎$ est de cardinal 1 (il vaut $\lbrace (id, \ldots, id) \rbrace$) :

\[\vert \overline{𝜎} \vert = \vert 𝜔_𝜎 \vert = \frac{\vert 𝕾_p^r \vert}{\vert H_𝜎 \vert} = \vert 𝕾_p^r \vert = (p!)^r\]

Donc, en notant $k ≝ (p!)^r$ le cardinal des classes d’équivalence pour $\sim$, il vient, par $⊛$ :

\[\vert 𝒫_o \vert = \vert 𝕾_{rp}/\sim \vert = \frac{\vert 𝕾_{rp} \vert}{k} = \frac{(rp)!}{(p!)^r}\]

Étape 2 : Montrons que $\vert 𝒫 \vert = \frac{\vert 𝒫_o \vert}{r!}$

De manière analogue, la fonction

\[𝜓 ≝ \begin{cases} 𝒫_o ⟶ 𝒫 \\ (E_1, ⋯, E_r) \mapsto \lbrace E_1, ⋯, E_r \rbrace \end{cases}\]

est trivialement surjective, et en notant $\sim$ la relation d’équivalence

\[(E_1, ⋯, E_r) \sim (E'_1, ⋯, E'_r) ⟺ 𝜓((E_1, ⋯, E_r)) = 𝜓((E'_1, ⋯, E'_r))\]

La fonction $\widetilde{𝜓} : 𝒫_o/\sim ⟶ 𝒫$ est injective. donc

\[\vert 𝕾_{rp}/\sim \vert = \vert 𝒫_o \vert\]

Or, pour toute “partition ordonnée” $(E_1, ⋯, E_r)$, on remarque que la classe d’équivalence $\overline{(E_1, ⋯, E_r)}$ pour la relation $\sim$ est l’orbite $𝜔_{(E_1, ⋯, E_r)}$ de $(E_1, ⋯, E_r)$ pour l’action du groupe $G ≝ 𝕾_r$ sur $𝒫_o$ définie par :

\[∀𝜎∈𝕾_r, ∀(E'_1, ⋯, E'_r)∈𝒫_o, \\ 𝜎\cdot (E'_1, ⋯, E'_r) ≝ (E'_{𝜎(1)}, ⋯, E'_{𝜎(r)})\]

et comme les stabilisateurs sont de cardinal 1 :

\[\vert \overline{(E_1, ⋯, E_r)} \vert = \vert 𝜔_{(E_1, ⋯, E_r)} \vert = \vert 𝕾_r \vert = r!\]

Il vient donc que :

\[\vert 𝒫 \vert = \vert 𝒫_o/\sim \vert = \frac{\vert 𝒫_o \vert}{r!} = \frac{(rp)!}{r!(p!)^r}\]

Donc le nombre de partitions d’un ensemble de cardinal $rp$ en $r$ parties de cardinal $p$ est

\[\frac{(rp)!}{r!(p!)^r}\]

2.

Par récurrence sur $s≥1$ : Si $r_1, …, r_s$ sont des entiers naturels tels que $N = \sum\limits_{i=1}^s i r_i$, le nombre de partitions d’un ensemble de cardinal $N$ en $r_1$ parties de cardinal $1$, …, $r_s$ parties de cardinal $s$ est :

\[\frac{N!}{\prod_{i=1}^s r_i ! \prod_{i=1}^s(i!)^{r_i}}\]

• Initialisation : Pour $s=1$, c’est résultat établi en Q1.

• Hérédité : Si $s≥2$ : soient $r_1, …, r_s$ sont des entiers naturels tels que $N = \sum\limits_{i=1}^s i r_i$.

  Sans perte de généralité, dénombrons le nombre de partitions de $⟦1,N⟧$ en $r_1$ parties de cardinal $1$, …, $r_s$ parties de cardinal $s$.

  Pour une partition de cette forme, on choisit l’ensemble $E$ des éléments appartenant aux $r_s$ parties de cardinal $s$ $\Big(\binom{N}{s r_s} = \frac{N(N-1)⋯(N-s r_s +1)}{(s r_s)!} \text{ choix} \Big)$, puis une partition de $E$ en $r_s$ parties de cardinal $s$ $\Big(\frac{(s r_s)!}{r_s!(s!)^{r_s}} \text{ choix (par Q1)} \Big)$, puis une partition de $⟦1,N⟧\backslash E$ en $r_1$ parties de cardinal $1$, …, $r_{s-1}$ parties de cardinal $s-1$ $\Big(\frac{(N-s r_s)!}{\prod_{i=1}^{s-1} r_i ! \prod_{i=1}^{s-1}(i!)^{r_i}} \text{ choix (par hypothèse de récurrence)} \Big)$

  Et réciproquement, toute partition est déterminée de manière unique par ces choix.

  Il vient donc qu’il y a :

  \[\frac{N(N-1)⋯(N-s r_s +1)}{(s r_s)!} × \frac{(s r_s)!}{r_s!(s!)^{r_s}} × \frac{(N-s r_s)!}{\prod_{i=1}^{s-1} r_i ! \prod_{i=1}^{s-1}(i!)^{r_i}} = \frac{N!}{\prod_{i=1}^s r_i ! \prod_{i=1}^s(i!)^{r_i}}\]

  partitions de la forme souhaitée : le résultat est acquis.

3.

\[⟦1,n⟧ = \bigsqcup\limits_{u∈⟦1,N⟧} I_u^{\mathbf{x}}\]

Donc

\[\begin{align*} n & = \vert ⟦1,n⟧ \vert \\ & = \sum\limits_{u∈⟦1,N⟧} \vert I_u^{\mathbf{x}} \vert \\ & = \sum\limits_{j∈⟦1,n⟧} \sum\limits_{\substack{u∈⟦1,N⟧ \\ u \text{ est de multiplicité } j \text{ dans } \mathbf{x}}} \vert \underbrace{I_u^{\mathbf{x}}}_{= \, j} \vert \\ & = \sum\limits_{j∈⟦1,n⟧} j \sum\limits_{\substack{u∈⟦1,N⟧ \\ u \text{ est de multiplicité } j \text{ dans } \mathbf{x}}} 1 \\ & = \sum\limits_{j∈⟦1,n⟧} j n_j^{\mathbf{x}} \\ \end{align*}\]

On a montré que :

\[n= \sum\limits_{j∈⟦1,n⟧} j n_j^{\mathbf{x}}\]

4.

\[n_j^{\mathbf{x}} = \vert \lbrace I_u^{\mathbf{x}} ∈ {\cal P}^{\mathbf{x}} \, \, \vert \, \, Card(I_u^{\mathbf{x}}) = j \rbrace \vert\]

par définition de $n_j^{\mathbf{x}}$

ou, si on note $Card_{ \mid {\cal P}^{\mathbf{x}} }$ la fonction

\[Card_{ \mid {\cal P}^{\mathbf{x}} } : {\cal P}^{\mathbf{x}} ⟶ ℕ, I_u \mapsto \vert I_u \vert\]

\[n_j^{\mathbf{x}} = \big\vert Card_{ \mid {\cal P}^{\mathbf{x}} }^{-1} ( \lbrace j \rbrace )\big\vert\]

5.

Soit $i∈⟦0, \lfloor n/2 \rfloor⟧$.

Sous les hypothèses de l’énoncé :

\[n= \sum\limits_{j∈⟦1,n⟧} j n_j^{\mathbf{x}} \\ = n_1^{\mathbf{x}} + 2 n_2^{\mathbf{x}} \\ = n_1^{\mathbf{x}} + 2 i\]

La donnée d’un vecteur $\mathbf{x}$ dans ${\cal E}_2⊆⟦1,N⟧^n$ tel que $n_2^{\mathbf{x}} = i$ correspond de manière biunivoque à la donnée :

• de $n_1^{\mathbf{x}} + i = n-2i +i = n-i$ éléments $y∈⟦1, N⟧$ qui forment l’ensemble ${\cal F}^{\mathbf{x}}$ ordonnés par ordre d’apparition dans ${\mathbf{x}}$, c’est-à-dire d’un $(n-i)$-uplet d’éléments distincts de $⟦1, N⟧$.

  ⟶ il y a $N(N-1)⋯(N-(n-i)+1)$ choix possibles

• d’une partition de $⟦1,n⟧$ en

  • $n_1^{\mathbf{x}} = n - 2i$ parties de cardinal $1$ (les indices des $y∈{\cal F}^{\mathbf{x}}$ de multiplicité $1$ dans $\mathbf{x}$)
  • et $n_2^{\mathbf{x}} = i$ parties de cardinal $2$ (les indices des $y∈{\cal F}^{\mathbf{x}}$ de multiplicité $2$ dans $\mathbf{x}$).

  ⟶ il y a $\frac{n!}{(n-2i)!i!2^{i}}$ choix possibles (d’après Q2)

On en conclut que :

Il y a

\[\frac{N! n!}{(N-n+i)!(n-2i)!i!2^{i}}\]

$\mathbf{x}$ dans ${\cal E}_2$ tel que $n_2^{\mathbf{x}} = i$

6.

\[{\cal E}_2 = \bigsqcup\limits_{i=0}^{\lfloor n/2 \rfloor} \lbrace \mathbf{x}∈{\cal E}_2 \, \, \mid \, \, n_2^{\mathbf{x}} = i \rbrace\]

Donc

\[\begin{align*} \vert {\cal E}_2 \vert &= \sum\limits_{i=0}^{\lfloor n/2 \rfloor} \frac{N! n!}{(N-n+i)!(n-2i)!i!2^{i}} \end{align*}\]

7.

On note $A_2$ l’événement “au moins trois des variables parmi $X_1, ⋯, X_n$ prennent la même valeur”.

L’événement complémentaire $\overline{A_2}$ est “pour tout $m≥3$, pour tous indices deux-à-deux distincts $i_1, i_2, ⋯, i_m ∈⟦1, n⟧$, $X_{i_1}, ⋯, X_{i_m}$ ne prennent pas la même valeur”.

C’est-à-dire :

\[\begin{align*} \overline{A_2} &= \Big((X_1, ⋯, X_n) ∈ \Big\lbrace \mathbf{x} ≝ (x_1, \ldots, x_n) ∈ ⟦1,N⟧^n \, \, \mid \, \, \lbrace I_u^{\mathbf{x}} ∈ {\cal P}^{\mathbf{x}} \, \, \vert \, \, Card(I_u^{\mathbf{x}}) ≥ 3 \rbrace =∅ \Big\rbrace \Big) \\ &= \Big((X_1, ⋯, X_n) ∈ \Big\lbrace \mathbf{x} ≝ (x_1, \ldots, x_n) ∈ ⟦1,N⟧^n \, \, \mid \, \, ∀m≥3, \lbrace I_u^{\mathbf{x}} ∈ {\cal P}^{\mathbf{x}} \, \, \vert \, \, Card(I_u^{\mathbf{x}}) = m \rbrace = ∅ \Big\rbrace \Big) \\ &= \Big((X_1, ⋯, X_n) ∈ \Big\lbrace \mathbf{x} ≝ (x_1, \ldots, x_n) ∈ ⟦1,N⟧^n \, \, \mid \, \, ∀m≥3, \vert \lbrace I_u^{\mathbf{x}} ∈ {\cal P}^{\mathbf{x}} \, \, \vert \, \, Card(I_u^{\mathbf{x}}) = m \rbrace \vert = 0 \Big\rbrace \Big) \\ &= \Big((X_1, ⋯, X_n) ∈ \Big\lbrace \mathbf{x} ≝ (x_1, \ldots, x_n) ∈ ⟦1,N⟧^n \, \, \mid \, \, ∀m≥3, n_m^{\mathbf{x}} = 0 \Big\rbrace \Big) && \text{(par Q4)}\\ &= \Big((X_1, ⋯, X_n) ∈ \Big\lbrace \mathbf{x} ≝ (x_1, \ldots, x_n) ∈ ⟦1,N⟧^n \, \, \mid \, \, ∀m∈ℕ, m>2 ⟹ n_m^{\mathbf{x}} = 0 \Big\rbrace \Big) \\ & = \Big((X_1, ⋯, X_n) ∈ {\cal E}_2 \Big) &&\text{ (par définition de ${\cal E}_2$)} \\ \end{align*}\]

On calcule la probabilité de $\overline{A_2}$ : comme les $(X_i)_{i∈⟦1,n⟧}$ sont indépendantes et suivent toutes la loi $𝒰(⟦1, N⟧)$ :

\[P(\overline{A_2}) = \frac{\vert {\cal E}_2 \vert}{\vert ⟦1,N⟧^n \vert} = \frac{N! n!}{N^n} \sum\limits_{i=0}^{\lfloor n/2 \rfloor} \frac{1}{(N-n+i)!(n-2i)!i!2^{i}}\]

Donc

La probabilité recherchée vaut :

\[1 - \frac{N! n!}{N^n} \sum\limits_{i=0}^{\lfloor n/2 \rfloor} \frac{1}{(N-n+i)!(n-2i)!i!2^{i}}\]

8.

a).

Avec les notations précédentes : il s’agit d’un cas particulier où $N = 365$ et, pour tout $i∈⟦1,n⟧$, $X_i \leadsto 𝒰(⟦1,N⟧)$ est la variable aléatoire qui, à la $i$-ème personne, associe le numéro du jour de son anniversaire (par hypothèse d’uniforme distribution des dates d’anniversaire).

Par suite :

\[p_n = 1 - \frac{365!n!}{365^n} \sum\limits_{i=0}^{\lfloor n/2 \rfloor} \frac{1}{(365-n+i)!(n-2i)!i!2^{i}}\]

b).

Avec le script python suivant :

from quicktions import Fraction
import numpy as np
import matplotlib.pyplot as plt

N = 365

n_max = 200
x = range(1, n_max)
plt.xlim(1, n_max)
plt.ylim(0, 1)

special_ycoord = [0.5, 0.95]

special_xcoord = []

def p():
    global N

    n=1

    is_n_even = False

    N_n = N


    TermsSum = [Fraction(N)]

    lenTermsSum = 1

    while True:
        yield float(1-Fraction(sum(TermsSum),N_n))
        #yield TermsSum, sum(TermsSum), N_n

        n+=1
        is_n_even = not is_n_even


        for i in range(lenTermsSum):
            TermsSum[i] = Fraction(TermsSum[i], Fraction((n-2*i)))
            TermsSum[i] *= n*(N-n+i+1)

        N_n *= N

        if is_n_even:
            TermsSum.append(Fraction(Fraction(TermsSum[-1]*2),Fraction((N-(n-(n/2-1))+1)*n)))
            lenTermsSum +=1

def special_plot(x,y):
    global special_ycoord, special_xcoord

    if not special_ycoord or len(special_xcoord)>=len(special_ycoord):
        return y

    if y >= special_ycoord[len(special_xcoord)]:
        special_xcoord.append(x)

    return y


P = p()
plt.plot(x, [special_plot(i, next(P)) for i in x], 'b.-')
plt.title('Graphe de la suite $(p_n)_{n≥0}$')
plt.ylabel('$p_n$')
plt.xlabel('$n$')
plt.grid(True)

for i, t in enumerate(special_xcoord):
    plt.plot([t,t],[0,special_ycoord[i]], color ='red', linewidth=3.5, linestyle="--")
    plt.scatter([t,],[special_ycoord[i],], 50, color ='red')

    plt.annotate(r'$n_{'+str(special_ycoord[i])+'}='+str(t)+'$',
                xy=(t, special_ycoord[i]), xycoords='data',
                xytext=(-110, 0), textcoords='offset points', fontsize=16,
                arrowprops=dict(arrowstyle="->", connectionstyle="arc3,rad=-.2"))

special_xcoord.extend([1, n_max])
special_ycoord.extend([0,1])

plt.xticks(special_xcoord)
plt.yticks(special_ycoord)


plt.show()

on obtient :

---

NB : pour le calcul de $p_n$, on a utilisé

\[p_n = 1 - \frac{1}{N^n} \sum\limits_{i=0}^{\lfloor n/2 \rfloor} \frac{(N)_{n-i} (n)_{2i} }{i!2^{i}}\]

avec $N=365$, et où $(x)_{k} ≝ x(x-1)(x-2)\cdots (x-k+1)$ est la factorielle décroissante

---

Il vient que :

La valeur de $n$ à partir de laquelle $p_n ≥ 0.5$ (resp. $p_n ≥ 0.95$) est $88$ (resp. $145$).

9.

De manière analogue, on note ${\cal E}_3$ l’ensemble des $\mathbf{x} ≝ (x_1, ⋯, x_n)$ tels que $n_j^{\mathbf{x}} = 0$ si $j > 3$, $A_3$ l’événement “au moins quatre des variables parmi $X_1, ⋯, X_n$ prennent la même valeur”.

De la même manière, on montre que

\[\overline{A_3} = \Big((X_1, ⋯, X_n) ∈ {\cal E}_3 \Big)\]

Et comme les $(X_i)_{i∈⟦1,n⟧}$ sont indépendantes et suivent toutes la loi $𝒰(⟦1, N⟧)$ :

\[P(\overline{A_3}) = \frac{\vert {\cal E}_3 \vert}{\vert ⟦1,N⟧^n \vert}\]

Calcul de $\vert {\cal E}_3 \vert$

Soit $j∈⟦0,\lfloor n/3\rfloor⟧$, $i∈⟦0, \lfloor \frac{n-3j}{2}\rfloor⟧$.

---

Calcul de $\vert \lbrace \mathbf{x} ∈ {\cal E}_3 \, \, \mid \, \, (n_3^{\mathbf{x}} = j) ∧ (n_2^{\mathbf{x}} = i) \rbrace \vert$

D’après Q3 :

\[n= \sum\limits_{j∈⟦1,n⟧} j n_j^{\mathbf{x}} \\ = n_1^{\mathbf{x}} + 2 n_2^{\mathbf{x}} + 3 n_2^{\mathbf{x}} \\ = n_1^{\mathbf{x}} + 2 i + 3 j\]

La donnée d’un vecteur $\mathbf{x}$ dans ${\cal E}_3⊆⟦1,N⟧^n$ tel que $n_3^{\mathbf{x}} = j$ et $n_2^{\mathbf{x}} = i$ correspond de manière biunivoque à la donnée :

• de $n_1^{\mathbf{x}} + i + j = n-i-2j$ éléments $y∈⟦1, N⟧$ qui forment l’ensemble ${\cal F}^{\mathbf{x}}$ ordonnés par ordre d’apparition dans ${\mathbf{x}}$, c’est-à-dire d’un $(n-i-2j)$-uplet d’éléments distincts de $⟦1, N⟧$.

  ⟶ il y a $N(N-1)⋯(N-(n-i-2j)+1)$ choix possibles

• d’une partition de $⟦1,n⟧$ en

  • $n_1^{\mathbf{x}} = n - 2i -3j$ parties de cardinal $1$ (les indices des $y∈{\cal F}^{\mathbf{x}}$ de multiplicité $1$ dans $\mathbf{x}$)
  • $n_2^{\mathbf{x}} = i$ parties de cardinal $2$ (les indices des $y∈{\cal F}^{\mathbf{x}}$ de multiplicité $2$ dans $\mathbf{x}$).
  • et $n_3^{\mathbf{x}} = j$ parties de cardinal $3$ (les indices des $y∈{\cal F}^{\mathbf{x}}$ de multiplicité $3$ dans $\mathbf{x}$).

  ⟶ il y a $\frac{n!}{(n-2i-3j)!i!j! 2^i 6^j}$ choix possibles (d’après Q2)

On en conclut que :

\[\vert \lbrace \mathbf{x} ∈ {\cal E}_3 \, \, \mid \, \, (n_3^{\mathbf{x}} = j) ∧ (n_2^{\mathbf{x}} = i) \rbrace \vert = \frac{N!n!}{(N-n+i+2j)!(n-2i-3j)!i!j! 2^i 6^j}\]

---

\[{\cal E}_3 = \bigsqcup\limits_{j=0}^{\lfloor n/3 \rfloor}\bigsqcup\limits_{i=0}^{\lfloor \frac{n-3j}{2} \rfloor} \lbrace \mathbf{x} ∈ {\cal E}_3 \, \, \mid \, \, (n_3^{\mathbf{x}} = j) ∧ (n_2^{\mathbf{x}} = i) \rbrace\]

Donc

\[\begin{align*} \vert {\cal E}_3 \vert &= \sum\limits_{j=0}^{\lfloor n/3 \rfloor}\sum\limits_{i=0}^{\lfloor \frac{n-3j}{2} \rfloor} \frac{N!n!}{(N-n+i+2j)!(n-2i-3j)!i!j! 2^i 6^j} \end{align*}\]

et

\[P(\overline{A_3}) = \frac{N!n!}{N^n}\sum\limits_{j=0}^{\lfloor n/3 \rfloor}\sum\limits_{i=0}^{\lfloor \frac{n-3j}{2} \rfloor} \frac{1}{(N-n+i+2j)!(n-2i-3j)!i!j! 2^i 6^j}\]

d’où :

\[p_n = P(A_3) = 1 - \frac{N!n!}{N^n}\sum\limits_{j=0}^{\lfloor n/3 \rfloor}\sum\limits_{i=0}^{\lfloor \frac{n-3j}{2} \rfloor} \frac{1}{(N-n+i+2j)!(n-2i-3j)!i!j! 2^i 6^j}\]

On modifie le script python précédent :

from quicktions import Fraction
import numpy as np
import matplotlib.pyplot as plt


N = 365

n_max = 400
x = range(1, n_max)
plt.xlim(1, n_max)
plt.ylim(0, 1)

special_ycoord = [0.5, 0.95]

special_xcoord = []

def p4():
    global N

    n=1

    is_n_not_multiple3 = 1

    is_nminus3j_even = [False]

    N_n = N


    TermsSum = [[Fraction(N)]]

    lenTermsSum = 1

    while True:
        yield float(1-Fraction(sum([i for j in TermsSum for i in j]),N_n))
        #yield TermsSum, sum([i for j in TermsSum for i in j]), N_n

        n+=1
        is_n_not_multiple3 = (is_n_not_multiple3 + 1) % 3

        for j in range(lenTermsSum):
            is_nminus3j_even[j] = not is_nminus3j_even[j]

        for j in range(lenTermsSum):
            for i in range(len(TermsSum[j])):
                TermsSum[j][i] = Fraction(TermsSum[j][i], Fraction(n-2*i-3*j))
                TermsSum[j][i] *= n*(N-n+i+2*j+1)

        N_n *= N

        for j in range(lenTermsSum):
            if is_nminus3j_even[j]:
                TermsSum[j].append(Fraction(Fraction(TermsSum[j][-1]*2),Fraction((N-(n-((n-3*j)/2-1)-2*j)+1)*(n-3*j))))


        if not is_n_not_multiple3:
            k = N-(n-2*(n/3-1))+1
            TermsSum.append([Fraction(Fraction(TermsSum[-1][0]*6),Fraction(k*(k+1)*2*n))])
            is_nminus3j_even.append(True)
            lenTermsSum +=1



def special_plot(x,y):
    global special_ycoord, special_xcoord

    if not special_ycoord or len(special_xcoord)>=len(special_ycoord):
        return y

    if y >= special_ycoord[len(special_xcoord)]:
        special_xcoord.append(x)

    return y






P_4 = p4()
plt.plot(x, [special_plot(i, next(P_4)) for i in x], 'b.-')
plt.title('Graphe de la suite $(p_n)_{n≥0}$')
plt.ylabel('$p_n$')
plt.xlabel('$n$')
plt.grid(True)

for i, t in enumerate(special_xcoord):
    plt.plot([t,t],[0,special_ycoord[i]], color ='red', linewidth=3.5, linestyle="--")
    plt.scatter([t,],[special_ycoord[i],], 50, color ='red')

    plt.annotate(r'$n_{'+str(special_ycoord[i])+'}='+str(t)+'$',
                xy=(t, special_ycoord[i]), xycoords='data',
                xytext=(-110, 0), textcoords='offset points', fontsize=16,
                arrowprops=dict(arrowstyle="->", connectionstyle="arc3,rad=-.2"))

special_xcoord.extend([1, n_max])
special_ycoord.extend([0,1])

plt.xticks(special_xcoord)
plt.yticks(special_ycoord)


plt.show()

et on obtient :

---

NB : pour le calcul de $p_n$, on a utilisé

\[p_n = 1 - \frac{1}{N^n}\sum\limits_{j=0}^{\lfloor n/3 \rfloor}\sum\limits_{i=0}^{\lfloor \frac{n-3j}{2} \rfloor} \frac{(N)_{n-i-2j} (n)_{2i+3j}}{i!j! 2^i 6^j}\]

avec $N=365$

---

Il vient que :

La valeur de $n$ à partir de laquelle $p_n ≥ 0.5$ (resp. $p_n ≥ 0.95$) est $187$ (resp. $280$).

On peut comparer la suite du problème des trois anniversaires avec celle des quatre anniversaires sur le même graphe (le script est sur mon github) :

Problème

Partie I

1.

Soit $z∈ℂ$ tel que $\vert z \vert≤ 1$. Pour tout $n∈ℕ$,

\[\vert P(X = n) z^n \vert ≤ \underbrace{P(X = n)}_{ \text{terme général de série (positive) convergente (vers 1)} }\]

La série $G_X ≝ \sum\limits_{ n≥0 } P(X=n) \bullet^n$ converge donc normalement sur le disque unité fermé $\lbrace z∈ℂ \, \mid \, \vert z \vert ≤ 1 \rbrace$

et

\[G_X(1) = \sum\limits_{ n≥0 } P(X=n) = 1\]

(car $P$ est une probabilité)

2.

Par ce qui précède : le rayon de convergence de $G_X$ est supérieur ou égal à $1$.

3.

---

NB : Dans l’énoncé : je suppose que, par $G_X$, il est entendu ${G_X}_{\vert [-1, 1]}$ (la dérivation de la variable complexe n’étant pas au programme de prépa, et le cours d’analyse complexe n’ayant lieu qu’au second semestre¹). Je ferai aussi l’abus de notation, dans la suite.

---

Montrons que

\[E(X) < +∞ ⟺ G_X \text{ est dérivable à gauche en } 1\]

$⟹$ :

Comme le disque unité fermé est inclus dans le domaine de convergence de $G_X$ : $∀t ∈ ]-1, 1[
$,

\[G'_X(t) = \sum\limits_{ n≥1 } n P(X=n) t^{n-1} = \sum\limits_{ n≥0 } (n+1) P(X=n+1) t^n\]

De plus, comme $X$ admet une espérance finie, la série entière $\sum\limits_{ n≥0 } (n+1) P(X=n+1) \bullet^n$ converge en $1$ (vers $E(X)$).

Montrons que :

$G_X$ est dérivable à gauche en $1$, et

\[G'_X(1) = \sum\limits_{ n≥1 } n P(X=n) ≝ E(X)\]

Méthode 1 : avec des outils élémentaires

---

Rappel :

Théorème de prolongement de la dérivée : Si $f$ est continue sur $[a,b]$, dérivable sur $]a,b[$, et si $f’$ a une limite finie $l$ en $b$, alors $f$ est dérivable à gauche en $b$ et

\[\underbrace{f'_g}_{\text{dérivée à gauche}}(b)=l\]

i.e $f’$ est continue à gauche en $b$.

Démonstration (vue en math sup) :

Pour tout $x∈[a,b[$, d’après le théorème des accroissements finis, il existe $c_x∈]x,b[$ tel que

\[\frac{f(b)-f(x)}{b-x} = f'(c_x)\]

Comme $c_x$ tend vers $b$ quand $x$ tend vers $b$, le résultat est acquis en passant à la limite, pour $x$ tendant vers $b$.

---

Comme $G’_X$ a le même rayon de convergence que $G_X$, $G’_X$ est aussi dérivable sur $]-1, 1[$, et

\[∀t∈[0, 1[, G''_X(t) = \sum\limits_{ n≥2 } n(n-1) P(X=n) t^{n-2} ≥ 0\]

Donc $G’_X$ croît sur $[0, 1[$, et $G_X’$

• converge en $1^{-}$

OU

• diverge vers $+∞$ en $1^{-}$

Or, pour tous $n∈ℕ, t∈[0, 1]$,

\[0≤(n+1) P(X=n+1) t^n ≤ \underbrace{(n+1) P(X=n+1)}_{\text{terme général de série (positive) convergente, par hypothèse}}\]

donc $G_X’$ est bornée sur $[0,1]$, et elle converge donc en $1^{-}$.

Or, la fonction $\sum\limits_{ n≥0 } (n+1) P(X=n+1) \bullet^n$ ne peut que converger vers sa valeur en $1$ (i.e $E(X)$) en $1^{-}$

• car si elle convergeait vers une limite $l≠E(X)$, l’intervalle ouvert centré en $l$ et de rayon $\vert E(X) - l \vert/3$ (auquel n’appartient pas $E(X)$) serait un voisinage de $l$ qui ne contiendrait aucune image par $f$ de voisinage à gauche de $1$.

De plus, comme le disque unité fermé est inclus dans son domaine de convergence, $G_X$ est continue en $1$.

Il vient donc, d’après le théorème de prolongement de la dérivée, que $G_X$ est dérivable à gauche en $1$, et

\[G'_X(1) = \sum\limits_{ n≥1 } n P(X=n) ≝ E(X)\]

Méthode 2 : avec le théorème d’Abel

---

Théorème d’Abel : Si la série entière $f(t) ≝ \sum\limits_{n≥0} a_n t^n$ converge pour tout $\vert t \vert < 1$, et si $\sum\limits_{n≥0} a_n$ converge vers $l$, alors

\[\lim_{t→1^{−}} f(t) = l ≝ \sum\limits_{n≥0} a_n = f(1)\]

Démonstration 1 (vue en maths spé) :

Pour tout $N∈ℕ$, on pose $S_N ≝ \sum\limits_{n=0}^N a_n$

$∀ t\in]0,1[, N∈ℕ :$

\[\begin{align*} \sum_{n=0}^N a_n t^n & = \sum_{n=1}^{N}(S_n-S_{n-1}) t^n + a_0 \\ & = \sum_{n=1}^{N} S_n t_n - \sum_{n=1}^{N} S_{n-1} t^n + a_0 \\ & = \sum_{n=1}^{N} S_n t_n - \sum_{n=0}^{N-1} S_{n} t^{n+1} + a_0 \\ & = \sum_{n=1}^{N-1} S_n (t^n - t^{n+1}) + S_N t^N - S_{0} t + \underbrace{a_0}_{= S_0} \\ & = S_0 (t^0 - t^1) + \sum_{n=0}^{N-1} S_n (t^n - t^{n+1}) + S_N t^N \\ & = \sum_{n=0}^{N-1} S_n (t^n - t^{n+1}) + S_N t^N \\ & = (1-t)\sum_{n=0}^{N-1} S_n t^n + \underbrace{S_N}_{\xrightarrow[N \to +∞]{} \sum\limits_{n≥0} a_n} \overbrace{t^N}^{\phantom{\Bigg|}\xrightarrow[N \to +∞]{} \, \, 0} \\ &\xrightarrow[N \to +∞]{} (1-t)\sum_{n=0}^{+∞} S_n t^n \overset{\text{donc}}{=} f(t) &&\text{(la somme existe car $\sum_{n=0}^N a_n t^n$ converge quand $N \to +∞$)} \\ \end{align*}\]

Soit $ε > 0$.

Comme $S_n \xrightarrow[n \to +∞]{} l$, il existe un rang $N∈ℕ$ tel que $∀n≥N, \vert S_n - l \vert ≤ 𝜀/2$

On pose

\[𝛼 ≝ \sum_{n=0}^{N-1} \vert S_n - l \vert\]

Donc $∀ t\in]1-\frac{𝜀}{2𝛼},1[$,

\[\begin{align*} \vert f(t)-l \vert & = \left\vert (1-t)\sum_{n=0}^{+∞} S_n t^n - (1-t) \sum_{n=0}^{+∞} l t^n \right\vert \\ & = \left\vert (1-t)\sum_{n=0}^{+∞} (S_n - l) t^n \right\vert \\ & = \left\vert (1-t)\sum_{n=0}^{N-1} (S_n - l) t^n + (1-t)\sum_{n=N}^{+∞} (S_n - l) t^n \right\vert \\ & ≤ \left\vert (1-t)\sum_{n=0}^{N-1} (S_n - l) t^n \right\vert + \left\vert \frac{𝜀}{2} (1-t)\sum_{n=N}^{+∞} t^n \right\vert \\ & ≤ (1-t) \sum_{n=0}^{N-1} \left\vert (S_n - l) \right\vert t^n + \frac{𝜀}{2} \underbrace{t^N}_{≤1} (1-t)\sum_{n=0}^{+∞} t^n \\ & ≤ \underbrace{(1-t) 𝛼}_{≤ \frac{𝜀}{2}} + \frac{𝜀}{2} = 𝜀 \\ \end{align*}\]

Donc $f(t) \xrightarrow[t \to 1^{-}]{} l$, et le résultat est acquis.

Démonstration 2 (alternative, pour utiliser l’indication de l’énoncé) :

Je viens de m’en rendre compte (bien après avoir rédigé complètement cette question), mais : si la suite $(a_n)$ est positive (ce qui sera le cas, pour nous, à chaque fois qu’on appliquera le théorème d’Abel par la suite), le théorème d’Abel joue parfaitement le rôle de “théorème de convergence du type convergence dominée” dont il est fait mention dans l’énoncé.

Pour illustrer cette idée, je vais démontrer cette version allégée du théorème d’Abel (mais suffisante pour nous), où je supposerai $(a_n)$ positive, en utilisant le théorème de convergence dominée vu en prépa.

Théorème de convergence dominée :

Soit $(g_m)_{m≥0}$ une suite de fonctions continues par morceaux d’un intervalle $I$ vers $𝕂 = ℝ \text{ ou } ℂ$ convergeant simplement vers une fonction $g: I→𝕂$ elle-même continue par morceaux.

S’il existe une fonction $φ:I→ℝ^+$ continue par morceaux et intégrable vérifiant :

\[∀m∈ℕ, \vert g_m \vert ≤ φ\]

alors les fonctions $g_n$ et la fonction $g$ sont intégrables et

\[∫_I g_m(x) dx \xrightarrow[m→+∞]{} ∫_I g(x) dx\]

Soit $(t_m)_{m∈ℕ} ∈ [0,1[^ℕ$ une suite de réels tendant vers $1^{—}$.

Pour tout $(x,t)∈ℝ^+ × [0,1[$, on pose

\[g(t, x) ≝ a_{\lfloor x \rfloor} t^{\lfloor x \rfloor}\]

En outre, pour tout $(x,m)∈ℝ^+ × ℕ$, on pose

\[g_m(x) ≝ g(t_m, x) = a_{\lfloor x \rfloor} t_m^{\lfloor x \rfloor}\]

Donc $∀m, n∈ℕ, ∀x∈[n, n+1[$,

\[g_m(x) = a_n t_m^n\]

Et la suite $(g_m)_{m≥0}$ de fonctions continues par morceaux de $I ≝ ℝ^+$ vers $ℝ$ convergent simplement vers la fonction continue par morceaux $g: I→ℝ$ définie par :

\[∀x∈ℝ^+, g(x) ≝ a_{\lfloor x \rfloor}\]

Soit : $∀n∈ℕ, ∀x∈[n, n+1[$,

\[g(x) = a_n\]

Comme :

• $g$ est à valeurs positives, continue par morceaux et intégrable
  • car $(a_n)$ est positive, et $\sum\limits_{n≥0} a_n$ converge par hypothèse
• $∀m∈ℕ, \vert g_m \vert = g_m ≤ g$

alors d’après le théorème de convergence dominée,

\[\sum\limits_{ n∈ℕ } a_n t_m^n = ∫_{ℝ^+} g_m(x) dx \xrightarrow[m→+∞]{} ∫_{ℝ^+} g(x) dx = \sum\limits_{n≥0} a_n\]

On a montré que pour toute suite $(t_m)_{m∈ℕ} ∈ [0,1[^ℕ$ de réels tendant vers $1^{—}$,

\[f(t_m) = \sum\limits_{ n∈ℕ } a_n t_m^n \xrightarrow[m→+∞]{} \sum\limits_{n≥0} a_n\]

donc

\[f(t) \xrightarrow[t→1^{-}]{} \sum\limits_{n≥0} a_n\]

par caractérisation séquentielle de la limite, et le résultat est acquis.

---

On applique le théorème d’Abel (ou même sa version allégée) à $G’_X$, et le résultat s’ensuit immédiatement.

$⟸$ :

Par contraposée : supposons que $E(X) = +∞$.

Par l’absurde : si $G_X(t)$ ne divergeait pas vers $+∞$ quand $t$ tend vers $1^{-}$ : il existerait un majorant $M∈ℝ$ tel que pour tous $N∈ℕ, t∈[0, 1[$,

\[\sum\limits_{ n=0 }^N n P(X=n) t^{n-1} ≤ \sum\limits_{ n≥0 } n P(X=n) t^{n-1} = G'_X(t) ≤ M\]

Donc en faisant tendre $N$ vers $+∞$, $t$ vers $1^{-}$, on aurait :

\[E(X) ≝ \sum\limits_{ n≥0 } n P(X=n) ≤ M\]

ce qui est absurde.

Donc $G_X(t) \xrightarrow[t \to 1^{-}]{} +∞$.

On a donc montré que :

\[E(X) < +∞ ⟺ G_X \text{ est dérivable à gauche en } 1\]

et, en cas d’existence :

\[E(X) = G'_X(1)\]

4.

Soient $X$ et $Y$ deux variables indépendantes à valeurs dans $ℕ$.

Soit $t$ dans l’intersection des disques de convergence de $G_X$ et $G_Y$.

Méthode 1 : produit de Cauchy

\[\begin{align*} G_{X+Y} (t) & = \sum\limits_{ n≥0 } P(X+Y=n) t^n \\ & = \sum\limits_{ n≥0 } \sum\limits_{k=0}^n P(X=k, Y=n-k) t^k t^{n-k} &&\text{(par $𝜎$-additivité, car $(X+Y=n) = \bigsqcup\limits_{k=0}^n (X=k, Y=n-k)$)}\\ & = \sum\limits_{ n≥0 } \sum\limits_{k=0}^n t^kP(X=k) t^{n-k} P(Y=n-k) &&\text{(car $X$ et $Y$ sont indépendantes)} \\ & \overset{⊛}{=} \sum\limits_{ n≥0 } t^nP(X=n) \sum\limits_{ n≥0 } t^n P(Y=n) \\ & = G_X(t) G_Y (t) \\ \end{align*}\]

L’avant-dernière égalité $⊛$ venant du fait que le produit de Cauchy des deux séries entières $G_X$ et $G_Y$ est une série entière de rayon de convergence supérieur au minimum de leurs rayons de convergence : il est donc défini en $t$, qui est dans l’intersection de leurs disques de convergence.

Méthode 2 : espérance d’un produit de variables indépendantes

Par le lemme des coalitions, les variables $t^X$ et $t^Y$ sont aussi indépendantes, donc

\[\begin{align*} G_{X+Y} (t) & = E(t^{X+Y}) &&\text{(par le théorème de transfert)} \\ & = E(t^Xt^Y) \\ & = E(t^X)E(t^Y) &&\text{(l'espérance d'un produit de variables indépendantes est le produit des espérances)}\\ & = G_X(t) G_Y (t) \\ \end{align*}\]

On a montré que pour tout $t$ dans l’intersection des disques de convergence de $G_X$ et $G_Y$

\[G_{X+Y} (t) = G_X(t) G_Y (t)\]

Partie II

1.

Si $X \leadsto ℬ(p)$,

\[G_X : t \mapsto 1-p + pt = 1 + p(t-1)\]

son rayon de convergence est infini (fonction polynomiale).

2.

Si $X \leadsto ℬ(n,p)$, on obtient par le calcul que :

\[∀t∈ℝ, G_X(t) = \sum\limits_{k=0}^n p^k (1-p)^{n-k} t^k \\ = \sum\limits_{k=0}^n (pt)^k (1-p)^{n-k} = (1-p + pt)^n \\ = (1 + p(t-1))^n\]

NB : alternativement, on peut aussi remarquer que $X$ suit la même loi qu’une somme de $n$ variables aléatoires indépendantes de Bernoulli de paramètre $p$, et le résultat s’ensuit d’après les questions I.4 et II.1.

Si $X \leadsto ℬ(n,p)$,

\[G_X : t \mapsto (1 + p(t-1))^n\]

son rayon de convergence est infini (fonction polynomiale).

3.

NB : On suppose que $X$ est à valeurs dans $ℕ’ = ℕ^\ast$ et pas dans $ℕ$, car sinon $\sum\limits_{k≥0} P(X=k)$ ne vaut pas $1$.

Si $X \leadsto 𝒢(p)$ :

$∀t∈[0, \frac{1}{1-p}[$,

\[\begin{align*} G_X(t) & = \sum\limits_{k≥1} p (1-p)^{k-1} t^k \\ & = \frac{p}{1-p} \sum\limits_{k≥1} ((1-p)t)^k \\ & = \frac{p}{1-p} \sum\limits_{k≥1} ((1-p)t)^k \\ & = \frac{pt}{1-(1-p)t} \end{align*}\]

Si $X \leadsto 𝒢(p)$,

\[G_X : t \mapsto \frac{pt}{1-(1-p)t}\]

son rayon de convergence vaut $\frac{1}{1-p}$.

4.

Si $X \leadsto 𝒫(𝛼)$ :

\[∀t∈ℝ, G_X(t) = {\rm e}^{-𝛼} \sum\limits_{k≥0} \frac{𝛼^k}{k!} t^k \\ = {\rm e}^{-𝛼} \sum\limits_{k≥0} \frac{(𝛼t)^k}{k!} = {\rm e}^{-𝛼+𝛼t}\]

Si $X \leadsto 𝒫(𝛼)$,

\[G_X : t \mapsto {\rm e}^{𝛼(t-1)}\]

son rayon de convergence est infini (exponentielle).

Partie III

1.

Comme $X_1$ est à valeurs dans $ℕ$, par définition de la série génératrice :

\[G_{X_1} : t \mapsto \sum\limits_{k≥0} p_k t^k\]

d’où

\[G_{X_1} = S\]

2.

NB : Par convention, on note $X_0$ une variable aléatoire à valeurs dans $ℕ$ ayant pour loi :

• $P(X_0 = 1) = 1$
• $∀k ≠1, P(X_0 = k) = 0$

de telle sorte que $G_{X_0} = id$

Montrons que $∀n∈ℕ’$ :

\[∀t ∈]−R, R[, G_{X_n}(t) = G_{X_{n−1}}(G_{X_1}(t))\]

Pour tout $l ∈ ℕ$ :

\[∀k ∈ ⟦1, n⟧, P(X_n = l \vert X_{n-1} = k) = P(Y_1 + ⋯ + Y_k = l)\]

d’où

\[∀k ∈ ⟦1, n⟧, P((X_n = l) ∩ (X_{n-1} = k)) = P(X_{n-1} = k) P(Y_1 + ⋯ + Y_k = l)\]

et comme $(X_n = l) = \bigsqcup\limits_{k≥0} \Big((X_n = l) ∩ (X_{n-1} = k) \Big)$ :

\[P(X_n = l) = \sum\limits_{k≥0} P(X_{n-1} = k) P(Y_1 + ⋯ + Y_k = l)\]

donc, sachant que le rayon de convergence de $G_{X_n}$ est supérieur à $1$ (puisque $\sum_{l∈ℕ} P(X_n = l) = 1$) :

$∀t ∈]-1, 1[$,

\[G_{X_n}(t) = \sum\limits_{l≥0} P(X_n = l) t^l = \sum\limits_{l≥0} \sum\limits_{k≥0} P(X_{n-1} = k) P(Y_1 + ⋯ + Y_k = l) t^l\]

Soit, par le théorème de Fubini :

$∀t ∈]-1, 1[$,

\[G_{X_n}(t) = \sum\limits_{k≥0} P(X_{n-1} = k) \underbrace{\sum\limits_{l≥0} P(Y_1 + ⋯ + Y_k = l) t^l}_{= G_{Y_1+ ⋯ + Y_k}(t)}\]

Or, les $Y_i$ suivent la même loi que $X_1$ et sont indépendantes, donc en appliquant I.4, il vient par une récurrence immédiate que $G_{Y_1+ ⋯ + Y_k} = G_{X_1}^k$, et :

$∀t ∈]-1, 1[$,

\[G_{X_n}(t) = \sum\limits_{k≥0} P(X_{n-1} = k) \big( G_{X_1}(t) \big)^k = G_{X_{n-1}}(G_{X_1}(t))\]

Le résultat est donc acquis :

\[∀n∈ℕ', t ∈]−1, 1[, G_{X_n}(t) = G_{X_{n−1}}(G_{X_1}(t))\]

De fait, par une récurrence immédiate, et par III.1), il vient que :

\[∀n∈ℕ', t ∈]−1, 1[, G_{X_n}(t) = G^n_{X_1}(t) = S^n(t)\]

(pour la composition)

Donc

$∀n∈ℕ’, t ∈]−1, 1[$,

\[G_{X_n}(t) = G_{X_1}(G^{n-1}_{X_1}(t)) \\ = G_{X_1}(G_{X_{n-1}}(t))\]

3.

D’après I.3, II.3, et comme une série entière (de la variable réelle) est dérivable sur l’intérieur de son disque de convergence :

$∀n∈ℕ’, t ∈]−1, 1[$,

\[G_{X_n}'(t) = G'_{X_1}(G_{X_{n-1}}(t))G'_{X_{n-1}}(t)\]

D’où, en faisant tendre $t$ vers $1^{-}$, par continuité à gauche des fonctions génératrices et de leurs dérivées en $1^{-}$ (d’après le théorème d’Abel (ou sa version allégée), démontré en I.3) :

\[\begin{align*} E(X_n) &= G_{X_n}'(1) \\ &= G'_{X_1}(G_{X_{n-1}}(1))G'_{X_{n-1}}(1) \\ &= G'_{X_1}(1)G'_{X_{n-1}}(1) \\ &= E(X_1) E(X_{n-1}) \end{align*}\]

On a donc montré que :

\[∀n∈ℕ, E(X_n) = E(X_1) E(X_{n-1})\]

4.

Comme $(E(X_n))_{n∈ℕ}$ est une suite géométrique de raison $E(X_1)$, on a :

\[∀n∈ℕ, E(X_n) = E(X_1)^n\]

5.

Avec III.2) : $∀n∈ℕ’,$

\[G_{X_n}(0) = G_{X_1}(G_{X_{n-1}}(0))\]

Donc en faisant tendre $n$ vers $+∞$ :

\[l = G_{X_1}(l) = S(l)\]

d’après III.1), et par composition des limites, car

• $G_{X_{n-1}}(0) \xrightarrow[n \to +∞]{} l$
• $G_{X_1}(G_{X_{n-1}}(0)) = S(G_{X_{n-1}}(0)) \xrightarrow[n \to +∞]{} S(l)$

  • en effet : en III.2), on a montré que :

    \[∀n∈ℕ', ∀t∈]-1,1[, G_{X_n}(t) = G_{X_1}^n(t) = S^n(t)\]

    donc

    \[∀n∈ℕ', G_{X_n}(0) = S^n(0)\]

    Or, la dérivée (terme à terme) de la série entière $S$ sur son disque de convergence est une fonction positive sur $[0,1]$, donc $S$ croît sur $[0,1]$, et $S^n$ aussi (par composition), d’où :

    \[∀n∈ℕ', G_{X_n}(0) = S^n(0) ≤ S^n(1) = 1\]

    (car $1$ est un point fixe de $S$)

    donc en passant à la limite pour $n \to +∞$ :

    \[l ≤ 1\]

    et

    • Cas 1 : $l<1$ : dans ce cas, $l$ appartient à l’intérieur du disque de convergence de $S$, donc $S$ est continue en $l$

    • Cas 2 : $l=1$ : dans ce cas, on utilise

      • le fait que $(G_{X_n}(0))_{n∈ℕ’}$ est à valeurs dans $[0,1]$ : en effet, pour le montrer, on procède de même que pour $S$, en utilisant

        • la croissance des $G_{X_n}$ (par positivité de leurs dérivées) sur $[0,1]$

        • et le fait qu’elles aient $1$ pour point fixe

      • et la continuité de $S$ en $1^{-}$ (par le théorème d’Abel (ou sa version allégée))

      pour conclure.

Donc si $(G_{X_n}(0))_{n∈ℕ’}$ admet une limite $l$,

\[S(l) = l\]

6.

$]0,1[$ est inclus dans l’intérieur du disque de convergence de la série entière $S$ : elle y est donc de classe $C^{∞}$.

De plus : $∀k∈ℕ’, ∀t∈]0,1[$,

\[S^{(k)}(t) = \sum\limits_{ n≥0 } (n+k)(n+k-1) ⋯ (n+1) \, p_{n+k} t^n≥0\]

$S$ est infiniment dérivable et ses dérivées successives sont positives sur $]0, 1[$.

Enfin : comme $S’’$ est positive,

$S$ est convexe.

7.

Pour alléger les notations, on pose, pour tout $n∈ℕ$ :

\[u_n ≝ G_{X_n}(0)\]

(toujours avec la convention que $G_{X_0} = id$)

Donc par III.2) :

\[∀n∈ℕ, u_{n+1} = S(u_n)\]

soit :

\[∀n∈ℕ, u_n = S^n(u_0)\]

a) Montrons que $(u_n)_{n∈ℕ}$ croît et converge vers un réel $l∈[0,1]$

Comme vu (dans la section “en effet”) en III.5) : $S$ est croissante sur $[0,1]$, et $u_n$ est à valeurs dans $[0,1]$.

Donc comme

\[0 = u_0 ≤ u_1\]

il s’ensuit, par croissance de $S$, et donc de $S^n$ (par composition) :

\[∀n∈ℕ, u_n = S^n(u_0) ≤ S^n(u_1) = S^{n+1}(u_0) = u_{n+1}\]

D’où la croissance de $u$, et comme elle est majorée (par $1$) : $u$ converge vers un réel $l$.

On a de plus, par passage à la limite dans :

\[∀n∈ℕ, 0≤ u_n ≤ 1\]

que

\[0 ≤ l≤1\]

Le résultat est acquis.

b) Montrons que $S$ admet un plus petit point fixe $t_S∈[0,1]$

On note $E$ l’ensemble des points fixes de $S$ dans $[0,1]$ :

\[E≝ \lbrace t∈[0,1] \, \mid \, S(t)=t \rbrace\]

Comme $1$ est point fixe de $S$, $E$ n’est pas vide, et comme il est minoré, il admet une borne inférieure, notée $t_S$.

Montrons que $t_S∈E$ :

Comme $E = (S-id)^{-1}\big(\lbrace 0 \rbrace \big)$ et $S-id$ est continue sur $[0,1]$, $E$ est un fermé de $[0,1]$ (en tant qu’image réciproque d’un fermé par une fonction continue), donc un fermé de $ℝ$ (puisque $[0,1]$ est fermé).

Donc sa borne inférieure est un minimum, et $t_S∈E$.

c) Montrons que $t_S = l$

Comme $S(t_S) = t_S$, et comme $S$ croît sur $[0,1]$ :

\[S([0,t_S]) ⊆ [0,t_S]\]

donc puisque $u_0∈[0,t_S]$, on montre par une récurrence immédiate que :

\[∀n∈ℕ, u_n = S^n(u_0)∈[0,t_S]\]

d’où, par passage à la limite :

\[l∈[0,t_S]\]

et comme $l$ est un point fixe de $S$ d’après III.5) :

\[l = t_S\]

par minimalité de $t_S$.

On a donc montré que

la suite $(G_{X_n}(0))_{n∈ℕ’}$ est croissante et elle converge vers le plus petit point fixe de $S$ dans $[0, 1]$.

Partie IV

1.

Il s’agit d’un cas particulier de la partie précédente, où $X_1$ et les $Y_i$ suivent la loi de probabilité pour un noeud d’avoir $k$ fils, définie par :

\[∀i, k∈ℕ, P(X_1 = k) = P(Y_i = k) = \frac{1}{2^{k+1}}\]

On a :

\[∀l, k ∈ ⟦1, n⟧, P(X_n = l \, \, \vert \, \, X_{n-1} = k) = P(Y_1 + ⋯ + Y_k = l)\]

car pour que le nombre de noeuds de profondeur $n$ soit égal à $l$ sachant que le nombre de noeuds de profondeur $n-1$ est égal à $k$, il faut et il suffit que les $k$ noeuds de profondeur $n-1$ aient un total de $l$ fils en tout (c’est-à-dire : que la somme de leurs nombres de fils vaille $l$).

On notera que les $Y_i$ sont bien à valeur dans $ℕ$ et indépendantes, car les $k$ noeuds de profondeur $n-1$ ont des fils indépendamment les uns des autres.

2.

En appliquant III.7) :

\[∀n∈ℕ', P(X_n = 0) = G_{X_n}(0) \xrightarrow[n \to +∞]{} l\]

où $l$ est le plus petit point fixe de $S$ dans $[0,1]$.

Or : $∀t∈]-2,2[$,

\[\begin{align*} S(t) & = \frac{1}{2} \sum\limits_{k≥1} \frac{1}{2^k} t^k \\ & = \frac{1}{2-t} \end{align*}\]

on vérifie aisément que ce plus petit point fixe $l$ dans $[0,1]$ est $1$ : c’est l’unique solution de l’équation de degré 2 : $t^2-2t+1=0$, d’inconnue $t$.

On a donc montré que :

\[P(X_n = 0) \xrightarrow[n \to +∞]{} 1\]

donc le résultat est acquis.

1. mais comme il entre en conflit avec le cours de $𝜆$-calcul et le projet de logique, un certain nombre d’informaticiens (dont moi) risquent de pas y assister. ↩