Вандермондов идентитет

Из Википедије, слободне енциклопедије

У комбинаторици, Вандермондов идентитет, који је добио име по математичару Александру-Теофилу Вандермонду, је тврђење да важи једнакост

{n+m \choose r}=\sum_{k=0}^r{n \choose k}{m \choose r-k}.

Доказ[уреди]

Идентитет се лако доказује коришћењем алгебарске једнакости

{n \choose k}={n! \over k!(n-k)!},

Ако претпоставимо да у одељењу има n дечака и m девојчица, на колико начина је могуће изабрати r ученика? Одговор је, наравно, израз са леве стране једнакости

{n+m \choose r}.

Са десне стране налази се збир свих могућих избора од r ученика таквих да је међу њима k дечака и r − k девојчица, при чему је k број између 0 и r.