Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #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...

  • |
  • Répondre

#0 Pub

 #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 smile


"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 smile

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 smile
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

Formule de Van der Monde, dernière page tongue


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 smile
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

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete