에고리체프법

에고리체프 방법은 게오르기 에고리체프가 이항계수 합계에서 정체성을 찾기 위해 도입한 기법의 집합체다.방법은 두 가지 관측에 의존한다.첫째, 생성함수의 계수를 추출함으로써 많은 정체성을 증명할 수 있다.둘째, 많은 발생함수는 수렴전원계열이며, 계수추출은 Cauchy 잔여정리(보통 이것은 원점을 감싸고 있는 작은 원형 등고선에 대해 집적함으로써 이루어진다)를 이용하여 할 수 있다.찾고자 하는 정체성은 이제 통합의 조작을 사용하여 찾을 수 있다.이러한 조작 중 일부는 발생함수의 관점에서 명확하지 않다.예를 들어, 통합은 대개 이성적인 함수로서, 이성적인 함수의 잔존물의 합은 0으로, 원래의 합계에 대해 새로운 표현을 산출한다.무한대의 잔류물은 이러한 고려사항에서 특히 중요하다.

Egorychev 방법에 의해 사용되는 주요 통합은 다음과 같다.

• 첫 번째 이항 계수 적분

${\displaystyle {n \cHB {1}{\frac {1}{2\pi i}\int _{z =\varepsilon }{\frac {(1+z)^{n}{z^{k+1}}\;dz를 선택하십시오.}$

• 2차 이항 계수 적분

${\displaystyle{n \n \k}={\frac {1}{2\pi i}\int _{z =\varepsilon }{\frac {1}{1-z)^{k+1}z^{n-k+1}}\;dz 선택.}$

• 지수 적분

${\displaystyle n^{k}={\frac {k!}}{2\pi i}\int _{z =\varepsilon }{\frac {\exp(nz)}{z^{k+1}\;dz:}$

• 아이버슨 브라켓

${\displaystyle [[0\leq k\leq n]]={\frac {1}{2\pi i}\int _{z^{k}{z^{n+1}}{\frac {1}{1-z}\;dz.}$

예 I

평가를 위해 노력한다고 가정합시다.

${\displaystyle S_{j}(n)=\sum _{k=0}^{n(-1)^{k}{n \선택 \k}{n+k 선택 \k}{k \선택 \j}}}$

(${\displaystyle }$- ${\displaystyle 1{}^{}}$)${\displaystyle n^{}}$ ${\displaystyle {}^{}n\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{j}{}}$)${\displaystyle }$(${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{}{}}$)${\displaystyle }$. ${\displaystyle(-1)^{n}{n \선택 j}.$$}$

Introduce :${\displaystyle {n+k \choose k}={\frac {1}{2\pi i}}\int _{ z =\varepsilon }{\frac {(1+z)^{n+k}}{z^{k+1}}}\;dz}$

및 :${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{k}{}}$ j${\displaystyle }$)${\displaystyle }$= ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{2\mathrm{}}{}}$ ${\displaystyle \frac{\pi }{}}$ ${\displaystyle i_{}}$ ${\displaystyle \frac{}{}{}_{}}$ w${\displaystyle {}_{}}$= ${\displaystyle \frac{{\gamma }^{}}{}{}_{}\frac{}{}}$( ${\displaystyle \frac{1}{}}$+ w${\displaystyle \frac{{}^{}}{}}$) ${\displaystyle \frac{w^{}}{}}$+ 1 ${\displaystyle w}$ .${\$d 디스플레이 $스타일 {$k$\선택 j}={\frac {1}{2\pi$ i$}\int _{w =\frac {}{\$frac {($1+w)^{k$$}}}{w^{j+1}}\;{nowledge.$$}$

이 값은 다음과 같다.

${\displaystyle{\begin{정렬}&,{\frac{1}{2\pi 나는}}\int _{z=\varepsilon}{\frac{ᆩ ^{n}}{z}}{\frac{1}{2\pi 나는}}\int _{w=\gamma}{\frac{1}{w^{j+1}}}\sum _ᆹ^ᆺ())^ᆻᆼᆽ(1+w)^{k}}{z^{k}}}\;dw\, dz\\[6pt]={}&,{\frac{1}{2\pi 나는}}\int _{z=\varepsilon}{\frac{ᆭ ^{n}}{z}}{\frac{1}{2\pi 나는}}\int_{w=\g.amma}{)frac {1}{w^{j+1}}\좌측(1-{\frac {(1+w)(1+z)}{z}}{z}\우측)^{n}\;dw\;dz\\[6pt]={}&{\frac {1}{2\pi i}}\int _{ z =\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{\frac {1}{2\pi i}}\int _{ w =\gamma }{\frac {1}{w^{j+1}}}(-1-w-wz)^{n}\;dw\;dz\\[6pt]={}&{\frac {(-1)^{n}}{2\pi i}}\int _{ z =\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{\frac {1}{2\pi i}}\int _{ w =\gamma }{\frac {1}{w^{j+1}}}(1+w+wz)^{n}\;dz.\end{정렬}}}$

이것은

${\displaystyle {\frac {(-1)^{n}}{2\pi i}}\int _{ z =\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{\frac {1}{2\pi i}}\int _{ w =\gamma }{\frac {1}{w^{j+1}}}\sum _{q=0}^{n}{n \choose q}w^{q}(1+z)^{q}\;dw\;dz.}$

${\displaystyle \mathrm{w}}$= 0 ${\displaystyle w=0}$에서 잔여물을 추출하면$$

${\displaystyle {\begin{aligned}&{\frac {(-1)^{n}}{2\pi i}}\int _{ z =\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{n \choose j}(1+z)^{j}\;dz\\[6pt]={}&{n \choose j}{\frac {(-1)^{n}}{2\pi i}}\int _{ z =\varepsilon }{\frac {(1+z)^{n+j}}{z^{n+1}}}\;dz\\[6pt]={}&(-1)^{n}{n \choose j}{n+j \choose n}\end{aligned}}}$

따라서 그 주장을 증명한다.

예 II

$\sum {\displaystyle \underset{k}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ k${\displaystyle }$( ${\displaystyle \genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{k}{}}$)${\displaystyle }$. ${\displaystyle \sum _{k=1}^{n}k{2n \선택 n+k}$를 평가하려고 한다고 가정합시다.$}$

소개하다

${\displaystyle{2n \n}={\frac {1}{2\pi i}\int _{z^{n-k+1}{\frac {1}{1}{n+k+1}}}{\frac {1}{n+k+1}}}\dz를 선택하십시오.}$

> ${\displaystyle k>n}$의 경우 이 값이 0이므로 $k{\displaystyle }$ ${\displaystyle k}$을(를) 무한대로$$ 확장하여 합계를 얻을 수 있는지 확인하십시오.

${\displaystyle {\begin{aligned}&{\frac {1}{2\pi i}}\int _{ z =\varepsilon }{\frac {1}{z^{n+1}}}{\frac {1}{(1-z)^{n+1}}}\sum _{k\geq 1}k{\frac {z^{k}}{(1-z)^{k}}}\;dz\\[6pt]={}&{\frac {1}{2\pi i}}\int _{ z =\varepsilon }{\frac {1}{z^{n+1}}}{\frac {1}{(1-z)^{n+1}}}{\frac {z/(1-z)}{(1-z/(1-z))^{2}}}\;dz\\[6pt]={}&{\frac {1}{2\pi i}}\int _{ z =\varepsilon }{\frac {1}{z^{n}}}{\frac {1}{(1-z)^{n}}}{\frac {1}{(1-2z)^{2}}}\;dz.\end{정렬}}}$

Now put ${\displaystyle z(1-z)=w}$ so that (observe that with ${\displaystyle w=z+\cdots }$ the image of ${\displaystyle z =\varepsilon }$ with ${\displaystyle \varepsilon }$ small is another closed circle-like contour which makes one turn and which we may certainly deform to obtain다른 원 ${\displaystyle w}$=$$${\displaystyle \gamma }$ ${\displaystyle$ w $=\property }$ )

${\displaystyle z={\frac {1-{\sqrt{1-4w}}{2}}:\design{\text{and}}}}}^{2}=1-4w}$

게다가

${\displaystyle dz=-{\frac {1}{1}:{1}{1}:{1}{1}:{1}{1}\fract (-4w)\filename (1-4w)^{-1/2}}\;1-4w)^{-1/2}}\;{-1/2}\;118}$

필수품을 구하다

${\displaystyle {\frac {1}{2\pi i}}\int _{ w =\gamma }{\frac {1}{w^{n}}}{\frac {1}{1-4w}}(1-4w)^{-1/2}\;dw={\frac {1}{2\pi i}}\int _{ w =\gamma }{\frac {1}{w^{n}}}{\frac {1}{(1-4w)^{3/2}}}\;dw.}$

검사로 평가하여 (뉴턴 이항계 사용)

${\displaystyle {\frac{n-1}{n-1+1/2 \선택 n-1}=4^{n-1}{n-1/2 \선택 n-1}={\frac {4^{n-1}:{n-1}{(n-1)!}}}\prod _{q=0}^{n-2}(n-1/2-q)\\={}&{\frac{2^{n-1}{(n-1)!}}}\prod _{q=0}^{n-2}-2}(2n-2q-1)={\frac {2^{n-1}{(n-1)!}}{\frac{(2n-1)!}{2^{n-1}(n-1)!}}\\[6pt]={}&{\frac{n^{2}}:{2}}:{2n \선택 n}={\frac{1}{2}}n \n \선택 n}\end{정렬}}}$

여기서 z${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle z=0}$에서 $w{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle w=0}$까지의 매핑은 제곱근의 선택을 결정한다$$.ϵ{\displaystyle \epsilon}과γ{\displaystyle \gamma}의 조건은 동안에 우리는 시리즈 융합될 우리가 z/(1z−)<1{\displaystyle z(1-z)<1}또는 ϵ/(1− ϵ)<1{\displaystyle \epsilon (1-\epsilon)< 1}또는ϵ<1/2.{\displaystyle \epsilo이 필요하다.n<>1/2.} 여이지아는 z의 ϵ{\displaystyle z=\epsilon}기원에 나오는 이미지 등고선 cm는ϵ− ϵ 2{\displaystyle \epsilon -\epsilon ^{2}}우리는γ<>를 선택한다;예를 들어 ϵ− ϵ 2{\displaystyle \gamma<>\epsilon -\epsilon ^{2}}γ)ϵ 2− ϵ 3.{\displaystyl 가장 가까운.e\gam마 총통 =\epsilon ^{2}-\epsilon ^{3}.}이 또한 1/4{\displaystyle \gamma<>1/4} 그렇게)w γ{\displaystyle w=\gamma}그 나뭇가지 자르는 경우에는 1/4, ∞){\displaystyle -LSB- 1/4,\infty)}라고 zϵ{\displaystyle z=\epsilon}의 이미지에 담겨 있다. 교차하지 않γ<>을 보장한다.cm이다.예를 들어 $ϵ{\displaystyle }$= ${\displaystyle 1}$/ ${\displaystyle 3\mathrm{}}$ ${\displaystyle \epsilon =1/3}$ 및$$ $\gamma {\displaystyle }$= ${\displaystyle 2}$/ ${\displaystyle 27}$ ${\displaystyle \gamma =2/27}$이(가) 작동한다$$.

또한 이 예는 더 간단한 방법을 제시하지만 통합 변수로 대체하는 효과를 입증하기 위해 여기에 포함되었다.

공식 파워 시리즈를 이용한 연산

Egorychev 텍스트(16페이지)에서 변수 규칙 1.8(5)의 변경을 통합에 사용할 수 있다.

${\displaystyle {\frac {1}{2\pi i}}\int _{ z =\varepsilon }{\frac {1}{z^{n}}}{\frac {1}{(1-z)^{n}}}{\frac {1}{(1-2z)^{2}}}\;dz={\underset {z}{\mathrm {res} }}{\frac {1}{z^{n}}}{\frac {1}{(1-z)^{n}}}{\frac {1}{(1-2z)^{2}}}}$

with ${\displaystyle A(z)={\frac {z}{(1-2z)^{2}}}}$ and ${\displaystyle f(z)={\frac {1}{1-z}}.}$ We get ${\displaystyle h(z)=z(1-z)}$ and find

${\displaystyle {w}{\mathrm {res}}}{{w^{n+1}}\왼쪽.\left[{\frac {A(z)}{f(z)h'}}}\right]\right _{z=g(w).}}$

$g{\displaystyle }$ ${\displaystyle g}$과(와) $h{\displaystyle }$ ${\displaystyle h}$의 역행$$$.$

이 되다

${\displaystyle {w}{\mathrm {res}}}{{w^{n+1}}\왼쪽.\left[{\frac{z/(1-2z)^{2}}:{(1-2z)/(1-z)}}\오른쪽 _{z=g(w)}}}}$

또는 대안으로

${\displaystyle {w}{\mathrm {res}}}{{w^{n+1}}\왼쪽.\left[{\frac{1-z)}{{3}}}{{3}}\right]\right _{z=g(w)}={\mathrm {w}{{1}{w^{n}}}\왼쪽.\left[{\frac{1}{(1-2z)^{3}\}\right]\right _{z=g(w).}}$

$({\displaystyle 1}$- ${\displaystyle 2}$ ${\displaystyle \mathrm{z}{}^{}}$) ${\displaystyle {2\mathrm{}}^{}}$= 1${\displaystyle }$- 4 ${\displaystyle z}$+ ${\displaystyle 1}$ - ${\displaystyle {}^{}{z\mathrm{}}^{}}$ ${\displaystyle 2}$= ${\displaystyle 1}$ -${\displaystyle 4}$ z${\displaystyle }$( ${\displaystyle 1}$-${\displaystyle \mathrm{z}}$ )${\displaystyle }$= 1 - ${\displaystyle 4}$ ${\displaystyle w}$ ${\displaystyle$ ($1-2z)^{2$}=$1-4z+$4z$^{$2}=$1-4z(1-z)=1-4w}$임을$$ 관찰하십시오.

${\displaystyle {w}{\mathrm {res}}}}{\frac {1}{w^{n}}{\frac {1}{1}{1-4w)^{3/2}}$

그리고 나머지 계산은 전과 같이 계속된다.

외부 링크

• Egorychev 방법을 사용하여 이항 계수를 포함하는 합계를 평가하는 계산 예제

참조

• Egorychev, G. P. (1984). Integral representation and the Computation of Combinatorial sums. American Mathematical Society.