Dénombrer l'ensemble des parties de E excluant m paires d'éléments identiques

GuydeSaint-Hilaire

Bonjour

Mon problème est la suivant.

Soit $E_{3}=\{P,C,L\}$ un ensemble à $ k=3$ éléments, et $P(E_3)$ l'ensemble des parties de $E_3$.

1) Supposons $ C=L$ , deux éléments de $E$ identiques. Je cherche à dénombrer toutes les parties de E ne contenant pas $C,L$ . Je note $ A^1_3 ⊂ P(E_3)$ cet ensemble. En faisant le dénombrement à “la main”, je trouve son cardinal $ |A^1_3|=6$. En procédant de la même manière, j'obtiens $|A^1_2| =3$ . En augmentant l'ensemble $ E$ du nombre d'éléments nécessaires (avec la contrainte que seuls $C,L$ sont identiques), j'obtiens $|A^1_4| =12, |A^1_5|=24$ ... ce qui suggère la relation suivante: $| A^1_ k| =| A^1_2| 2^{k-2}$, pour $k ≥ 2$ .

2) Supposons maintenant que l'on ait $E$ tel que 2 paires d'éléments sont identiques. En procédant de la même façon, j'obtiens $|A^2_4|=9$ et $ |A^2_k|=|A^2_4| 2^{k-4} - \left\lfloor 2^{k-6}\right\rfloor$, pour $k ≥ 4$ .

Je ne sais pas si j'ai été très clair jusqu'ici ...

Mais j'aimerais pouvoir aller au delà de ces simples conjectures et généraliser ces résultats pour calculer $|A^m_k|$ , avec $m$ paires d'éléments identiques ($m<k$ ) ... L'analyse combinatoire doit surement être triviale, mais pour le moment je sèche.

En vous remerciant d'avance pour vos lumières !!

GaBuZoMeu

Bonsoir

Pas très clair pour moi.

Je sais à peu près le début : tu comptes le nombre de parties d'un ensemble à $k$ éléments qui ne contiennent pas une paire fixée. Bon, compter celles qui contiennent cette paire revient à compter le nombre de parties d'un ensemble à $k-2$ éléments.

Mais après, ça se gâte. Qu'est-ce que tu comptes exactement ?

GuydeSaint-Hilaire

Bonsoir,

Voila, comment je procède "à la main": je commence par écrire toutes les parties qui forment $P(E_k)$ (y compris celles qui contiennent la paire fixée). Ensuite, je supprime toutes celles qui contiennent la paire en question.  Ce qui me donne mon ensemble $A_k$. Je n'ai plus qu'a compter le nombre de parties pour obtenir $|A_k|$. Donc je compte toutes les parties qui ne contiennent pas ma paire (mon triplet, ou mon n-uplet) fixée. 

GaBuZoMeu

Toujours pas compris ton 2).

lourrran

Quand tu dis : on veut exclure $m$ paires ... précise un peu. 

J'ai un ensemble $E$ avec $n$ éléments, dont $m$ paires.
Je regarde une partie de $E$.
Interprétation n°1 :  si cette partie de $E$ ne contient aucune des $m$ paires, alors cette partie est considérée comme 'Ok'
Interprétation n°2 :  si cette partie de $E$ contient éventuellement certaines paires, mais ne contient pas toutes les $m$ paires, alors cette partie est considérée comme 'Ok'

Et évidemment on cherche à comptabiliser les parties qui sont 'Ok'.

Dans le cas où on a $m=1$, c'est flagrant que c'est très facile de compter les parties qui sont 'pas-Ok', comme déjà dit. Puis de faire la soustraction.
Pour $m>1$, si c'est l'interprétation n°1, ça se gâte. Si c'est l'interprétation n°2, c'est très simple.

GuydeSaint-Hilaire

Dans le 2, je prends un ensemble $E$ à $k\geq 4$ éléments et je fixe "2 paires (soit 4 éléments). Et comme dans le 1), je compte toutes les parties de $E_{k\geq 4}$ qui ne contiennent pas les 2 paires fixées.

Je commence par compter les parties formant $A_4$, puis celles formant $A_5$, et ainsi de suite ...

GuydeSaint-Hilaire

@lourran. Malheureusement, c'est l'interpretation 1.

Mes 2 (ou 4, ou m) éléments identiques ne doivent être présents (ensembles) ni dans une paire, ni dans un triplet, ni dans un quadruplet, ...

lourrran

Tu écris : qui ne contiennent pas les 2 paires fixées.
Mais, ensuite, tu dis que c'est l'interprétation n°1, et donc : qui ne contiennent aucune des 2 paires fixées. 
J'espère que tu vois bien à quel point ta formulation est ambiguë.

Regarde 'le crible de Poincaré' ; tu devrais trouver la réponse à ta question.