Formule du crible

par **Ariarty** » 26 Nov 2011, 16:11

Bonjour,

J'aurais besoin d'aide pour comprendre la formule du crible (ou de Poincaré) en dénombrement. J'ai du mal à comprendre son application. Je vous donne un exemple.

On se place dans la situation suivante :

On a n lettres et n enveloppes, et on veut mettre les n lettres dans les n enveloppes de telle sorte que au moins une lettre arrive à son destinataire.
Si on appelle Ak l'ensemble des façons qu'il y a de mettre n lettres dans n enveloppes de telle sorte que k lettres arrive à son destinataire, on peut répondre à la question posée en calculant :

card(A1UA2U...UAn)

en utilisant la formule du crible donc.

Mais dans la formule du crible, il y a de nouveaux ensembles A indicés i1,i2,...,ik

Et j'ai du mal à comprendre à quoi correspond l'intersection de ces Aik dans la formule, même dans cette situation particulière.

Si quelqu'un pouvait m'expliquer comment comprendre la formule...

Voilà, merci !

par **nodjim** » 26 Nov 2011, 16:14

Question bête :qu'est ce qui t'empêche de mettre la lettre dans l'enveloppe correspondante ?

par **Ariarty** » 26 Nov 2011, 16:18

Hum, je me suis posé la même question quand je suis tombé sur cet exo en colle, mais je suppose qu'on se place dans la situation où l'on est un imbécile fini qui n'a aucun problème à placer une lettre destinée à X dans l'enveloppe pour Y, mais bon...

par **Doraki** » 26 Nov 2011, 16:26

dans la définition de Ak (donnée par l'énoncé ?) c'est "exactement k lettres sont bien mises" ou "au moins k lettres sont bien mises" ?

par **Ariarty** » 26 Nov 2011, 16:31

L'énoncé se limitait à la question posée.

Il est possible que j'ai mal compris, mais j'avais compris les Ak comme étant "exactement k lettres arrivent à leur destinataire", si bien que l'union de ces ensembles répondaient à "au moins une lettre arrive". Mais encore une fois j'ai pu mal comprendre...

par **Doraki** » 26 Nov 2011, 16:39

Ben dans ta situation, les ensembles Aik sont tous vides, mais l'ennui c'est que c'est plutôt difficile de calculer la taille des Ak.

La formule du crible c'est pour calculer un truc compliqué en utilisant des trucs qu'on sait calculer.
Si tu décompose ton ensemble avec des trucs que tu ne sais pas calculer, ça ne sert à rien.

Si tu changes le "exactement k" en "au moins k", la taille des Ak devient facilement calculable, mais par contre les intersections sont pas forcément vides (mais leur taille reste aussi facilement calculable, donc tout va bien).

par **Ariarty** » 26 Nov 2011, 16:42

Alors j'ai dû mal comprendre. Mais pourriez-vous m'expliquer pourquoi l'intersection des ensembles Aik serait vide si c'était "exactement k lettres arrivent" ? Comme je l'ai dit, je n'ai justement pas compris à quoi correspondait cette intersection...

Merci !

par **Doraki** » 26 Nov 2011, 16:47

Ben par exemple A1 inter A2 c'est l'ensemble des manières de mettre n lettres dans n enveloppes tel qu'il y ait exactement 1 personne qui reçoive sa lettre et tel qu'il y ait exactement 2 personnes qui reçoivent leur lettre.
Comme 1 est différent de 2, il n'y a aucune manière de mettre n lettres dans n enveloppes tel qu'il y ait exactement 1 personne et exactement 2 personnes qui reçoivent leur lettre.
Donc A1 inter A2 est l'ensemble vide.

par **Ariarty** » 26 Nov 2011, 16:57

Mais justement, les ensemble Aik sont différents des ensembles Ak. Les ensembles Aik ne correspondent donc pas aux façons qu'il y a de mettre n lettres dans n enveloppes telles que k lettres arrivent à leur destinataire. Et je comprends alors pas à quoi ces Aik correspondent...

par **Doraki** » 26 Nov 2011, 17:02

si ton cours parle d'ensembles Aik sans dire ce que sont ces ensembles, c'est que tu l'as mal recopié ou qu'il est super mal fait.
http://fr.wikipedia.org/wiki/Principe_d'inclusion-exclusion

par **Ariarty** » 26 Nov 2011, 17:27

Mais les ensembles du membre gauche de la formule et ceux de droite ne sont pas indicés pareil, ce ne sont pas les mêmes donc si ?

par **Doraki** » 26 Nov 2011, 17:34

Je vois pas le problème.
Regarde la première version de la formule.

|A1 union A2| = |A1| + |A2| - |A1 inter A2|
|A1 union A2 union A3| = |A1| + |A2| + |A3| - |A1 inter A2| - |A1 inter A3| - |A2 inter A3| + |A1 inter A2 inter A3|
etc.

Dans les autres versions, Ai1 c'est A indice (i indice 1) où (i indice 1) est un nombre qui varie comme marqué dans la somme. A chaque somme tu fais varier k indices en même temps, i1, i2 ... ik

par **Ariarty** » 26 Nov 2011, 17:38

Donc les indices servent juste à introduire la somme ?

la somme qui fait varier les k indices i1,i2,...,ik revient à la somme allant de i=1 à k des Ai ?

Merci.

par **Doraki** » 26 Nov 2011, 19:58

Non c'est la somme qui dit quels sont les indices que tu prends.

Pour n=3 et k=2 par exemple, quand tu lis "somme pour 1<= i1 < i2 <= 3 de |Ai1 inter Ai2|",
d'abord tu fais la liste de tous les couples (i1,i2) qui interviennent dans la somme (les couples i1,i2 tels que 1 <= i1 < i2 <= 3),
(i1 = 1, i2 = 2)
(i1 = 1, i2 = 3)
(i1 = 2, i2 = 3)

puis pour chaque couple (i1,i2) tu ajoutes le terme |Ai1 inter Ai2|
Pour cette somme-là, ça donne |A1 inter A2| + |A1 inter A3| + |A2 inter A3|.

par **Ariarty** » 26 Nov 2011, 22:28

Oui j'ai bien compris cette application directe purement calculatrice, mais dans la situation que j'ai énoncée, j'ai du mal à comprendre.

A quoi correspond cette intersection des Aik, en supposant que les Ak soient l'ensemble des façons qu'il y a de mettre n lettres dans n enveloppes telles qu'au moins k lettres arrivent ?

Formule du crible

Formule du crible

Qui est en ligne