Calcul de combinaisons
Avez-vous des idées pour montrer cette égalité : pour $n, m,i >0$
Réponses
-
Bonjour, Il semble être une extension de Identité de Vandermonde.
-
J'ai déjà pensé à utiliser l'identité de Vandermonde mais ça ne marche pas.
-
Bonsoir,
Est-ce que sous la forme
$$ \sum_{k=0}^n \begin{pmatrix}m-1+k\\m-1\end{pmatrix}\begin{pmatrix} n+i-1-k\\ i-1\end{pmatrix}= \begin{pmatrix} m+n+i-1\\m+i-1\end{pmatrix}$$
cette égalité t'inspire plus ? (Deux façons de compter le nombre de parties à $m+i-1$ éléments de l'ensemble $\{1,2,\ldots,m+n+i-1\}$ .) -
Bonsoir,
La première façon est très simple mais la deuxième qui contient la somme n'est pas claire pour moi (surtout la décomposition). -
Indice : dans une partie à $m+i-1$ éléments rangée dans $\{1,\ldots,m+n+i-1\}$, il y a le $m$-ème élément de cette partie .... avec $m-1$ avant et $i-1$ après.
-
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 -
L’ « anti-Vandermonde plus un ». :-D
-
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.
-
Très bien, comme d'habitude les Trois Démonstrations : récurrence, fonctions génératrices, combinatoire.
Mais à la relecture, je ne suis pas certain que mon message précédent soit totalement correct : pour l'égalité des sigmas, un terme correctif est sans doute nécessaire. -
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}$. -
Merci pour vos réponses.
-
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. -
Pour compléter ce qu'a écrit Chaurien on peut remarquer que la formule s'étend à $a$ et $b$ nombres complexes si on l'écrit sous la forme :$$\displaystyle\sum_{k=0}^n {a+k\choose k}{b+n-k\choose n-k}={a+b+n+1\choose n}$$
-
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 -
Bonjour
Concernant la preuve combinatoire dont fait allusion Math Coss, on peut se ramener pour la formule de Vandermonde, à un tirage de boules dans une urne qui contient $a$ boules blanches et $b$ boules rouges. Il s'agira d'en tirer $n$ boules de l'urne. L'égalité avec la manipulation de la somme s'établit donc par double comptage.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.1K Toutes les catégories
- 60 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres