Une somme

Cidrolin

Simplifier : $\displaystyle \sum _{i=0} ^p \binom{n-m+i-1}{i} \binom{m+p-i-1}{p-i} $

nicolas.patrois

C’est un produit scalaire de vecteurs du plan ? :-D

Cidrolin

Non ce sont des coefficients binomiaux.

samok

$p$ fois le vecteur $(n+p-2,p)$ mort de lol ?

S

Fin de partie

Cidrolin:

Je pense que Maxima aide à calculer cette somme.

Si je lui demande,

Zeilberger((binomial(n-m+i-1,i))*(binomial(p+m-i-1,p-i)),i,p);

Il me renvoie $\frac{i\, \left( p+m-i\right) }{p-i+1},[p+n,-\left( p+1\right)]$

(voir la signification ici, http://maxima.sourceforge.net/docs/manual/de/maxima_77.html , cela permet, en principe, de transformer la somme d'origine en une somme qui se télescope. J'ai la flemme de faire les calculs tout de suite maintenant)

PS:
On peut voir la même méthode utilisée, mais sur un exemple plus simple, ici:
http://www.les-mathematiques.net/phorum/read.php?5,1578732,1579794#msg-1579794

Fin de partie

En fait, Wolfram indique que c'est égal à $\dfrac{(n+p-1)!}{(n-1)!p!}=\binom{n+p-1}{p}$

Mais comme il indique un résultat pendant quelques secondes avant de finalement rien renvoyer (l'écran est changé avant que tu aies le temps de noter, heureusement il y a f5) ce résultat n'est peut-être pas exact (et j'ai la flemme de "vérifier" numériquement).


PS:
J'ai procédé à quelques "vérifications" numériques et ça à l'air de marcher.

Cidrolin

Oui bravo Fin de partie.
Ma démonstration (voir demain) utilise les fonctions arithmétiques. En fait je retrouve des identités binomiales avec la convolution de Dirichlet. Certaines bien connues, d'autres moins. Par exemple si $n=p_1p_2\cdots p_k$ alors le nombre de diviseurs de $n$ est $(1+1)(1+1)\dots (1+1)$ soit $2^k$. On choisit un diviseur de $n$ en prenant $i$ facteurs parmi les $p_1,p_2,\cdots ,p_k$, il y a $\binom ki$ façons. On a donc $\sum _0 ^k \binom ki=2^k$.

Fin de partie

Ces sommes, comme déjà indiqué, Maxima par des méthodes de "creative telescoping" peut aider à les calculer.
Il renvoie un truc qui joue le rôle d'une primitive quand on veut calculer une intégrale.
Il faut évaluer cette "primitive" en des valeurs ce que Maxima ne fait pas tout seul, ou bien je ne sais pas comment on est censé faire pour qu'il fasse tout le boulot (et qui est pénible à faire)

Cidrolin

Notons ${\Large \mathbf{1}}$ la fonction qui à tout $n \in \N^*$ associe $1$, et soit $q$ un nombre premier.

On a ${\Large \mathbf{1}} \star {\Large \mathbf{1}} (q^a)=\tau (q^a)=a+1$, c'est le nombre de diviseurs de $q^a$.

Par récurrence, il vient : ${\Large \mathbf{1}} \star {\Large \mathbf{1}} \cdots \star {\Large \mathbf{1}}(q^a)={\Large \mathbf{1}}^n(q^a)=\binom {n+a-1}{a}$.

De l'égalité ${\Large \mathbf{1}} ^n={\Large \mathbf{1}} ^{n-m} \star {\Large \mathbf{1}} ^m$, remplaçons $a$ par $p$, on déduit :

$$\binom {n+p-1}{p}=\displaystyle \sum _{i=0}^p \binom {n-m-1+i}{i} \binom {m+p-i-1}{p-i}$$

claude quitté

Bonjour Cidrolin,

Ah, les coefficients binomiaux, on pourrait y passer toute sa vie. Hier soir, j'ai cherché ta somme et j'ai trouvé la réponse dans GKP (Graham, Knuth, Patashnik), Concrete Mathematics. Tu connais probablement ? Le chapitre 5 ``Binomial Coefficients'' fait un peu près 100 pages et ce qui nous concerne est la la page 169. Il y a un tableau avec 5 identités (Sums of products of binomial coefficients). Je t'en touche 2 mots si tu permets. La première chose que mentionnent les auteurs, c'est de ne pas apprendre par coeur ces identités mais de voir comment on peut les déduire de la première qui est :
$$
\sum_k \binom{r}{m+k}\binom{s}{n-k} = \binom{r+s}{m+n} \qquad \qquad \hbox {(Vandermonde's convolution)}
$$
En passant, la philosophie des auteurs (spécialistes du sujet) est de ne pas mentionner le lieu de variation de l'indice, ici $k$, quand cela est pris en charge de manière automatique par les coefficients binomiaux eux-mêmes. Ici quand $k$ devient trop négatif, $\binom{s}{n-k}$ est nul et quand $k$ devient grand, $\binom{r}{m+k}$ est nul. Bref, la somme ci-dessus est finie.

La preuve de cette identité consiste à remplacer $k$ par $k-m$ puis $m+n$ par $n$ :
$$
\sum_k \binom{r}{k}\binom{s}{m+n-k} = \binom{r+s}{m+n} \quad \hbox {ou encore} \quad
\sum_k \binom{r}{k}\binom{s}{n-k} = \binom{r+s}{n} \
\quad\hbox {(Vandermonde's convolution variante)}
$$
Et l'égalité de droite se déduit de l'examen du coefficient de $X^n$ dans $(X+1)^r (X+1)^s = (X+1)^{r+s}$.

Et il paraît, je n'ai pas pris le temps de le faire (c'est pas bien) que l'on en déduit (c'est la dernière identité du tableau)
$$
\sum_{h=0}^a \binom {a-h}{q}\binom{b+h}{r} = \binom {a+b+1}{q+r+1}, \qquad \fbox {$r \ge b$}
\qquad\qquad (\heartsuit)
$$
J'ai changé complètement les lettres de façon, à ce qu'en cas de besoin, on puisse faire des changements de variables. Et il faut noter les contraintes, ce qui fait qu'une telle identité $(\heartsuit)$ est moins belle que la première identité là-haut.

Rapport avec la choucroute ? J'y viens. Toi, je pense que tu vas te reconnaître :
$$
\binom{n-m+i-1}{i} \binom {m+j-1}{j} \quad \hbox {avec $i+j = p$} \qquad \hbox {pareil que} \qquad
\binom{n-m+i-1}{n-m-1} \binom {m+j-1}{m-1}
$$
Et en regardant bien (en bas des coefficients binomiaux, c'est fixe maintenant), on peut alors utiliser $(\heartsuit)$ pour en déduire ta somme. En n'oubliant pas que $(n-m+i-1) + (m+j-1) =
(n + p-1) - 1$. Ouf !

Mais pourquoi je te raconte tout cela? Eh bien, avec tout le respect que je te dois, je trouvais que ton identité, ta somme si tu veux, elle manquait un tantinet de symétrie. Question de goût bien entendu.

Cidrolin

Merci Claude.

Je retrouve effectivement Vandermonde dans ce qui suit:

Notons $\mu$ la fonction de Möbius, on a $\mu ^n(q^a)=(-1)^a \binom{n}{a}$

L'égalité $\mu ^n(q^a)=\mu ^{n-m} \star \mu ^m(q^a)$ donne:

$$\binom{n}{a}=\displaystyle \sum _{i=0}^a \binom{n-m}{i} \binom{m}{a-i}$$.

NB $\quad q$ est premier et $\mu ^n$ vaut $\mu \star \mu \dots \star \mu\quad $,$n$ fois

claude quitté

Cidrolin,

On a l'impression que tu utilises la lettre $q$ pour un premier générique, comme si c'était une indéterminée. Et du coup, tu piques ma curiosité. Car je ne peux pas m'empêcher de penser à toutes ces choses que je ne connais pas : $q$-calcul, $q$-séries génératrices ...etc...

Et comme je suis trop vieux, c'est trop tard. Je veux dire par là, que je ne peux pas me permettre de tirer sur une imprimante les 362 pages de combinatoire de Foata & Hanhttp://irma.math.unistra.fr/~guoniu/papers/p55lectnotes1.pdf dans lesquelles, un chapitre entier est consacré aux $q$-objets.

Où les ranger ces pages tirées ? Quand trouver le temps de les lire ? Ok, c'est mon problème tu vas me dire (et c'est pas faux).

Sauf que toi Cidrolin, tu as utilisé la lettre $q$ et pas la lettre $p$. Et peut-être alors que tu es au courant de ces $q$-choses ? Et qu'en quelques mots (sans pointer sur wikipedia comme font trop souvent certains ou me renvoyer à un pdf de 500 pages), tu pourrais me dire ce qu'il en est, juste sur ton exemple ?

Je $q$-rêve ?
En tout cas merci.

Cidrolin

J'ai utilisé $q$, mais $1789$ ou $p$ faisait l'affaire. Je ne sais rien de ces $q-$choses, rien de ces histoires de $q$.

LOU16

Bonjour à tous
Dit autrement (mais c'est surtout histoire de m'exercer au Latex):
L' égalité $\displaystyle{\binom{n+p-1}{p}\:=\:\sum_{i=0}^{p} \binom{n-m+i-1}{i}\binom{m+p-i-1}{p-i}}$("de convolution") proposée exprime aussi simplement le fait que les coefficients de $X^p$ dans les séries formelles (ou entières, comme on voudra) $~\dfrac{1}{(1-X)^n}~$ et $~\dfrac{1}{(1-X)^m}\cdot\dfrac{1}{(1-X)^{n-m}}~$ sont égaux.

Amicalement.

Cidrolin

Oui LOU16, les séries de Bell permettent de retrouver bien de mes "résultats".

claude quitté

@Cidrolin
J'ai dû être $q$-troublé. Car $q$ n'intervient pas dans le membre droit. Mais on apprend toujours des choses avec des gens de bonne volonté, n'est ce pas ? Par exemple, j'ai appris que 1789 est un nombre premier ; il y a un autre nombre, mais moins connu : il s'agit de 1951, qui est premier. Le savais tu ?

Cependant, je ne peux pas m'empêcher de contempler :
$$
{\bf 1}^{\star n}(q^a) = \binom {n+a-1}{a}, \qquad\qquad \mu^{\star n}(q^a) = (-1)^a \binom {n}{a}
$$
J'ai parfois tendance à chercher midi à quatorze heures.

@Lou16
Convolution et tutti quanti. Par principe, l'utilisation des séries
$$
{1 \over (1-X)^n} = \sum_{i \ge 0} \binom {i + n-1}{n-1} X^i
$$
c'est une ``bonne chose''. Ce que tu dis doit être plus mieux que le truc auquel je pensais :
$$
\binom {n+m}{\bullet} = \binom {n}{\bullet} \star \binom {m}{\bullet} = \qquad \hbox {lié à} \qquad (X+1)^{n+m} = (X+1)^n (X+1)^m
$$
Il faut (??) probablement mettre aussi dans la course l'identité concernant le polynôme binomial :
$$
B_n(-X) = (-1)^n B_n(X + n-1), \qquad \qquad
B_n(X) = {\overbrace {X(X-1) \cdots (X-(n-1))}^{n} \over n!}
$$

Binomialement vôtre.

Cidrolin

Pour $1951$ je le savais ---> http://www.les-mathematiques.net/phorum/read.php?5,1552962,1554018#msg-1554018

Chaurien

J'ai une solution si $m \ge 1$ et $n \ge m+1$. Mon idée est de se débarrasser des $i$ en bas.
On a : $\displaystyle \sum _{i=0} ^p \binom{n-m+i-1}{i} \binom{m+p-i-1}{p-i}= \sum _{i=0} ^p \binom{n-m+i-1}{n-m-1} \binom{m+p-i-1}{m-1}$
$\displaystyle = \sum _{k=n-m-1} ^{n-m+p-1} \binom{k}{n-m-1} \binom{n+p-2-k}{m-1}= \sum _{k=0} ^{n+p-2} \binom{k}{n-m-1} \binom{n+p-2-k}{m-1}$.

Et alors j'applique la formule qu'on pourrait dire « anti-Vandermonde », que j'avais rappelée il y a deux ans dans le fil :
http://www.les-mathematiques.net/phorum/read.php?18,1366700,1366942
C'est : $\displaystyle \sum _{j=0} ^q \binom{j}{r} \binom{q-j}{s}= \binom{q+1}{r+s+1}$, ce qui me donne ici : $\displaystyle \binom{n+p-1}{n-1}=\binom{n+p-1}{p}$.
Bonne soirée.
Fr. Ch.

Cidrolin

Merci Chaurien.

claude quitté

@Chaurien
Je ne sais pas si tu as vu mon post en http://www.les-mathematiques.net/phorum/read.php?34,1600660,1600996#msg-1600996 ? J'ai probablement rapporté maladroitement Graham, Knuth et Patashnik, si bien que j'attache leurs pages 169-170 en question. Ainsi qu'une page manuscrite de mézigue réalisant le ``je n'ai pas pris le temps de le faire'' dans mon post pointé.

Pour mieux comprendre de quoi il s'agit, il faut savoir que l'égalité suivante (Vandermonde convolution) n'est soumise à aucune restriction si ce n'est $n, m \in \Z$ :
$$
\sum_k \binom {r}{m+k} \binom{s}{n-k} = \binom {r+s}{m+n} \qquad \qquad \hbox {restriction : $n,m \in \Z$} \qquad\qquad (\star)
$$
Ce qui signifie que $r,s$ sont quelconques (par exemple des réels ou des complexes ou pourquoi pas des indéterminées). Il est entendu que la définition du coefficient binomial est la suivante, le coefficient du bas est un entier, celui du haut quelconque :
$$
\binom {x}{d} = \cases {
\displaystyle {x(x-1) \cdots (x-(d-1)) \over d!} &si $d \ge 0$ \cr
0 &sinon \cr
}
\qquad d \in \Z
$$
Par exemple, $\binom {x}{2} = x(x-1)/2$ est un polynôme en $x$ et n'est pas nul sur la plage $x < 0$. Bien sûr, j'adopte ici les conventions des spécialistes GKP.
Dans $(\star)$, la plage de l'entier $k$ s'auto-détermine par $m+k \ge 0$ et $n-k \ge 0$ i.e. par $-m \le k \le n$.

On a l'identité polynomiale (je mets un $X$ pour appuyer le coup de l'indéterminée) :
$$
\binom {-X}{d} = (-1)^d \binom {X + d-1}{d} \qquad \qquad d \in \Z
$$
Si dans $(\star)$, on remplace $r$ par $-r$, $s$ par $-s$ (ce qui est licite car ce sont des indéterminées) et que l'on utilise l'identité ci-dessus, on finit par faire passer le paramètre ``sommatoire'' $k$ (qui était en position basse) en position haute. Et on obtient ce que tu appelles anti-Vandermonde (à l'aide de changements de variables, cf page manuscrite) :
$$
\sum_k \binom {a-k}{p} \binom{b+k}{q} = \binom {a+b+1}{p+q+1} \qquad\qquad (\heartsuit)
$$
ATTENTION cependant aux clauses (restrictions) requises pour $(\heartsuit)$ (on impose par exemple $p, q \in \N$ et bien d'autres choses) et à la plage de variation de $k$ qu'il convient maintenant de spécifier. Quelques subtilités (je trouve). Cf les explications de GKP et ma page manuscrite (désolé, c'est un brouillon pas très propre et le scan est médiocre).

GaBuZoMeu

L'égalité
$$\binom{n}{a}=\displaystyle \sum _i \binom{n-m}{i} \binom{m}{a-i}$$
n'est-elle pas une trivialité combinatoire ? Pour choisir $a$ éléments parmi $n$, on en choisit $i$ parmi les $n-m$ premiers et $a-i$ parmi les $m$ derniers, pour tous les $i$ possibles.
L'égalité
$$\sum_\ell \binom {\ell}{p} \binom{c-\ell}{q} = \binom {c+1}{p+q+1}$$
est à peine moins évidente combinatoirement : pour choisir $p+q+1$ parmi $c+1$, on choisit $\ell$, on choisit $p$ parmi les $\ell$ premiers, le $p+1$-ème des choisis est $\ell+1$, et on choisit encore $q$ parmi les $c-\ell$ derniers.
J'ai encore un peu de peine à trouver la trivialité combinatoire qui explique l'égalité du début de ce fil.

C'est peut-être expliqué dans les documents mis en lien, je ne les ai pas regardé.
PS. En fait, le message de Chaurien explique comment se ramener à la trivialité combinatoire : compter ceux qu'on jette plutôt que ceux que l'on choisit.;-)

PS2. La bijection de l'ensemble des triplets formés :
- d'un entier $i$ entre $0$ et $p$,
- d'une partie $A$ à $i$ éléments de $I_i=[\![1,n-m+i-1]\!]$,
- d'une partie $B$ à $p-i$ éléments de $J_i=[\![n-m+i+1,n+p-1]\!]$,
sur l'ensemble des parties à $p$ éléments de $[\![1,n+p-1]\!]$ qui au triplet $(i,A,B)$ associe $A\cup B$ prouve l'égalité
$$ \sum _{i=0} ^p \binom{n-m+i-1}{i} \binom{m+p-i-1}{p-i} =\binom{n+p-1}{p}\;.$$
Indication pour la bijection : le $i$ du triplet antécédent de la partie $M$ à $p$ éléments de $[\![1,n+p-1]\!]$ est l'entier $i$ tel que le $(n-m)$-ème élément du complémentaire de $M$ soit $n-m+i$ (il est bien compris entre $0$ et $p$).

Chaurien

@ Claude Quitté

$~~~~$ J'ai regardé tous les messages, mais je ne les ai pas étudiés dans le détail parce que je voulais rédiger selon mon idée.

$~~~~$ Depuis longtemps je recommande d'utiliser systématiquement les coefficients binomiaux généralisés $\binom {x}{k}$ avec $x \in \mathbb R$ ou $x \in \mathbb C$ comme tu dis, et $k \in \mathbb N$. Définis par $\binom {x}{k}=\frac{x(x-1)...(x-k+1)}{k!}$, et $\binom {x}{0}=1$. Et notamment de bien noter que $\binom {n}{k}=0$ si $n \in \mathbb N$ et $k>n$, ce qui rejoint la définition combinatoire. Pour l'instant je n'aborde pas le cas des indéterminées, mais pourquoi pas, on définit ainsi un polynôme.

$~~~~$ Avec cette définition, la formule de Vandermonde $ \displaystyle \sum _{j=0} ^n \binom{x}{j} \binom{y}{n-j}= \binom{x+y}{n}$ est vraie quels que soient $x \in \mathbb C$, $y \in \mathbb C$, $n \in \mathbb N$. Il est intéressant d'en collecter les démonstrations à bac+1. En particulier cette formule est vraie si $x \in \mathbb N$ et $y \in \mathbb N$. Dans ce cas, en vue des applications combinatoires, on peut s'amuser à regarder combien il y a de termes non nuls dans la somme.

$~~~~$ Malheureusement il y a encore des professeurs trop frileux pour adopter cette généralité. Il y en a même qui persistent à ne définir $\binom {n}{k}$ que pour $n \in \mathbb N$, $k \in \mathbb N$ et $k \le n$. Alors, la formule de Vandermonde que j'ai citée demande des hypothèses très compliquées !

$~~~~$ L'égalité : $ \displaystyle \binom{-a-1}{k}= (-1)^k \binom{a+k}{a} $, pour $a \in \mathbb N$ et $k \in \mathbb N$, permet de « monter » l'indice variable $k$ et de prouver la formule que j'ai dite « anti-Vandermonde » : $\displaystyle \sum _{j=0} ^q \binom{j}{r} \binom{q-j}{s}= \binom{q+1}{r+s+1}$, pour $q \in \mathbb N$, $r \in \mathbb N$, $s \in \mathbb N$, mais j'aimerais savoir si elle a un véritable nom, moins « négatif ». Cette formule a comme l'autre des applications probabilistes.

$~~~~$ J'ai le livre Concrete Mathematics de Graham, Knuth, Patashnik, en version papier légalement acquise ([small]pour une fois[/small]), mais je ne l'utilise pas fréquemment. C'est une mine de résultats, présentés dans un style décontracté que j'aime bien, un point fort pour les Anglo-Saxons. Je ne m'étais pas aperçu qu'il définissait des coefficients binomiaux avec un indice inférieur possiblement négatif, et je me sens pris de la frilosité de mes collègues devant cette extension pour moi inhabituelle. Il faudra que je vérifie que les propriétés connues restent valables.

Bien cordialement. Bonne journée.
Fr. Ch.

claude quitté

@Chaurien
Graham, Knuth et Patashnik prennent beaucoup de soin (au début de leur long chapitre V, 100 pages consacrées aux coefficients binomiaux) pour expliquer les règles du jeu. Chaque identité est accompagnée d'une clause spécifiant le lieu de vie des intervenants. Par exemple, tu verras :
$$
\binom{n}{k} = \binom{n}{n-k} \qquad \qquad \hbox {$k$ entier, $n$ entier $\ge 0$}
$$
Cela demande quand même quelques précautions. Par exemple, soit $n \in \N$. Faut-il prendre la formule de gauche ou celle de droite ?
$$
{1 \over (1-t)^n} = \sum_{i \ge 0} \binom {n-1 + i}{i}\, t^ i
\qquad\qquad\qquad
{1 \over (1-t)^n} = \sum_{i \ge 0} \binom {n-1 + i}{n-1}\, t^ i
$$
C'est sans importance car $n \in \N$. Mais si on veut relâcher cette clause $n \in \N$ en $n \in \Z$, c'est celle de gauche qu'il faut considérer.

Chaurien

J'aime bien l'approche combinatoire de GaBuZoMeu, à ceci près que je ne taxerais pas de « triviale » la formule de Vandermonde $ \displaystyle \sum _{j=0} ^n \binom{x}{j} \binom{y}{n-j}= \binom{x+y}{n}$. Elle l'est pour lui, et peut-être pour moi, parce que, matheux blanchis sous le harnois, nous l'avons vue tant de fois, mais il faut savoir conserver sa capacité d'émerveillement.
Cette formule se démontre de plusieurs façons si $x$ et $y$ sont des entiers naturels. Je peux en citer trois :
(1) Avec la fonction génératrice binomiale $(1+t)^{x+y}=(1+t)^x (1+t)^y$ ;
(2) combinatoire ;
(3) par récurrence sur $x$ (ou $y$).

Ce qui est remarquable c'est que l'on peut passer rapidement de $ (x,y) \in \mathbb N \times \mathbb N$ à $ (x,y) \in \mathbb C \times \mathbb C$.
Pour $n \in \mathbb N$, la fonction : $ \displaystyle (x,y) \mapsto P_n(x,y)= \binom{x+y}{n}- \sum _{j=0} ^n \binom{x}{j} \binom{y}{n-j}$, de $ \mathbb C \times \mathbb C$ dans $ \mathbb C$, est une fonction-polynôme à deux variables. Comme elle s'annule sur $ \mathbb N \times \mathbb N$, elle s'annule partout. C'est une sorte de densité algébrique, pour ainsi dire.

Bonne journée.
Fr. Ch.

GaBuZoMeu

C'est exactement la densité de $\N\times \N$ dans $\C\times \C$ (pour la topologie de Zariski, dont les fermés sont les sous-ensembles algébriques).

jandri

La question posée par Cidrolin revient régulièrement sur le forum.

J'ai retrouvé dans mes notes que Cidrolin avait lui-même proposé une démonstration combinatoire de cette formule il y a six ans: démonstration de Cidrolin.

Pour compléter ce qu'a dit Chaurien voici trois formules équivalentes valables pour tout couple $(x,y)\in \C^2$ et pour $n\in\N$ :

$\displaystyle \sum _{i+j=n} \binom{x}{i} \binom{y}{j}= \binom{x+y}{n}$ (c'est la formule de Vandermonde)

$\displaystyle \sum _{i+j=n} \binom{x+i}{i} \binom{y+j}{j}= \binom{x+y+n+1}{n}$

$\displaystyle \sum _{i+j=n} \binom{x-i}{j} \binom{y-j}{i}= \binom{x+y-n+1}{n}$.

nicolas.patrois

Variante vue dans la feuille d’exercice que j’ai eue taupin :
Démontrer que $C_n^q C_{n-q}^{p-q}=C_n^p C_p^q$ puis calculer $\sum_{k=0}^n C_n^k C_{n-k}^{p-k}$.