조합론(combinatorics)에서, 이항 변환(binomial transform)은 순방향 차이(forward differences)를 계산하는 수열 변환(sequence transformation, 즉, 수열의 변환)입니다. 그것은 보통의 생성하는 함수(ordinary generating function)와 결합된 수열에 이항 변환을 적용한 결과인 오일러 변환(Euler transform)과 밀접한 관련이 있습니다.
Definition
수열 \(\{a_n\}\)의 이항 변환(binomial transform), T는 다음에 의해 정의된 수열 \(\{s_n\}\)입니다:
\(\quad\displaystyle s_n = \sum_{k=0}^n (-1)^k {n\choose k} a_k.\)
형식적으로, 그 변환에 대해 다음과 같이 쓸 수 있습니다:
\(\quad\displaystyle s_n = (Ta)_n = \sum_{k=0}^n T_{nk} a_k\)
여기서 T는 행렬 원소 \(T_{nk}\)를 갖는 무한-차원 연산자(operator)입니다. 그 변환은 인볼루션(involution)입니다, 즉,
\(\quad\displaystyle TT = 1\)
또는, 인덱스 표기법을 사용하여,
\(\quad\displaystyle \sum_{k=0}^\infty T_{nk}T_{km} = \delta_{nm}\)
여기서 \(\delta_{nm}\)는 크로네커 델타(Kronecker delta)입니다. 원래 급수는 다음에 의해 다시 얻을 수 있습니다:
\(\quad\displaystyle a_n=\sum_{k=0}^n (-1)^k {n\choose k} s_k.\)
수열의 이항 변환은 수열의 n-번째 순방향 차이(forward differences)이며, 홀수 차이는 음의 부호를 수반합니다. 즉:
\(\quad\displaystyle \begin{align}
s_0 &= a_0 \\
s_1 &= - (\Delta a)_0 = -a_1+a_0 \\
s_2 &= (\Delta^2 a)_0 = -(-a_2+a_1)+(-a_1+a_0) = a_2-2a_1+a_0 \\
&\;\; \vdots \\
s_n &= (-1)^n (\Delta^n a)_0
\end{align}\)
여기서 Δ는 순방향 차이 연산자(forward difference operator)입니다.
일부 저자는 그것이 자체-역이 아니도록 여분의 부호를 갖는 이항 변환을 정의합니다:.
\(\quad\displaystyle t_n = \sum_{k=0}^n (-1)^{n-k} {n\choose k} a_k\)
그것의 역은 다음과 같습니다:
\(\quad\displaystyle a_n=\sum_{k=0}^n {n\choose k} t_k.\)
이 경우에서, 전자의 변환은 역 이항 변환(inverse binomial transform)이라고 불리고, 후자는 단지 이항 변환입니다. 이것은 예를 들어 On-Line Encyclopedia of Integer Sequences에서 표준 사용법입니다.
Example
이항 변환의 두 버전 모두 다른 테이블에 나타납니다. 다음 차이 테이블을 생각해 보십시오:
| 0 | 1 | 10 | 63 | 324 | 1485 | |||||
| 1 | 9 | 53 | 261 | 1161 | ||||||
| 8 | 44 | 208 | 900 | |||||||
| 36 | 164 | 692 | ||||||||
| 128 | 528 | |||||||||
| 400 |
각 줄은 이전 줄의 차이입니다. (m-번째 줄의 n-번째 숫자는 \(a_{m,n}=3^{n-2}(2^{m+1}n^2+2^m (1+6m)n+2^{m-1}9m^2)\)이고, 차이 방정식 \(a_{m+1,n}=a_{m,n+1}-a_{m,n}\)이 유지됩니다.)
왼쪽에서 오른쪽으로 읽은 맨 위 줄은 \(\{a_n\}=0,1,10,63,324,1485, ...\)입니다. 같은 시작하는 점 0을 갖는 대각선은 \(\{t_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\}\)의 인볼루션 이항 변환입니다.
Ordinary generating function
그 변환은 급수와 결합된 생성하는 함수(generating functions)를 연결합니다. 보통의 생성하는 함수(ordinary generating function)에 대해, 다음 둘을 놓으면
\(\quad\displaystyle f(x)=\sum_{n=0}^\infty a_n x^n\)
및
\(\quad\displaystyle g(x)=\sum_{n=0}^\infty s_n x^n \)
다음과 같습니다:
\(\quad\displaystyle g(x) = (Tf)(x) = \frac{1}{1-x} f\left(\frac{-x}{1-x}\right).\)
Euler transform
보통의 생성하는 함수 사이의 관계는 때때로 오일러 변환(Euler transform)이라고 불립니다. 그것은 공통적으로 두 가지 방법 중 하나로 나타납니다. 한 형태에서, 그것은 교대 급수(alternating series)의 수렴을 가속화하기 위해 사용됩니다. 즉, 다음 항등식을 가집니다:
\(\quad\displaystyle \sum_{n=0}^\infty (-1)^n a_n = \sum_{n=0}^\infty (-1)^n \frac{(\Delta^n a)_0}{2^{n+1}}\)
이는 x = 1/2를 위의 마지막 공식에 대입함으로써 얻습니다. 오른쪽 변에 있는 항은 전형적으로 훨씬 더 작아지고, 훨씬 더 빠르게 되고, 따라서 빠른 수치 합계를 허용합니다.
오일러 변환은 다음과 같이 일반화될 수 있습니다 (Borisov B. and Shkodrov V., 2007):
\(\quad\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,…
오일러 변환은 역시 오일러 초기하 적분(Euler hypergeometric integral) \(\,_2F_1\)에서 자주 적용됩니다. 여기서, 오일러 변환은 다음과 같은 형식을 취합니다:
\(\quad\displaystyle \,_2F_1 (a,b;c;z) = (1-z)^{-b} \,_2F_1 \left(c-a, b; c;\frac{z}{z-1} \right).\)
이항 변환, 및 오일러 변환과 같은 변형은 숫자의 연속된 분수(continued fraction) 표현과의 연결로 유명합니다. \(0 < x < 1\)가 다음과 같은 연속된 분수 표현을 가진다고 가정합니다:
\(\quad\displaystyle x=[0;a_1, a_2, a_3,\cdots]\)
그런-다음
\(\quad\displaystyle \frac{x}{1-x}=[0;a_1-1, a_2, a_3,\cdots]\)
및
\(\quad\displaystyle \frac{x}{1+x}=[0;a_1+1, a_2, a_3,\cdots].\)
Exponential generating function
지수 생성하는 함수(exponential generating function)에 대해, 다음이라고 놓습니다:
\(\quad\displaystyle \overline{f}(x)= \sum_{n=0}^\infty a_n \frac{x^n}{n!}\)
및
\(\quad\displaystyle \overline{g}(x)= \sum_{n=0}^\infty s_n \frac{x^n}{n!}\)
그런-다음
\(\quad\displaystyle \overline{g}(x) = (T\overline{f})(x) = e^x \overline{f}(-x).\)
보렐 변환(Borel transform)은 보통의 생성하는 함수를 지수 생성하는 함수로 변환할 것입니다.
Integral representation
수열이 복소 해석적 함수에 의해 보간될 수 있을 때, 수열의 이항 변환은 보간하는 함수 위에 뇌룬드–라이스 적분(Nörlund–Rice integral)을 수단으로 나타낼 수 있습니다.
Generalizations
Prodinger는 관련된, 모듈러-같은(modular-like) 변환을 제공합니다: 다음이라고 놓습니다:
\(\quad\displaystyle u_n = \sum_{k=0}^n {n\choose k} a^k (-c)^{n-k} b_k\)
다음을 제공합니다:
\(\quad\displaystyle U(x) = \frac{1}{cx+1} B\left(\frac{ax}{cx+1}\right)\)
여기서 U와 B는 각각 급수 \(\{u_n\}\)와 \(\{b_n\}\)와 결합된 보통의 생성하는 함수입니다.
올라가는 k-이항 변환은 때때로 다음과 같이 정의됩니다:
\(\quad\displaystyle \sum_{j=0}^n {n\choose j} j^k a_j.\)
떨어지는 k-이항 변환은 다음입니다:
\(\quad\displaystyle \sum_{j=0}^n {n\choose j} j^{n-k} a_j\).
둘 다는 급수의 한켈 변환(Hankel transform of a series)의 커널(kernel)의 준동형입니다.
이항 변환이 다음과 같이 정의되는 경우에서
\(\quad\displaystyle \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}a_i=b_n.\)
이것을 함수 \(\mathfrak J(a)_n=b_n\)과 같다고 놓습니다.
만약 새로운 순방향 차이(forward difference) 테이블이 만들어지고 이 테이블의 각 행에서 첫 번째 원소가 새로운 수열 \(\{b_n\}\)을 형성하기 위해 취해지면, 원래 수열의 두 번째 이항 변환은 다음과 같습니다:
\(\quad\displaystyle \mathfrak J^2(a)_n=\sum_{i=0}^n(-2)^{n-i}\binom{n}{i}a_i.\)
만약 같은 과정이 k-번 반복되면, 다음임이 따라옵니다:
\(\quad\displaystyle \mathfrak J^k(a)_n=b_n=\sum_{i=0}^n(-k)^{n-i}\binom{n}{i}a_i.\)
그것의 역은 다음입니다:
\(\quad\displaystyle \mathfrak J^{-k}(b)_n=a_n=\sum_{i=0}^nk^{n-i}\binom{n}{i}b_i.\)
이것은 다음과 같이 일반화될 수 있습니다:
\(\quad\displaystyle \mathfrak J^k(a)_n=b_n=(\mathbf E-k)^na_0\)
여기서 \(\mathbf E\)는 미는 연산자(shift operator)입니다.
그것의 역은 다음입니다:
\(\quad\displaystyle \mathfrak J^{-k}(b)_n=a_n=(\mathbf E+k)^nb_0.\)
References
- John H. Conway and Richard K. Guy, 1996, The Book of Numbers
- Donald E. Knuth, The Art of Computer Programming Vol. 3, (1973) Addison-Wesley, Reading, MA.
- Helmut Prodinger, 1992, Some information about the Binomial transform
- Michael Z. Spivey and Laura L. Steil, 2006, The k-Binomial Transforms and the Hankel Transform
- Borisov B. and Shkodrov V., 2007, Divergent Series in the Generalized Binomial Transform, Adv. Stud. Cont. Math., 14 (1): 77-82
- Khristo N. Boyadzhiev, Notes on the Binomial Transform, Theory and Table, with Appendix on the Stirling Transform (2018), World Scientific.