Тождество Вандермонда
Войти  |  Регистрация
Авторизация
» » Тождество Вандермонда

Тождество Вандермонда



Тождество Вандермонда (или свёртка Вандермонда) — это следующее тождество для биномиальных коэффициентов:

( m + n r ) = ∑ k = 0 r ( m k ) ( n r − k ) {displaystyle {m+n choose r}=sum _{k=0}^{r}{m choose k}{n choose r-k}}

для любых неотрицательных целых чисел r, m, n. Тождество названо именем Александра Теофила Вандермонда (1772), хотя оно было известно ещё в 1303 китайскому математику Чжу Шицзе. См. статью Аскея по истории тождества.

Существует q-аналог этой теоремы, называющийся q-тождеством Вандермонда.

Тождество Вандермонда можно обобщить множеством способов, включая тождество

( n 1 + ⋯ + n p m ) = ∑ k 1 + ⋯ + k p = m ( n 1 k 1 ) ( n 2 k 2 ) ⋯ ( n p k p ) {displaystyle {n_{1}+dots +n_{p} choose m}=sum _{k_{1}+cdots +k_{p}=m}{n_{1} choose k_{1}}{n_{2} choose k_{2}}cdots {n_{p} choose k_{p}}} .

Доказательства

Алгебраическое доказательство

В общем случае для произведения двух многочленов степеней m и n имеет место формула

( ∑ i = 0 m a i x i ) ( ∑ j = 0 n b j x j ) = ∑ r = 0 m + n ( ∑ k = 0 r a k b r − k ) x r , {displaystyle {iggl (}sum _{i=0}^{m}a_{i}x^{i}{iggr )}{iggl (}sum _{j=0}^{n}b_{j}x^{j}{iggr )}=sum _{r=0}^{m+n}{iggl (}sum _{k=0}^{r}a_{k}b_{r-k}{iggr )}x^{r},}

где используем соглашение, что ai = 0 для всех целых чисел i > m и bj = 0 для всех целых j > n. Согласно биному Ньютона,

( 1 + x ) m + n = ∑ r = 0 m + n ( m + n r ) x r . {displaystyle (1+x)^{m+n}=sum _{r=0}^{m+n}{m+n choose r}x^{r}.}

Используем формулу бинома Ньютона также для степеней m и n, а затем вышеприведённую формулу для произведения многочленов, получаем

∑ r = 0 m + n ( m + n r ) x r = ( 1 + x ) m + n = ( 1 + x ) m ( 1 + x ) n = ( ∑ i = 0 m ( m i ) x i ) ( ∑ j = 0 n ( n j ) x j ) = ∑ r = 0 m + n ( ∑ k = 0 r ( m k ) ( n r − k ) ) x r , {displaystyle {egin{aligned}sum _{r=0}^{m+n}{m+n choose r}x^{r}&=(1+x)^{m+n}&=(1+x)^{m}(1+x)^{n}&={iggl (}sum _{i=0}^{m}{m choose i}x^{i}{iggr )}{iggl (}sum _{j=0}^{n}{n choose j}x^{j}{iggr )}&=sum _{r=0}^{m+n}{iggl (}sum _{k=0}^{r}{m choose k}{n choose r-k}{iggr )}x^{r},end{aligned}}}

где вышеупомянутые соглашения о коэффициентах многочленов согласуются с определением биномиальных коэффициентов, поскольку дают нуль для всех i > m {displaystyle i>m} и j > n {displaystyle j>n} .

Сравнивая коэффициенты при xr, получаем тождество Вандермонда для всех целых r с 0 ⩽ r ⩽ m + n {displaystyle 0leqslant rleqslant m+n} . Для больших значений r обе стороны тождества Вандермонда равны нулю согласно определению биномиальных коэффициентов.

Комбинаторное доказательство

Тождество Вандермонда допускает также комбинаторное доказательство при помощи двойного подсчёта. Предположим, что комитет состоит из m мужчин и n женщин. Сколькими способами можно сформировать подкомитет из r членов? Ответом является

( m + n r ) . {displaystyle {m+n choose r}.}

Это число является суммой по всем возможным значениям k числа комитетов, состоящим из k мужчин и r − k {displaystyle r-k} женщин:

∑ k = 0 r ( m k ) ( n r − k ) . {displaystyle sum _{k=0}^{r}{m choose k}{n choose r-k}.}

Геометрическое доказательство

Возьмём прямоугольную решётку из r x (m+n-r) квадратов. Существует

( r + ( m + n − r ) r ) = ( m + n r ) {displaystyle {inom {r+(m+n-r)}{r}}={inom {m+n}{r}}}

путей, начинающихся с нижнего левого угла и кончающихся в верхнем правом углу, двигаясь только вправо и вверх (в результате имеем r переходов вправо и m+n-r переходов вверх (или наоборот) в любом порядке, а всего переходов будет m+n). Обозначим нижний левый угол через (0,0).

Существует ( m k ) {displaystyle {inom {m}{k}}} путей, начинающихся в (0,0) и кончающихся в (k,m-k), поскольку должно быть сделано k правых переходов и m-k переходов вверх (длина пути будет равна m). Аналогично, имеется ( n r − k ) {displaystyle {inom {n}{r-k}}} путей, начинающихся в (k,m-k) и кончающихся в (r,m+n-r), как результат r-k переходов вправо и (m+n-r)-(m-k) движений вверх, длина пути будет равна r-k + (m+n-r)-(m-k) = n. Таким образом, имеется

( m k ) ( n r − k ) {displaystyle {inom {m}{k}}{inom {n}{r-k}}}

Путей, начинающихся в (0,0), кончающихся в (r, m+n-r) и проходящих через (k, m-k). Этот набор путей является подмножеством всех путей, начинающихся в (0,0) и заканчивающихся в (r, m+n-r), так что сумма от k=0 до k=r (поскольку точка (k, m-k) должна лежать внутри прямоугольника) даст полное число путей, начинающихся в (0,0) и завершающихся в (r, m+n-r).

Обобщения

Обобщённое тождество Вандермонда

Можно обобщить тождество Вандермонда следующим образом:

∑ k 1 + ⋯ + k p = m ( n 1 k 1 ) ( n 2 k 2 ) ⋯ ( n p k p ) = ( n 1 + ⋯ + n p m ) {displaystyle sum _{k_{1}+cdots +k_{p}=m}{n_{1} choose k_{1}}{n_{2} choose k_{2}}cdots {n_{p} choose k_{p}}={n_{1}+dots +n_{p} choose m}} .

Это тождество можно получить с помощью алгебраического вывода (как выше) при использовании более двух многочленов, или через обычный двойной подсчёт.

С другой стороны, можно выбрать k 1 {displaystyle extstyle k_{1}} элементов из первого множества из n 1 {displaystyle extstyle n_{1}} элементов, затем выбрать k 2 {displaystyle extstyle k_{2}} элементов из другого множества, и так далее, для всех p {displaystyle extstyle p} таких множеств, пока не будет выбрано m {displaystyle extstyle m} элементов из p {displaystyle extstyle p} множеств. Таким образом, выбирается m {displaystyle extstyle m} элементов из n 1 + ⋯ + n p {displaystyle extstyle n_{1}+dots +n_{p}} в левой части тождества, что в точности совпадает с тем, что делается в правой части.

Тождество Чжу — Вандермонда

Тождество обобщается на нецелочисленные аргументы. В этом случае тождество известно как Тождество Чжу — Вандермонда (см. статью Аскея) и принимает вид

( s + t n ) = ∑ k = 0 n ( s k ) ( t n − k ) {displaystyle {s+t choose n}=sum _{k=0}^{n}{s choose k}{t choose n-k}}

для комплексных чисел s и t общего вида и неотрицательных целых n. Тождество можно доказать по аналогии с доказательством выше с помощью умножения биномиальных рядов для ( 1 + x ) s {displaystyle (1+x)^{s}} и ( 1 + x ) t {displaystyle (1+x)^{t}} и сравнения членов с биномиальными рядами для ( 1 + x ) s + t {displaystyle (1+x)^{s+t}} .

Это тождество можно переписать в терминах убывающих символов Похгаммера

( s + t ) n = ∑ k = 0 n ( n k ) ( s ) k ( t ) n − k {displaystyle (s+t)_{n}=sum _{k=0}^{n}{n choose k}(s)_{k}(t)_{n-k}}

В этом виде тождество ясно распознаётся как теневой вариант бинома Ньютона (о других теневых вариантах бинома Ньютона см. Последовательность многочленов биномиального типа). Тождество Чжу — Вандермонда можно рассматривать также как частный случай гипергеометрической теоремы Гаусса, которая утверждает, что

2 F 1 ( a , b ; c ; 1 ) = Γ ( c ) Γ ( c − a − b ) Γ ( c − a ) Γ ( c − b ) {displaystyle ;_{2}F_{1}(a,b;c;1)={frac {Gamma (c)Gamma (c-a-b)}{Gamma (c-a)Gamma (c-b)}}}

где 2 F 1 {displaystyle ;_{2}F_{1}} — гипергеометрическая функция, а Γ ( n + 1 ) = n ! {displaystyle Gamma (n+1)=n!} — гамма-функция. Если взять в тождестве Чжу — Вандермонда a = −n, получим

( n k ) = ( − 1 ) k ( k − n − 1 k ) {displaystyle {n choose k}=(-1)^{k}{k-n-1 choose k}} .

Тождество Роте — Хагена является дальнейшим обобщением данного тождества.

Гипергеометрическое распределение вероятности

Если обе части тождества разделить на выражение слева, то сумма станет равной 1 и члены можно интерпретировать как вероятности. Получающееся распределение вероятностей называется гипергеометрическим распределением. Это распределение соответствует распределению вероятности числа красных шаров при выборке (без возвращения) r шаров из урны, содержащей n красных и m синих шаров.


Добавлено Admin 4-08-2021, 12:01 Просмотров: 14
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent