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.

+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