이항 변환

조합학에서 이항 변환은 순서의 변환(즉, 순서의 변환)으로, 그 순서의 차이를 계산한다.그것은 오일러 변환과 밀접하게 연관되어 있는데, 이것은 이항 변환을 그것의 일반적인 생성 기능과 연관된 순서에 적용한 결과물이다.

정의

시퀀스 {a_n}의 이항 변환 T는 {s_n}에 의해 정의된 시퀀스

${\displaystyle s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \선택 k}a_{k}.}$

형식적으로는 글을 쓸 수 있다.

${\displaystyle s_{n}=(Ta)_{n}=\sum _{k=0}^{nn}}T_{nk}a_{k}}}}$

변환의 경우, 여기서 T는 매트릭스 요소 T를_nk 갖는 무한 차원 연산자다.그 변형은 무의식적인 것이다, 즉,

${\displaystyle TT=1}$

또는 색인 표기법을 사용하여

${\displaystyle \sum _{k=0}^{\nk}T_{nk}T_{km}=\delta _{nm}}}$

여기서$$ ${\displaystyle {\Delta n}_{}}$ ${\displaystyle m_{}}$ ${\$는 Kronecker 델타다.원래의 시리즈는 다음 방법으로 되찾을 수 있다.

${\displaystyle a_{n}=\sum _{k=0}^{n}(-1)^{k}{n \선택 k}s_{k}.}$

시퀀스의 이항 변환은 시퀀스의 n번째 전방 차이일 뿐이며, 홀수 차이는 음의 부호를 전달한다. 즉, 다음과 같다.

${\displaystyle {\begin}s_{0}&=a_{0}\\s_{1}=-(\Delta a)_{0}=-a_{1}+a_{0}}\\s_{2}&=(\Delta ^{2}a)_{0}=-(-a_{2}+a_{1}+++(-a_{0})++(-a_{1})=a_{2}-2a_{1}+a_{0}=a_{0}=a_{0}+a_{0}}\\&\\\\vdots \\s_{n}&=(-1)^{n}(\Delta ^{n}a)_{0}\end{arged}}}}}}}$

여기서 Δ는 전방차 측정 시스템이다.

일부 저자는 추가 기호로 이항 변환을 정의하여 이항 변환이 자기반복적이지 않도록 한다.

${\displaystyle t_{n}=\sum _{k=0}^{n(-1)^{n-k}{n \선택 k}a_{k}}}$

그 반대인.

${\displaystyle a_{n}=\sum _{k=0}^{n}{n \선택 k}t_{k}.}$

이 경우 전자의 변환을 역이항변환이라고 하며 후자는 이항변환일 뿐이다.이것은 예를 들어 온라인 정수 백과사전에서의 표준 용법이다.

예

이항 변환의 두 버전은 모두 차이 표에 나타난다.다음 차이 표를 고려하십시오.

0		1		10		63		324		1485
	1		9		53		261		1161
		8		44		208		900
			36		164		692
				128		528
					400

각 행은 이전 행의 차이다.(m-th 라인의 n번째 숫자는 a_m,n = 3ⁿ⁻²(2n^m+12 + 2^m(1+6m)n + 29m^m-12)이며, 차이 방정식 a_m+1,n = a_m,n+1 - a holds_m,n)

왼쪽에서 오른쪽으로 읽는 상단 라인은 {a_n} = 0, 1, 10, 63, 324, 1485, ...출발점이 같은 대각선은_n 0, 1, 8, 36, 128, 400, ...이다.{t_n}은(는) {a_n}의 비인접 이항 변환이다.

오른쪽에서 왼쪽으로 읽은 상단 라인은 {b_n} = 1485, 324, 63, 10, 1, 0, ...출발점이 같은 1485인 교차 대각선은 {s_n} = 1485, 1161, 900, 692, 528, 400, ...{s_n}은(는) {b_n}의 비자발적 이항변환이다.

일반생성함수

변환은 영상 시리즈와 관련된 생성 기능을 연결한다.일반적인 생성 기능의 경우

${\displaystyle f(x)=\sum _{n=0}^{\infit }a_{n}x^{n}}}}}$

그리고

${\displaystyle g(x)=\sum _{n=0}^{\n=}s_{n}x^{n}}}}}$

그때

${\displaystyle g(x)=(tf)(x)={\frac {1}{1-x}f\왼쪽({\frac {-x}{1-x}}\오른쪽).}$

오일러 변환

일반적인 생성함수 사이의 관계를 오일러 변환이라고도 한다.그것은 보통 두 가지 다른 방법 중 하나로 등장한다.한 형태로, 교대계열의 정합화를 가속화하기 위해 사용된다.즉, 사람은 정체성을 가지고 있다.

${\displaystyle \sum \{n=0}^{n1}a_{n}=\sum _{n=0}^{n=0}^{n1}-1)^{n}{\frac {(\Delta ^{n}a)_{0}{2^{n+1}:{n+1}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}.$

위의 마지막 공식에 x = 1/2을 대입하여 얻는다.오른쪽의 용어는 일반적으로 훨씬 더 작아지고, 훨씬 더 빠르게 증가하며, 따라서 빠른 숫자의 합계가 가능하다.

오일러 변환은 일반화할 수 있다(Borisov B. 및 Shkodrov V, 2007).

${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}{n+p \choose n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{n+p \choose n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+p+1}}},}$

여기서 p = 0, 1, 2,…

오일러 변환은 오일러 초기하학 적분 2 ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}:{1$}:{$1}에도 자주 적용된다$.$ 여기서 오일러 변환은 다음과 같은 형식을 취한다.

${\displaystyle \,_{2}F_{1}(a,b;c;z)=(1-z)^{-b}\,_{2}F_{1}\좌측(c-a,b;c;{\frac {z}{z-1}\right)}$

이항변환과 오일러변환으로서의 변형은 숫자의 지속적인 분수표현과 연관성이 있다는 점에서 주목할 만하다.< < ${\displaystyle 0<x<1$}을(를$)$ 계속 부분 표시하도록 한다.

${\displaystyle x=[0;a_{1},a_{2},a_{3},\cdots ]}$

그때

${\displaystyle {\frac}{1-x}=[0;a_{1}-1,a_{2},a_{3},\cdots ]}$

그리고

${\displaystyle {\frac}{1+x}=[0;a_{1}+1,a_{2},a_{3},\cdots ].}$

지수생성함수

지수 생성 함수의 경우

${\displaystyle {\f}(x)=\sum _{n=0}^{\n}a_{n}{\frac{x^{n}}{n!}}}$

그리고

${\displaystyle {\coverline{g}}(x)=\sum _{n=0}^{n}{\frac{x^{n}{n!}}}$

그때

${\displaystyle {\overline{g}(x)=(T{\overline{f})(x)=e^{x}{\overline{f}(-x).}$

보렐 변환은 일반 발생 함수를 지수 생성 함수로 변환한다.

적분표현

복잡한 분석 함수에 의해 시퀀스를 보간할 수 있는 경우, 보간 기능에 통합된 Nörlund-Rice를 사용하여 시퀀스의 이항 변환을 나타낼 수 있다.

일반화

Prodinger는 다음과 같은 모듈형 변환 기능을 제공한다.

${\displaystyle u_{n}=\sum _{k=0}^{n}{n \선택 k}a^{k}(-c)^{n-k}b_{k}}}}}$

주다

${\displaystyle U(x)={\frac {1}{cx+1}B\왼쪽({\frac {ax}{cx+1}\오른쪽)}$

여기서 U와 B는 각각${\displaystyle }${${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \{u_{n}\}}$ 및$$ {${\displaystyle b_{}}{\displaystyle {}_{}}$ ${\displaystyle \{b_{n}\}}}$과$($와) 관련된 일반적인 생성 함수다.

상승 k-이항 변환은 때때로 다음과 같이 정의된다.

${\displaystyle \sum _{j=0}^{n}{n \선택 j}j^{k}a_{j}.}$

떨어지는 k-이항 변환은

${\displaystyle \sum _{}^{}}$ ${\displaystyle \underset{}{\overset{}{j}}}$= ${\displaystyle \underset{}{\overset{}{0}}}$ ${\displaystyle \underset{}{\overset{}{}}}$( ${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$ ${\displaystyle j}$) ${\displaystyle j^{}}$ -${\displaystyle k^{}}$ ${\displaystyle j_{}}$ ${\$\n \$선택 j}j^{n-k}a_{j$

둘 다 한켈 시리즈 변형의 알맹이의 동형상이다.

이항 변환이 다음과 같이 정의된 경우

${\displaystyle \sum _{i=0}^{n-i}^{n-i}{n}{n}}{n}}{n}a_{i}=b_{n}.}$

$함수{\displaystyle \mathfrak{}}$ J (${\displaystyle a{}_{}}$)${\displaystyle {}_{}{n}_{}}$ = ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$. ${\displaystyle {\mathfrak{J}(a)_{n}=b_{n}.$$}$

새로운 순방향 차이 테이블을 만들고 이 테이블의 각 행에서 첫 번째 요소를 취하여 새 시퀀스${\displaystyle }${${\displaystyle {bn}_{}}$ ${\displaystyle \{b_{n}\}}}$을$($를) 형성하는 경우 원래 시퀀스의 두 번째 이항 변환은 다음과 같다.

${\displaystyle {\mathfrak{J}^{2}(a)_{n}=\sum _{i=0}^{n-i}{n-i}{n}a_{i}.}$

만약 같은 과정이 k번 반복된다면, 그것은 그 과정을 따른다.

${\displaystyle {\mathfrak{J}^{k}(a)_{n}=b_{n}=\sum _{i=0}^{n-i}^{\binom {n}{i}a_{i}.}$

그 반대는,

${\displaystyle {\mathfrak{J}^{-k}(b)_{n}=a_{n}=\sum _{i=0}^{n-i}{\binom {n}b_{i}.}$

이는 다음과 같이 일반화될 수 있다.

${\displaystyle {\mathfrak{J}^{k}(a)_{n}=b_{n}=(\mathbf {E} -k)^{n}a_{0}}}$

여기서 $E{\displaystyle \mathbf{}}$ ${\$은$($는) 시프트 연산자다.

그것의 역은

${\displaystyle {\mathfrak{J}^{-k}(b)_{n}=a_{n}=(\mathbf {E} +k)^{n}b_{0}.}$

참고 항목

• 뉴턴 시리즈
• 행클 매트릭스
• 뫼비우스 변환
• 스털링 변환
• 오일러 합계
• 이항 QMF
• 요인 및 이항 항목 목록

참조

• 존 H. 콘웨이와 리처드 K.1996년 '숫자책' 가이
• 도널드 크누스, 컴퓨터 프로그래밍의 기술 제3권 (1973) 애디슨 웨슬리, 리딩, MA.
• 헬무트 프로딩거, 1992년, 이항변환에 관한 몇 가지 정보
• 마이클 Z.스피비와 로라 L.Steil, 2006, The k-Binomial Transforms and the Hankel Transforms
• 보리스노프 B.와 슈코드로프 V., 2007, 일반화 이항변환 다이버전트 시리즈, Adv. Stud.수학, 14(1): 77-82
• 크리스토 N.보야지예프, 이항 변환, 이론 및 표에 대한 노트, 스털링 변환(2018), 월드 사이언티픽 부록.

외부 링크

• 이항 변환
• 정수 시퀀스의 변환