Donner une preuve combinatoire de la formule

amafhh

Bonjour,

1) Soit la question "Donner une preuve combinatoire de la formule ..."
Que signifie preuve combinatoire ?
2) Quelle est la différence entre le thème dénombrement et le thème combinatoire ?

Merci pour la réponse

Soc

Il n'y en a pas vraiment, faire de la combinatoire, c'est faire du dénombrement en utilisant les combinaisons, ce qui est à peu près tout le temps le cas.

Typiquement on peut trouver des coefficients de polynômes en comptant le nombre de façons de choisir des parenthèses (comme dans le développement de $(1+X)^n$).

JLT

Pour la n-ième fois :  

Merci de ne pas mettre des points d'exclamation à la fin de chaque titre !!!!!!! A chaque fois je suis obligé de les retirer !!!!!!

Heuristique

Ici, les 2 mots me semblent synonymes.

De manière générale, j'aurais tendance à dire que le dénombrement fait partie de la combinatoire mais que la combinatoire ne se résume pas au dénombrement. Etudier une famille de graphes, c'est de la combinatoire. Compter ses éléments, c'est du dénombrement.

Math Coss

Une preuve combinatoire, c'est une preuve qui est fondée sur un dénombrement plutôt que sur un calcul,  typiquement : il y a telle relation entre ces nombres parce que ces nombres comptent tels objets et qu'il y a telle bijection entre ces objets.
Un exemple, la formule dite du pion ou du capitaine : $k\binom n k =n\binom{n-1}{k-1}$. Une preuve combinatoire consiste à interpréter ces deux produits comme le nombre de couples $(x,A)$ formés d'un élément $x$ et d'une partie $A$ de cardinal $k$ dans un ensemble de cardinal $n$. On peut choisir d'abord $A$ puis un élément de $A$ ou commencer par $x$ puis kes $k-1$ autres éléments de $A$. Une preuve calculatoire se contenterait d'écrire des quotients de factorielles et de simplifier pour identifier les deux membres.