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

a marqué ce sujet comme résolu.
Auteur du sujet

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.

+0 -0

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 :

$$\sum_{i=0}^n {n \choose i }\cdot 2^{n-i}$$

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 :

$$n\cdot \sum_{i=0}^{n-1} {n-1\choose i}\cdot 2^{n-1-i}= n\cdot 3^{n-1}$$

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

Édité par InaDeepThink

+0 -1

@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.

Ceci est une signature tellement longue qu’elle devrait faire plus de deux lignes. Ceci est une signature tellement longue qu’elle devrait faire plus de deux lignes. Ceci est une signature tellement longue qu’elle fait plus de deux lignes. Ceci est une signature tellement longue qu’elle fait plus de deux lignes. Ceci est une signature tellement longue qu’elle fait plus de deux vaches. Ceci est une signature tellement vache qu’elle mange de l’herbe. Ceci est une jolie preuve de l’hypothèse de Rie

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte