COMBINATOIRE
		CORRIGÉ DU DEVOIR DE JANVIER 2006

(1) Soit S la relation d'équivalence engendrée par R. Donc pour A, B
dans P(E), A R B implique A S B. Comme S est réflexive, on a aussi A S
A. Donc S contient la relation T = R U id, la réunion de R et de
l'identité, définie par
	A T B  SSI  A = B ou A R B (c.-à-d. B = E\A).
T suffit-il pour donner tout S ? Il suffit de montrer que T est une
relation d'équivalence. En effet, comme T contient R, elle contiendra
la plus petite relation d'équivalence contenant R, c.-à-d. la relation
d'équivalence engendrée par R, à savoir S ; mais S contient T, on en
déduit ainsi que S = T.

Montrons que T est une relation d'équivalence. Elle est réflexive :
pour A dans P(E), A = A, donc A T A. Elle est aussi symétrique : pour
A, B dans P(E), si A T B, alors A = B ou B = E\A, donc B = A ou 
A = E\B, ainsi B T A. Elle est transitive : pour A, B, C dans P(E), si
A T B et B T C, on a :
	A = B et B = C, 	donc A = C,
ou	A = B et C = E\B,	donc C = E\A,
ou	B = E\A et B = C,	donc C = E\A,
ou	B = E\A et C = E\B,	donc A = C,
ce qui donne A T B dans chaque cas.

(2) (i) On définit
	f : P(E,p) -> P(E\{p}) : X |-> X \ {p},
et
	g : P(E\{p}) -> P(E,p) : Y |-> Y U {p}.
On vérifie que pour X dans P(E,p) (partie de E contenant p) on a
	g(f(X)) = (X \ {p}) U {p} = X
et que pour Y dans P(E\{p}) on a
	f(g(Y)) = (Y U {p}) \ {p} = Y.
Donc g o f est l'identité sur P(E,p) et f o g est l'identité sur
P(E\{p}), ainsi f est une bijection et g est la bijection inverse
(cf. TD 1).

(ii) Pour X dans P(E,p) et Y dans P(E\{p}) avec f(X) = Y et g(Y) = X,
on a card(X) = card(Y) + 1, donc les cardinaux de X et Y sont de
parités opposées. On a ainsi les bijections :

dans P(E,p), de              dans P(E\{p}), de
cardinal pair    <-------->  cardinal impair
                 g        f
dans P(E,p), de  <-------->  dans P(E\{p}), de
cardinal impair              cardinal pair

Comme P(E) est partitionné en deux par P(E,p) et P(E\{p}) (toute
partie de E, soit contient p, soit ne le contient pas), on obtient
ainsi la bijection h : P_P(E) -> P_I(E) :
	X |-> f(X) = X \ {p}	si p appartient à X,
	X |-> g(X) = X U {p}	si p n'appartient pas à X.
En fait, h est l'application X |-> X Delta {p}, où Delta est la
différence symétrique (A Delta B = (A\B) U (B\A)), et la bijection
inverse P_I(E) -> P_P(E) prend la même forme X |-> X Delta {p}.

(iii) card(P(E)) = 2^n et P(E) est la reunion des deux ensembles
disjoints P_P(E) et P_I(E), donc 2^n = card(P_P(E)) +
card(P_I(E)). Comme il y a une bijection entre P_P(E) et P_I(E),
card(P_P(E)) = card(P_I(E)). Aussi card(P_P(E)) = 2^(n-1).

(3) (i) Les conditions nécessaires et suffisantes pour que f soit
idempotente (f o f = f) et Im(f) = S sont :
	C1 : pour x dans S, f(x) = x ;
	C2 : pour x dans E\S, f(x) est dans S .
Nécessaires : Supposons que f soit idempotente et Im(f) = S. Pour x
dans S = Im(f), il existe z dans E tel que f(z) = x ; alors on a f(x)
= f(f(z)) = f(z) = x, donc C1. Pour x dans E\S, on a f(x) dans Im(f) =
S, donc C2.
Suffisantes : Supposons C1 et C2 vérifiées. Pour tout x dans E, soit x
appartient à S et f(x) = x dans S (par C1), soit x appartient à E\S et
f(x) est dans S (par C2), donc de toute manière f(x) appartient à S,
c.-à-d. Im(f) est inclus dans S. Mais pour x dans S, f(x) = x, donc x
appartient à Im(f), c.-à-d. S est inclus dans Im(f). On a ainsi Im(f)
= S, puisque les deux sont inclus l'un dans l'autre. Pour tout x dans
E, comme f(x) appartient à Im(f) = S, par C1 on a f(f(x)) = f(x), donc
f est idempotente.

(ii) Il faut compter les applications f : E -> E vérifiant C1 et
C2. Pour x dans S, f(x) = x, donc le choix de f(x) est unique. Pour x
dans E\S, f(x) est n'importe quel élément S, ce qui donne s
choix. Comme card(E\S) = n-s, on a en tout s^(n-s) choix. Vu d'une
autre manière, une application f : E -> E vérifiant C1 et C2 est
uniquement déterminée par sa restriction à E\S, qui est alors
n'importe quelle application E\S -> S, le nombre de telles
applications étant card(S)^card(E\S) = s^(n-s).

(iii) On suppose n>0. Pour toute application f : E -> E, Im(f) est
non-vide, donc card(Im(f)) est compris entre
1 et n. Pour chaque s = 1, ..., n, le nombre de choix de S avec
card(S) = s est le coefficient binomial de s dans n. Donc par (ii), le
nombre total d'applications idempotentes E -> E est :
	 n
	---
	\   /n\  (n-s)
	/   \s/ s      .
	---
	s=1
(Si on avait n=0, ce nombre serait 1).