Inscription / Connexion Nouveau Sujet
Formule du crible
Bonjour tout le monde,
svp, j'ai une petite question...
Je n'arrive pas à comprendre la formule du crible:
et je n'arrive pas à l'appliquer par exemple à 3 ensembles: ,
et
Merci d'avance pour votre aide 
pour deux ensembles, oui, je la connais
mais comment tu as pu faire pour 3? (je ne suis pas vraiment habitué à la notation )
merci
Bonjour,
Trois présentations équivalentes de la formule du crible :
Soit ensembles
, ...,
.
(1)
(C'est celle de ton message)
(2)
où la somme est prise sur les
sous-ensembles de
de cardinal
.
(inspirée de Sheldon Ross, A first course in probability)
D'où une transformation de ton expression de départ :
(3)
où la somme est prise sur les
sous-ensembles de
de cardinal
.
Récurrence sur ?
Nicolas
Salut Nicolas 
Les deux autres sont vraiment trop longues et leur faut une heure pour acquérir le principe.. 
sinon, si on veut appliquer la première "présentation" pour ?
La présentation (2) permet d'écrire immédiatement :
Essaie de voir le lien avec ta formule.
Sauf erreur.
Pour comprendre dans le cas I = |[1,2,3]|, je te suggère de ne pas partir de (1), mais de (3), qui se déduit immédiatement de (1).
J'étais en train de me dire que j'avais déjà vu cette formule deux fois, mais sous deux autres noms : "formule de Poincaré" et "Sieve formula". Un coup de Google et de dico m'a ouvert les yeux
N'empêche, écrire un message là-dessus, c'est immonde.. toutes ces balises, ouille (suis pas encore très douée non plus faut dire ) !
Critou contente que monrow ait vu l'astuce, du coup
FF> le superlatex me fait peur... ça fait plus de 20 minutes qu'il écrit.. Donc, 2 ou 3 pages en beau latex ....
Le plus adéquat, c'est que tu mets ce topic dans le chapitre "latex"
(en faite je peux aider pour le tri 
)
On va montrer la formule (3) (qui est quasiment la même que celle de ton message initial) .
Attachons nos ceintures. Rien de compliqué, mais... de la lourdeur. J'ai volontairement beaucoup détaillé.
Voici l'hérédité...
On utilise la formule des 4 cardinaux :
On développe le troisième terme :
On applique l'hypothèse de récurrence sur les premier et troisième termes :
On distribue et simplifie le dernier terme :
Dans le dernier terme, on isole le terme :
Dans le troisième terme, on fait le changement de variable :
Dans le troisième terme, on remplace par
:
Dans le premier terme, on isole l'indice :
On regroupe avec ses amis :
On regroupe les deux sommes ensemble :
On s'aperçoit alors avec bonheur que la combinaison des deux sommes séparées par un correspond bien à une sommation sur l'ensemble des sous-ensembles de |[1;n+1]| de taille r : la première somme correspond aux sous-ensembles ne contenant pas (n+1), et la seconde aux sous-ensembles contenant (n+1) :
On corrige le tout dernier terme :
C'est-à-dire :
CQFD
Sauf erreur.
Nicolas
Après cet effort, je vais me coucher. 
Sérieusement, la meilleure façon de "visualiser" ta formule (1) est de la mettre sous la forme (3).
La forme (3) est exactement la même que (2), mais si (2) te semble hermétique, laisse-la tomber.
Nicolas
Un double sigma en prenant un exemple un peu plus simple , mettons :
Cette somme signifie :
Est-ce que tu le vois mieux comme ça ?
Le double sigma, c'est juste une "somme de sommes", en fait. Sauf que dans le deuxième sigma, en "paramètres", on peut se servir des paramètres du premier (dans mon exemple, dans le deuxième sigma on se sert de k, qui est défini dans le premier). Ça simplifie l'écriture (va chercher une écriture passable avec un seul sigma pour exprimer
)
Suis pas sûre que ce soit très clair tout ça 
bonsoir à tous et à toutes !
j'ai bien compris pour 2 et trois ensembles à calculer card([A]grandinter[/B]grandinter[/C]) je m'embrouille pour le faire pour 4 ensembles A,B,C,D
merci de bien vouloir m'aider
A 
B
Annuler
connectez vous
algèbre en post-bac