Calcul de combinaisons

La première idée de GBZM est la bonne, déjà pour restreindre l’intervention de l'indice variable $k$. Un changement d'indice $j:=m-1+k$ met la somme sous la forme : $\displaystyle \sum_{j=m-1}^{m+n-1} \begin{pmatrix}j\\m-1\end{pmatrix}\begin{pmatrix} n+m+i-j\\ i-1\end{pmatrix}$, qui est égale à : $\displaystyle \sum_{j=0}^{m+n+i} \begin{pmatrix}j\\m-1\end{pmatrix}\begin{pmatrix} n+m+i-j\\ i-1\end{pmatrix}$.

Or on a la formule : $\displaystyle \sum_{j=0}^{q} \begin{pmatrix}j\\r\end{pmatrix}\begin{pmatrix} q-j\\s\end{pmatrix}$$=\begin{pmatrix} q+1\\r+s+1\end{pmatrix}$, quels que soient $q,r,s$ entiers naturels. C'est pourrait-on dire la formule d'anti-Vandermonde (faute d'appellation plus pertinente), qui peut se démontrer par récurrence, ou bien au moyen de la fonction génératrice : $\displaystyle \sum_{n=0}^{+\infty} \begin{pmatrix}n\\a\end{pmatrix}x^n=x^a (1-x)^{-a-1}$, pour tout $a \in \mathbb N$. GBZM semble dire qu'il y a aussi une démonstration combinatoire pour cette formule, c'est pour moi une bonne nouvelle.

Bonne et belle et chaude journée.
Fr. Ch.
08/06/2021

Non seulement je semble dire qu'il y a une démonstration combinatoire, mais je le dis ! Et je donne même une énorme indication qui devrait te la faire trouver sans peine, Chaurien.

Comme GaBuZoMeu j'aime bien les démonstrations combinatoires.

Dans le cas de la formule "anti-Vandermonde" j'ai une préférence pour la démonstration donnée par Cidrolin il y a 9 années dans le fil suivant : Coefficient binomial.

J'avais écrit la formule sous la forme $\displaystyle\sum_{k=0}^n {a+n-k\choose a}{b+k\choose b}={a+b+n+1\choose n}$.

En effet, la formule « anti-Vandermonde » sous cette forme donne tout de suite la solution.

Il est vrai que la démonstration combinatoire est la meilleure car elle exprime en fait la nature profonde du problème. Il me semble qu'on l'appelle aussi « preuve par bijection ». Je crois savoir qu'il existe des identités dont on n'a pas la démonstration par bijection, mais qu'on sait prouver autrement.

Pour cette formule-ci, j'avais signalé une démonstration par récurrence dans ce fil : http://www.les-mathematiques.net/phorum/read.php?18,1366700,1378710#msg-1378710. Elle est un peu trop laborieuse.

Je me satisfaisais de la démonstration par fonction génératrice, car pour $a \in \mathbb N$.et $n \in \mathbb N$, on a : $(-1)^n(_{~~~~~n}^{-a-1})=(_{~~~a}^{a+n})$. Par suite : $\displaystyle (1-x)^{-a-1}=\sum_{n=0}^{+ \infty} (_{~~~a}^{a+n})x^n$, et le produit de Cauchy conduit à la formule en question : $\displaystyle \sum_{k=0}^{n} (_{~~~a}^{a+k}) (_{~~~~~b}^{b+n-k}) = (_{~~~a+b+1}^{a+b+1+n})$.
Dans les classes où les séries et/ou leur produit de Cauchy ne sont pas au programme, par exemple en prépa-HEC, on peut démontrer ceci avec des développements limités. Si la démonstration combinatoire est plus profonde, la démonstration par fonction génératrice est plus rapide.

Maintenant, ce serait bien de trouver une autre appellation pour cette formule « anti-Vandermonde ». Un copain l'appelle Ednomrednav, en zorglangue, mais je trouve que ce n'est pas sérieux.

Bonne soirée.
Fr. Ch.

Je voudrais prolonger la remarque de Jandri.

$\bullet$ Je rappelle la définition des coefficients binomiaux généralisés pour $x \in \mathbb C$ et $n \in \mathbb N$ : $\displaystyle { x\choose n} :=\frac 1{n!}$$ x(x-1)...(x-n+1)$
(en particulier ${x\choose 0}:=1$).

$\bullet$ La formule de Vandermonde classique, pour $x \in \mathbb C$ et $y \in \mathbb C$ et $n \in \mathbb N$, est : $\displaystyle\sum_{k=0}^n {x\choose k}{y\choose n-k}={x+y\choose n}$.
Si $x$ et $y$ sont des entiers naturels, les coefficients binomiaux ont une interprétation combinatoire bien connue, et on a une démonstration combinatoire de cette formule, et même plusieurs, trajets sur un quadrillage ou bien parties d'un ensemble. Ou bien une démonstration par récurrence, moins jolie. Ou les fonctions génératrices (série ou développement limité).
Si $x$ et $y$ sont des réels ou des complexes quelconques, pas d'interprétation combinatoire pour les coefficients binomiaux, il reste les fonctions génératrices.
Mais on peut penser à une autre démonstration, car l'identité à prouver concerne une fonction polynomiale de $x,y$. Si elle a été démontrée, de quelque façon, pour $x,y$ entiers naturels, ensemble infini, elle se trouve vraie pour $x,y$ réels ou complexes quelconques, par prolongement des identités polynomiales.

$\bullet$ Maintenant, une simple inversion de l'ordre des facteurs du numérateur nous montre que : $\displaystyle { -x-1\choose n} = (-1)^n {x+n\choose n}$.
Alors la formule de Vandermonde classique : $\displaystyle\sum_{k=0}^n {-x-1\choose k}{-y-1\choose n-k}={-x-y-2\choose n}$ devient immédiatement la formule donnée par Jandri :
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\displaystyle\sum_{k=0}^n {x+k\choose k}{y+n-k\choose n-k}={x+y+n+1\choose n}$.
Et alors, en faisant $x:=m-1$ et $y:=i-1$, on a tout de suite l'égalité demandée au début de ce fil.
Par ailleurs, la formule de Vandermonde sous cette deuxième forme est utile dans certains calculs d'espérance et variance de certaines variables aléatoires discrètes.

Bonne journée.
Fr. Ch.
09/06/2021