Math 15 Minutes - Devenir fort en Maths pour intégrer une prépa scientifique

Formule de Vandermonde – formule du pion et dénombrement

by Michel 2 Comments

La formule de Vandermonde (on dit aussi l’identité de Vandermonde) terminera ce post. Mais l’autre but de cet article est de montrer comment trouver une autre expression de sommes utilisant des coefficients binomiaux par calcul ou par dénombrement.

formule de vandermonde et du pion

Somme des carrés de k parmi n

Calculons :

somme carres k parmi n formule

On sait que :

formule binome newton 1+x

 

 

et que :

formule binome newton 2n

 

 

Exprimons donc en la développant l’expression de (1+x)2n.

1+x puissance 2n

 

 

et :

1+x puissance 2n autrement

 

 

Le produit donne des termes en xn pour les produits des xi et xj avec i+j = n.

Donc le coefficient correspondant à C2nn est la somme des coefficients de tous ces termes correspondant à i+j=n.

On rappelle que les indices dans la notation Cji sont inversés par rapport à la notation avec les parenthèses.

1+x puissance 2n demonstration

 

Remarque : en appliquant l’identité de Vandermonde au triplet (n,n,n) on retrouve cette formule (il faut aussi utiliser Cnk = Cnn-k).

somme carres k parmi n par vandermonde

Identité de Vandermonde

Démontrons l’identité de Vandermonde :

identite vandermonde

Nous allons utiliser une démonstration ensembliste utilisant les dénombrements et cardinalités. Démonstration tirée de cet excellent livre p 456.

Soit E et F deux ensembles disjoints de cardinalité respective p et q, G leur union. G = E ∪ F.

Il y a Cp+qn parties à n éléments dans G (dont le cardinal est p+q).

Parmi ces parties à n éléments on cherche à savoir 
combien il y en a qui contiennent exactement k éléments dans E.


Il y a Cpk façons de choisir k éléments de E.

Une fois choisis il reste n-k éléments à choisir dans F.
Il y a Cqn-k façons.


Au total il y a CpkCqn-k  façons de choisir n éléments dont k sont dans E.

Soit Pk les ensembles de ces parties.

Les ensembles Pk sont disjoints deux à deux (une partie de G ne peut être dans Pk et Pk').

L'union des Pk est l'ensemble des parties à n éléments de G.

Les ensembles Pk forment une partition de l'ensemble des parties à n éléments de G.
Donc,
identite vandermonde demonstration

 

Démonstration par récurrence

Nous allons maintenant démonter la formule de Vandermonde par récurrence.

Initialisation

Pour q=0,

Cqn-k est non nul uniquement pour n=k. En effet Cji est nul quand on n’a pas 0≤i≤j, par convention.

vandermonde recurrence a

C’est donc ok pour q=0.

 

Hérédité

Si la propriété est vérifiée pour q > 0,

si n=0,

vandermonde recurrence heredite a

sinon, grâce à la formule du triangle de Pascal,

vandermonde recurrence heredite b

(1) : d’après l’hypothèse de récurrence appliquée à (p,q,n) mais aussi à (p,q,n-1).

(2) : d’après la formule du triangle de Pascal

 

Autre démonstration de la formule de Vandermonde

Prenons un réel x. Original ! 🙂

(1+x)n+m = (1+x)n(1+x)m

Mais

vandermonde demonstration puissances 1

Or,

vandermonde demonstration puissances 2b

vandermonde demonstration puissances 3b

 

En identifiant les coefficients de même degré des polynômes résultant de (1+x)n+m d’une part et (1+x)n(1+x)m d’autre part, on arrive à la formule de Vandermonde.

vandermonde demonstration puissances 4

En effet, la condition sur les indices i,j>0 et i+j=n se traduit par un seul indice i variant de 0 à n et on remplace j par n-i.

 

Formule du pion

Au passage, et surtout parce que nous allons l’utiliser ci-après… Un petit mot sur la formule du pion. C’est :

formule du pion

Retenons la !

 

Utilisation de la formule de Vandermonde

Nous allons voir comment la formule du pion et la formule de Vandermonde peuvent être utilisées.

Calculons :

vandermonde k seule 2

Utilisons la formule du pion pour extraire p.

vandermonde k seule demonstration-pion

On vérifie que pour n=0, d’une part, et p=0 d’autre part cela marche aussi.

 

 

 

Crédit image : cooldesign à FreeDigitalPhotos.net

Comments ( 2 )

  1. ReplyPierre Cazals
    Je pense qu'une erreur s'est glissée dans la ligne : (1+x)^n(1+x)^n soit la 5ième ligne de calcul. Comme c'est un calcul que je n'arrive pas à comprendre pourriez vous m'aider en rétablissant si besoin la bonne écriture dans la 5ième ligne ou me donner une indication. En tous cas merci de votre site. Pierre Cazals
    • ReplyMichel
      Bonjour, effectivement, une coquille s'est glissée. On ne va pas jusqu'à (n 2n)à mais (n n). J'ai rectifié. Il faudra sans doute faire une refresh de la page. Merci de me l'avoir signalé.

Leave a reply

Your email address will not be published.

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>