↩ Chapitre : Probabilités finies · Sommes et dénombrement (ECG1-ECG2)
Introduction
De combien de façons peut-on répartir
personnes en
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
telles que
.
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
est un ensemble
de parties non vides de
, deux à deux disjointes, de réunion
; ce sont les classes de la partition (l’ordre des classes ne compte pas). Pour
, on note
le nombre de partitions d’un ensemble à
éléments en
paires, et l’on pose
.
Partie I – Partitions en paires
1 ▷ Déterminer
,
,
.
Indication
Pour
, la paire contenant
détermine la partition.
Corrigé
. Pour
:
,
,
:
. Pour six éléments,
choix du partenaire de
, puis
façons de partager les quatre autres :
.
2 ▷ Soit
et
. En distinguant les partitions selon la paire qui contient
, montrer que
. En déduire que
.
Indication
Il y a
choix pour le partenaire de
. Pour la formule close, multiplier et diviser par les nombres pairs.
Corrigé
La paire contenant
est
avec
:
choix. Une fois cette paire fixée, les autres classes forment une partition en paires des
éléments restants :
choix. Ces cas étant disjoints,
.
Par récurrence,
, formule vraie aussi pour
.
Partie II – Partitions en paires et singletons
Pour
, on note
le nombre de partitions d’un ensemble à
éléments en classes qui sont des paires ou des singletons.
3 ▷ Déterminer
,
,
,
.
Indication
Pour
, compter selon le nombre de paires :
,
ou
.
Corrigé
,
(deux singletons, ou une paire),
(trois singletons, ou une paire parmi
). Pour
: aucune paire (
), une paire (
), deux paires (
) :
.
4 ▷ (a) Pour
, en distinguant selon le nombre
de singletons, montrer que
. (b) Établir une formule analogue pour
.
Indication
Le nombre de singletons a la même parité que
. Choisir les éléments seuls, puis une partition en paires des autres.
Corrigé
(a) Si la partition compte
singletons, on choisit ces
éléments (
choix), puis une partition en paires des
autres (
choix). En sommant sur
:
.
(b) Pour
, le nombre de singletons est impair, égal à
:
. Vérification :
.
5 ▷ Soit
et
. En distinguant selon la classe qui contient
, montrer que
. Calculer
pour
.
Indication
La classe de
est soit
, soit une paire
.
Corrigé
Si
est une classe, les autres classes forment une partition convenable des
éléments restants :
cas. Sinon la classe de
est
(
choix de
) et les autres classes forment une partition convenable des
éléments restants :
cas. D’où
.
Avec
et
:
,
,
,
,
,
,
,
. Contrôle par 4(a) :
.
Partie III – Involutions
6 ▷ Une application
est une involution si
. (a) Montrer qu’une involution est bijective. (b) À une involution
, on associe la partition de
en classes
. Montrer que c’est une partition en paires et singletons, et que l’on définit ainsi une bijection. (c) Combien un ensemble à
éléments possède-t-il d’involutions ? Quelle est la probabilité qu’une permutation de
choisie au hasard soit une involution ?
Indication
(b) Les classes
ont un ou deux éléments, et
. Réciproquement, une partition en paires et singletons définit
: échanger les éléments de chaque paire, fixer les singletons.
Corrigé
(a)
montre que
est bijective, de réciproque
.
(b) Si
, alors
et
: deux classes sont égales ou disjointes, elles recouvrent
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 à
éléments est donc
. Parmi les
permutations, la probabilité d’en tirer une involution est
.
7 ▷ (Python) Écrire une fonction b(m) qui calcule
par la relation de récurrence, puis vérifier par une boucle que
pour
.
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
et
.
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…).
