trouver une formule qui donne le nombre de sous ensembles respectant ...

Salut je suis nouveau sur le site et j’aimerai trouver une réponse à un problème de maths que j’ai.

$card(E) = n$, et $X, Y \in P(E)$.

Je dois trouver tous les couples $(X, Y)$ tels que $card(X \cap Y) = 1$.

Je bloque complètement. J’ai fais des diagrammes et j’ai testé des petits cas mais sa devient vite impossible à manager pour $n > 2$. Pour $n = 2$, je trouve $6$.

Avez vous des idées ?

Je vous remercie. Bonne soirée.

Bonne idée, je vais regarder ça et je vais voir ce que je trouve !

Tu sais que : $ n \choose{k}$ représente le nombre de sous-ensembles à $k$ éléments d’un ensemble en bijection avec $[\![ n ]\!]$ (donc qui est de cardinal $n$).

Maintenant, tu peux te poser la question suivante : dans un ensemble à $n$ éléments combien y a t-il de couples disjoints ?

Tu sais que $\mid \mathcal{P}([\![n]\!]) \mid = 2^n$. Maintenant, tu regardes le nombre de sous-éléments de cardinal $k$, il y en a : $n \choose{k}$. Maintenant pour chacun de ces sous-ensembles de $k$ éléments il y en a : $2^{n-k}$ qui sont disjoints (effectivement on enlève $k$ éléments puis on regarde le nombre de parties de ce qu’il reste).

Donc on trouve :

En fait maintenant on a presque résolu le problème puisque se demander le nombre de couples ayant une intersection de card $1$ dans un ensemble de card $n$ revient à se demander, combien il y a de couples disjoints dans un ensemble de card $n-1$ et ensuite on rajoute les $n$ entiers.

Donc sauf erreur j’obtiens comme formule :

Désolé, c’est un peu degueu mais je suis sur portable.

@InaDeepThink : Pour compter le nombre de paires de sous-parties disjointes $A$ et $B$ dans un ensemble à $n$ éléments, on peut voir directement que c’est $3^n$ en disant que pour chaque élément, on a trois possibilités : dans $A$, dans $B$ ou dans aucun des deux.

Ah oui bien vu !