Simplification de l'expression combinatoire

Question

Je résous un problème et je suis coincé dessus depuis des heures.

Je ne me souviens d'aucune approche / formule combinatoire pour l'expression ci-dessous:

$$\sum_{i=a+1}^n {i-1 \choose a}{n-i \choose k-a}$$

N'importe quelle sorte d'aide serait appréciée. Je sais que c'est une norme de partager aussi mon approche pour montrer que j'ai fait un effort mais honnêtement je n'ai aucune idée sur cette question particulière.

Merci!

Answer 1

Ce qui suit n'est certes pas la preuve la plus simple. Nous postons ici en guise d'enrichissement et pour présenter quatre techniques, les extracteurs de coefficients, le bracket Iverson, les résidus et la règle de Leibniz.

Nous cherchons à montrer que

$$\sum_{q=a+1}^n {q-1\choose a} {n-q\choose k-a} = {n\choose k+1}$$

où $k\ge a$ pour le coefficient binomial à définir, et $n\ge a+1$ Ou bien

$$\sum_{q=0}^{n-a-1} {q+a\choose a} {n-a-1-q\choose k-a} = {n\choose k+1}.$$

Le LHS est

$$[z^{k-a}] (1+z)^{n-a-1} \sum_{q\ge 0} {q+a\choose a} (1+z)^{-q} [[q\le n-a-1]] \\ = [z^{k-a}] (1+z)^{n-a-1} \sum_{q\ge 0} {q+a\choose a} (1+z)^{-q} [w^{n-a-1}] \frac{w^q}{1-w} \\ = [z^{k-a}] (1+z)^{n-a-1} [w^{n-a-1}] \frac{1}{1-w} \sum_{q\ge 0} {q+a\choose a} (1+z)^{-q} w^q \\ = [z^{k-a}] (1+z)^{n-a-1} [w^{n-a-1}] \frac{1}{1-w} \frac{1}{(1-w/(1+z))^{a+1}} \\ = [z^{k-a}] (1+z)^{n} [w^{n-a-1}] \frac{1}{1-w} \frac{1}{(1+z-w)^{a+1}}.$$

C'est

$$[z^{k-a}] (1+z)^n (-1)^a \mathrm{Res}_{w=0} \frac{1}{w^{n-a}} \frac{1}{w-1} \frac{1}{(w-(1+z))^{a+1}}.$$

Maintenant le résidu à l'infini pour $w$ est égal à zéro par examen, la somme des résidus à zéro et le résidu à $w=1$ rendements

$$[z^{k-a}] (1+z)^n (-1)^a \frac{1}{(-1)^{a+1} z^{a+1}} = - {n\choose k+1}.$$

C'est la revendication si nous pouvons montrer que la contribution du pôle à $w=1+z$est zéro. Nous obtenons (règle de Leibniz)

$$\frac{1}{a!} \left(\frac{1}{w^{n-a}} \frac{1}{w-1}\right)^{(a)} = \frac{1}{a!} \sum_{q=0}^a {a\choose q} \frac{(-1)^q (n-1-a+q)!}{(n-1-a)! \times w^{n-a+q}} \frac{(-1)^{a-q} (a-q)!}{(w-1)^{a+1-q}} \\ = (-1)^a \sum_{q=0}^a {n-1-a+q\choose q} \frac{1}{w^{n-a+q}} \frac{1}{(w-1)^{a+1-q}}.$$

On obtient ainsi pour la contribution

$$[z^{k-a}] (1+z)^n \sum_{q=0}^a {n-1-a+q\choose q} \frac{1}{(1+z)^{n-a+q}} \frac{1}{z^{a+1-q}} \\ = \sum_{q=0}^a {n-1-a+q\choose q} [z^{k+1-q}] (1+z)^{a-q} = 0$$

car $a\ge q$ et $k+1\gt a.$ Ceci conclut l'argument.

Answer 2

On obtient \ begin {align *} \ color {blue} {\ sum_ {i = a + 1} ^ n} & \ color {blue} {\ binom {i-1} {a} \ binom {ni} {ka }} \\ & = \ sum_ {i = a + 1} ^ n \ binom {i-1} {ia-1} \ binom {ni} {ni-k + a} \ tag {1} \\ & = \ sum_ {i = a + 1} ^ n \ binom {-a-1} {ia-1} (- 1) ^ {ia-1} \ binom {-k + a-1} {ni-k + a } (- 1) ^ {ni-k + a} \ tag {2} \\ & = (- 1) ^ {nk-1} \ sum_ {i = 0} ^ {na-1} \ binom {-a -1} {i} \ binom {-k + a-1} {nk-1-i} \ tag {3} \\ & = (- 1) ^ {nk-1} \ binom {-k-2} {nk-1} \ tag {4} \\ & = \ binom {n} {nk-1} \ tag {5} \\ & \, \, \ color {blue} {= \ binom {n} {k +1}} \ end {align *} et la revendication suit.

Commentaire:

• Dans (1) nous utilisons $\binom{p}{q}=\binom{p}{p-q}$ deux fois.

• Dans (2) nous appliquons l'identité binomiale $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• Dans (3), nous décalons l'index pour commencer par $i=0$.

• Dans (4) nous appliquons le https://en.wikipedia.org/wiki/Vandermonde%27s_identity#Chu%E2%80%93Vandermonde_identity. Ici, nous utilisons que l'indice supérieur est en fait$n-k-1$, depuis $k\geq a$.

• Dans (5), nous appliquons à nouveau l'identité comme nous l'avons fait dans (2).

Answer 3

Considérez les mots binaires de longueur $n$ avec $k+1$ ceux ... $ \binom{n}{k+1}$.

Laisse le $(a+1)^{th}$ on se produit au $i^{th}$position. Il y a$a$ ceux dans le $i-1$ positions avant cette entrée ... $\binom{i-1}{a}$. Et il y a$k-a$ ceux dans le $n-i$ positions après ... $\binom{n-i}{k-a}$. Maintenant$i$ peut varier $a+1$ et $n$, ainsi nous avons \ begin {eqnarray *} \ sum_ {i = a + 1} ^ n \ binom {i-1} {a} \ binom {ni} {ka} = \ binom {n} {k + 1} . \ end {eqnarray *}

Je serais intéressé de voir une preuve algébrique de cela.

Edit (à la lumière de la réponse de MS ci-dessous): Utilisez deux fois l'astuce binomiale négative \ begin {eqnarray *} \ binom {-p} {q} = (- 1) ^ q \ binom {p + q-1} {q} . \ end {eqnarray *} L'identité Vandermonde peut maintenant être appliquée, binôme négatif à nouveau et le résultat suit.

Answer 4

Astuce: essayez$\binom{n}{k+1}$c'est comme Hockey Stick et Vandermonde ensemble. Essayez de combiner chacune de leurs descriptions combinatoires. N'oubliez pas que l'identité du bâton de hockey est comme$\sum _{k=0}^n\binom{k}{\ell}=\binom{n+1}{\ell +1}$ et ce qu'il fait est de réparer le plus gros élément et de choisir le reste $k.$Ici, vous choisissez un élément du milieu! (Appeler$i$et cueillette à gauche et à droite (comme sur Vandermonde)).

Un indice pas sérieux: j'ai appelé cette identité: "Vandermonde jouant au hockey" quelque part auparavant.