|
#1 - 05-11-2012 14:29:24
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Combintoires, produits et sommes
Salut à tous !
Voilà une petite égalité qui m'est apparue au détour d'un problème, fort élégante et que je ne connaissais pas: [TeX]\sum_{i=0}^nC_a^i*C_b^{n-i} = C_{a+b}^n[/TeX] où [latex]C_y^x[/latex] signifie "nobmre de combinaisons de x éléments parmi y" (Possibilité de vérifier ça ici)
J'en ai trouvé une démonstration plutôt logique, mais pour l'instant aucune démonstration formelle...
#2 - 05-11-2012 14:53:09
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
combinatoiees, produits et sommes
Il suffit d'écrire [TeX](1+x)^{a+b}=(1+x)^{a}\,(1+x)^{b}[/TeX] Ensuite on applique la formule du binôme au 1er membre et aux 2 facteurs du second membre. On regarde le coefficient de [latex]x^n[/latex] dans le 1er membre, puis dans le second membre. Cela donne l'égalité cherchée.
#3 - 05-11-2012 15:16:41
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Cominatoires, produits et sommes
Première démo (logique ?) :
Choisir n entiers dans [1 ; a+b] revient à choisir i entiers dans [1 ; a] et n-i entiers dans [a+1 ; a+b], avec i compris entre 0 et n.
Deuxième démo (formelle ?) : [TeX](x+1)^a=\sum_{i=0}^a{a \choose i}x^i[/latex] et de même [latex](x+1)^b=\sum_{j=0}^b{b \choose j}x^j[/TeX] En effectuant le produit de ces deux expressions, on obtient : [TeX](x+1)^{a+b}=\sum_{i,j}{{a \choose i}{b \choose j}}x^{i+j}[/TeX] D'autre part, on peut également écrire [latex](x+1)^{a+b}=\sum_{k}{a+b \choose k}x^{k}[/latex]
En identifiant les coefficients en [latex]x^n[/latex] de ces polynômes, on obtient : [TeX]\sum_{i+j=n}{{a \choose i}{b \choose j}}={a+b \choose n}[/TeX]
#4 - 05-11-2012 15:25:21
- Azdod
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 763
- Lieu: In this universe ... !!
Combniatoires, produits et sommes
Bonjour Scarta, On peut considérer un groupe de [latex]a [/latex]hommes et [latex]b [/latex] femmes et ainsi calculer le nombre de sous-groupes de taille [latex]n[/latex]. Première méthode : Le nombre de sous-groupe est évidemment une combinaison de [latex]n [/latex]éléments parmi les [latex]a+b[/latex]. Deuxième méthode: On peut tirer 0 hommes et [latex]n[/latex] femmes, 1 homme et [latex]n-1[/latex] femmes ... plus généralement [latex]i[/latex] hommes et [latex]n-i[/latex] femmes. Donc : [TeX]C_a^0 . C_b^n + C_a^1 . C_b^{n-1} ....[/TeX] D'où le résultat
"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"
#5 - 05-11-2012 17:57:27
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
combinatoires, produitq et sommes
Bonjour
En fait c'est assez évident si on se souvient que [latex]C_n^p[/latex] est le nombre de parties à [latex]p[/latex] éléments parmi [latex]n[/latex] . [latex]C_{a+b}^n[/latex] est le nombre de parties à [latex]n[/latex] éléments parmi [latex]a+b[/latex] . Or pour prendre n éléments de [latex]A\cup B[/latex] avec [latex]|A|=a[/latex] et [latex]|B|=b[/latex] il faut en prendre [latex]0[/latex] dans [latex]A[/latex] et [latex]n[/latex] dans [latex]B[/latex] ou [latex]1[/latex] dans A et [latex]n-1[/latex] dans [latex]B[/latex] , ... La formule découle directement de là .
Vasimolo
#6 - 05-11-2012 21:37:23
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Combinatoires, prroduits et sommes
Masab: ça c'est la méthode que je cherchais Vasimolo: ça c'est celle que j'avais. Azdod et titoufred ont les 2
#7 - 07-11-2012 15:55:51
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
Combinatoires, produits et sommess
Je pense que l'on obtient cette égalité en identifiant le coefficient de [latex]X^n[/latex] dans l'égalité [latex](1+X)^a(1+X)^b=(1+X)^{a+b}[/latex].
Le coefficient de [latex]X^n[/latex] dans le membre de gauche s'obtient multipliant 2 à 2 les coefficients des monômes dont la somme des puissances fait n, ce qui donne la somme de produits de gauche et dans le terme de droite, le coefficient de [latex]X^n[/latex] est évidemment [latex]C_{a+b}^n[/latex].
#8 - 07-11-2012 21:10:54
- franck9525
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1935
- Lieu: 86310
Combiantoires, produits et sommes
The proof of the pudding is in the eating.
#9 - 08-11-2012 15:53:26
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
Combinatoirees, produits et sommes
rivas a écrit:Je pense que l'on obtient cette égalité en identifiant le coefficient de [latex]X^n[/latex] dans l'égalité [latex](1+X)^a(1+X)^b=(1+X)^{a+b}[/latex].
Le coefficient de [latex]X^n[/latex] dans le membre de gauche s'obtient multipliant 2 à 2 les coefficients des monômes dont la somme des puissances fait n, ce qui donne la somme de produits de gauche et dans le terme de droite, le coefficient de [latex]X^n[/latex] est évidemment [latex]C_{a+b}^n[/latex].
Une démo parfaite comme j'aime. Simple, évidente quand on la voit.
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#10 - 08-11-2012 22:57:31
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
combinatoires, peoduits et sommes
En effet, très simple quand on y pense Comme d'autres l'ont fait remarquer, on peut aussi considérer que le nombre de manières de prendre n éléments parmi a+b peut être exprimé comme le nombre de manières d'en prendre k parmi un sous ensemble de a éléments et le reste parmi les b restantes, pour toutes les valeurs possibles de k.
Bravo à tous les participants
Mots clés des moteurs de recherche
|
|
Prise2Tete
Forum
Statistiques
Liste des membres
Hall of Fame
Contact
|