Введение
Математическая теорема о свёрточных биномиальных коэффициентах
выражение для специального определителя
В комбинаторике, тождество Вандермонда (или свёртка Вандермонда) — это следующее тождество для биномиальных коэффициентов:
the expression for a special determinant
In combinatorics, Vandermonde's identity (or Vandermonde's convolution) is the following identity for binomial coefficients:
для любых неотрицательных целых чисел r, m, n. Это тождество названо в честь Александра Теофиля Вандермонда (1772 год), хотя оно было известно уже в 1303 году китайскому математику Чжу Шицзе. Существует q-аналог этой теоремы, называемый q-тождеством Вандермонда. Тождество Вандермонда может быть обобщено множеством способов, в том числе к тождеству
Геометрическое доказательство
Возьмите прямоугольную сетку из r x (m+n−r) квадратов. Существует путей, которые начинаются в нижней левой вершине и, двигаясь только вверх или вправо, заканчиваются в верхней правой вершине (это потому, что необходимо сделать r шагов вправо и m+n−r шагов вверх (или наоборот) в любом порядке, а общая длина пути равна m+n). Обозначим нижнюю левую вершину как (0, 0). Существует путей, начинающихся в (0, 0) и заканчивающихся в (k, m−k), поскольку необходимо сделать k шагов вправо и m−k шагов вверх (длина пути равна m). Аналогично, существует путей, начинающихся в (k, m−k) и заканчивающихся в (r, m+n−r), поскольку необходимо сделать в общей сложности r−k шагов вправо и (m+n−r) − (m−k) шагов вверх, а длина пути должна быть равна (r−k) + (m+n−r) − (m−k) = n. Таким образом, существует путей, которые начинаются в (0, 0), заканчиваются в (r, m+n−r) и проходят через (k, m−k). Это подмножество всех путей, которые начинаются в (0, 0) и заканчиваются в (r, m+n−r), поэтому, суммируя по k от 0 до r (поскольку точка (k, m−k) должна находиться внутри квадрата), мы получим общее количество путей, которые начинаются в (0, 0) и заканчиваются в (r, m+n−r).
paths that start on the bottom left vertex and, moving only upwards or rightwards, end at the top right vertex (this is because r right moves and m+n r up moves must be made (or vice versa) in any order, and the total path length is m + n). Call the bottom left vertex (0, 0). There are paths starting at (0, 0) that end at (k, m−k), as k right moves and m−k upward moves must be made (and the path length is m). Similarly, there are paths starting at (k, m−k) that end at (r, m+n−r), as a total of r−k right moves and (m+n−r) − (m−k) upward moves must be made and the path length must be r−k + (m+n−r) − (m−k) = n. Thus there are
paths that start at (0, 0), end at (r, m+n−r), and go through (k, m−k). This is a subset of all paths that start at (0, 0) and end at (r, m+n−r), so sum from k = 0 to k = r (as the point (k, m−k) is confined to be within the square) to obtain the total number of paths that start at (0, 0) and end at (r, m+n−r).
Гипергеометрическое распределение вероятностей
Когда обе стороны разделены на выражение слева, так что их сумма равна 1, члены этой суммы можно интерпретировать как вероятности. В результате получается гипергеометрическое распределение – распределение вероятности количества красных шаров в r выборках без возвращения из урны, содержащей n красных и m синих шаров.