Problème ECG1 maths approfondies : partitions en paires et nombre d’involutions

↩ Chapitre : Probabilités finies · Sommes et dénombrement (ECG1-ECG2)

Introduction

De combien de façons peut-on répartir 2n personnes en n binômes ? Et si l’on autorise certaines personnes à rester seules ? Ces deux dénombrements mènent au nombre d’involutions d’un ensemble, c’est-à-dire des applications f telles que f\circ f=\mathrm{id}.

Le problème entraîne aux raisonnements de dénombrement par disjonction de cas et aux relations de récurrence.

Le sujet

Problème d’après ESSEC, repris dans un concours blanc d’ECS1, adapté au programme ECG 2021. Durée indicative : 1 h 30. Programme : dénombrement, coefficients binomiaux, factorielles, récurrence, applications, Python.

Option : maths approfondies. Niveau : ★★. Faisable : dès le premier semestre, après le chapitre de dénombrement.

Énoncé et corrigé

Une partition d’un ensemble fini non vide E est un ensemble \lbrace A_1,\dots,A_k\rbrace de parties non vides de E, deux à deux disjointes, de réunion E ; ce sont les classes de la partition (l’ordre des classes ne compte pas). Pour n\in\mathbb N^*, on note a_n le nombre de partitions d’un ensemble à 2n éléments en n paires, et l’on pose a_0=1.

Partie I – Partitions en paires

1 ▷ Déterminer a_1, a_2, a_3.

Indication

Pour E=\lbrace1,2,3,4\rbrace, la paire contenant 1 détermine la partition.

Corrigé

a_1=1. Pour \lbrace1,2,3,4\rbrace : \lbrace\lbrace1,2\rbrace,\lbrace3,4\rbrace\rbrace, \lbrace\lbrace1,3\rbrace,\lbrace2,4\rbrace\rbrace, \lbrace\lbrace1,4\rbrace,\lbrace2,3\rbrace\rbrace : a_2=3. Pour six éléments, 5 choix du partenaire de 1, puis a_2=3 façons de partager les quatre autres : a_3=15.

2 ▷ Soit n\geqslant2 et E=\lbrace x_1,\dots,x_{2n}\rbrace. En distinguant les partitions selon la paire qui contient x_1, montrer que a_n=(2n-1)a_{n-1}. En déduire que a_n=\dfrac{(2n)!}{2^n\,n!}.

Indication

Il y a 2n-1 choix pour le partenaire de x_1. Pour la formule close, multiplier et diviser par les nombres pairs.

Corrigé

La paire contenant x_1 est \lbrace x_1,x_j\rbrace avec j\in[\![2,2n]\!] : 2n-1 choix. Une fois cette paire fixée, les autres classes forment une partition en paires des 2n-2 éléments restants : a_{n-1} choix. Ces cas étant disjoints, a_n=(2n-1)a_{n-1}.

Par récurrence, a_n=(2n-1)(2n-3)\cdots3\cdot1=\dfrac{(2n)!}{(2n)(2n-2)\cdots2}=\dfrac{(2n)!}{2^n\,n!}, formule vraie aussi pour n=0.

Partie II – Partitions en paires et singletons

Pour m\in\mathbb N^*, on note b_m le nombre de partitions d’un ensemble à m éléments en classes qui sont des paires ou des singletons.

3 ▷ Déterminer b_1, b_2, b_3, b_4.

Indication

Pour m=4, compter selon le nombre de paires : 0, 1 ou 2.

Corrigé

b_1=1, b_2=2 (deux singletons, ou une paire), b_3=4 (trois singletons, ou une paire parmi 3). Pour m=4 : aucune paire (1), une paire (\binom42=6), deux paires (a_2=3) : b_4=10.

4 ▷ (a) Pour m=2p, en distinguant selon le nombre 2i de singletons, montrer que b_{2p}=\displaystyle\sum_{i=0}^p\binom{2p}{2i}a_{p-i}. (b) Établir une formule analogue pour m=2p+1.

Indication

Le nombre de singletons a la même parité que m. Choisir les éléments seuls, puis une partition en paires des autres.

Corrigé

(a) Si la partition compte 2i singletons, on choisit ces 2i éléments (\binom{2p}{2i} choix), puis une partition en paires des 2p-2i autres (a_{p-i} choix). En sommant sur i : b_{2p}=\displaystyle\sum_{i=0}^p\binom{2p}{2i}a_{p-i}.

(b) Pour m=2p+1, le nombre de singletons est impair, égal à 2i+1 : b_{2p+1}=\displaystyle\sum_{i=0}^p\binom{2p+1}{2i+1}a_{p-i}. Vérification : b_3=\binom31a_1+\binom33a_0=4.

5 ▷ Soit m\geqslant3 et F=\lbrace y_1,\dots,y_m\rbrace. En distinguant selon la classe qui contient y_1, montrer que b_m=b_{m-1}+(m-1)\,b_{m-2}. Calculer b_m pour m\leqslant10.

Indication

La classe de y_1 est soit \lbrace y_1\rbrace, soit une paire \lbrace y_1,y_j\rbrace.

Corrigé

Si \lbrace y_1\rbrace est une classe, les autres classes forment une partition convenable des m-1 éléments restants : b_{m-1} cas. Sinon la classe de y_1 est \lbrace y_1,y_j\rbrace (m-1 choix de j) et les autres classes forment une partition convenable des m-2 éléments restants : (m-1)b_{m-2} cas. D’où b_m=b_{m-1}+(m-1)b_{m-2}.

Avec b_1=1 et b_2=2 : b_3=4, b_4=10, b_5=26, b_6=76, b_7=232, b_8=764, b_9=2620, b_{10}=9496. Contrôle par 4(a) : b_4=a_2+\binom42a_1+\binom44a_0=3+6+1=10.

Partie III – Involutions

6 ▷ Une application f:F\to F est une involution si f\circ f=\mathrm{id}_F. (a) Montrer qu’une involution est bijective. (b) À une involution f, on associe la partition de F en classes \lbrace y,f(y)\rbrace. Montrer que c’est une partition en paires et singletons, et que l’on définit ainsi une bijection. (c) Combien un ensemble à 10 éléments possède-t-il d’involutions ? Quelle est la probabilité qu’une permutation de [\![1,10]\!] choisie au hasard soit une involution ?

Indication

(b) Les classes \lbrace y,f(y)\rbrace ont un ou deux éléments, et z\in\lbrace y,f(y)\rbrace\Rightarrow\lbrace z,f(z)\rbrace=\lbrace y,f(y)\rbrace. Réciproquement, une partition en paires et singletons définit f : échanger les éléments de chaque paire, fixer les singletons.

Corrigé

(a) f\circ f=\mathrm{id}_F montre que f est bijective, de réciproque f.

(b) Si z=f(y), alors f(z)=y et \lbrace z,f(z)\rbrace=\lbrace y,f(y)\rbrace : deux classes sont égales ou disjointes, elles recouvrent F et ont un ou deux éléments. Réciproquement, à une partition en paires et singletons on associe l’involution qui échange les deux éléments de chaque paire et fixe les singletons ; les deux constructions sont réciproques l’une de l’autre.

(c) Le nombre d’involutions d’un ensemble à 10 éléments est donc b_{10}=9496. Parmi les 10!=3\,628\,800 permutations, la probabilité d’en tirer une involution est \dfrac{9496}{3628800}\approx0{,}0026.

7 ▷ (Python) Écrire une fonction b(m) qui calcule b_m par la relation de récurrence, puis vérifier par une boucle que b_{2p}=\sum_{i}\binom{2p}{2i}a_{p-i} pour p\leqslant10.

Indication

Garder les deux derniers termes en mémoire ; comb et factorial du module math.

Corrigé
from math import comb, factorial

def b(m):
    u, v = 1, 2          # b(1), b(2)
    if m == 1:
        return 1
    for k in range(3, m + 1):
        u, v = v, v + (k - 1) * u
    return v

a = lambda n: factorial(2*n) // (2**n * factorial(n))
for p in range(1, 11):
    s = sum(comb(2*p, 2*i) * a(p - i) for i in range(p + 1))
    print(p, b(2*p), s, b(2*p) == s)

Les deux calculs coïncident ; par exemple b_{10}=9496 et b_{20}=23\,758\,664\,096.


Pour aller plus loin

Besoin d’aide sur ce chapitre, ou un concours à viser ?

Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir surveillé — ou l’ambition d’intégrer une grande école : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 25 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca, ou à distance, partout au Maroc et en France.

🎯 Prépas commerciales : réussir les écrits BCE et Ecricome et intégrer les meilleures écoles de commerce (HEC, ESSEC, ESCP…).

Publications similaires