カントールの対関数の漸化式

カントールの対関数の漸化式

カントールの対関数は以下の漸化式を満たす。

(1)

\[ \pi\left(m,n\right)+1=\begin{cases} \pi\left(m-1,n+1\right) & m\ne0\\ \pi\left(n+1,0\right) & m=0 \end{cases} \]

(2)

\[ \pi\left(m,n\right)-1=\begin{cases} \pi\left(m+1,n-1\right) & n\ne0\\ \pi\left(0,m-1\right) & n=0\land m\ne0\\ -1 & n=0\land m=0 \end{cases} \]

-

\(\pi\left(m,n\right)\)はカントールの対関数

\[ \pi\left(m,n\right)=\frac{\left(m+n\right)\left(m+n+1\right)}{2}+n \]

(1)

\(m\ne0\)のとき、

\begin{align*} \pi\left(m,n\right)+1 & =\frac{\left(m+n\right)\left(m+n+1\right)}{2}+n+1\\ & =\frac{\left(\left(m-1\right)+\left(n+1\right)\right)\left(\left(m-1\right)+\left(n+1\right)+1\right)}{2}+\left(n+1\right)\\ & =\pi\left(m-1,n+1\right) \end{align*}

\(m=0\)のとき、

\begin{align*} \pi\left(0,n\right)+1 & =\frac{n\left(n+1\right)}{2}+n+1\\ & =\frac{\left(n+2\right)\left(n+1\right)}{2}\\ & =\frac{\left(0+\left(n+1\right)\right)\left(0+\left(n+1\right)+1\right)}{2}+0\\ & =\pi\left(n+1,0\right) \end{align*}

故に与式は成り立つ。

(2)

\(n\ne0\)のとき、

(1)より、

\begin{align*} \pi\left(m,n\right) & =\pi\left(m-1,n+1\right)-1\\ & =\pi\left(m+1,n-1\right)+1 \end{align*}

これより、

\[ \pi\left(m,n\right)-1=\pi\left(m+1,n-1\right) \]

\(n=0\land m\ne0\)のとき、

(1)より、

\[ \pi\left(m,0\right)-1=\pi\left(0,m-1\right) \]

\(n=0\land m=0\)のとき、

\[ \pi\left(0,0\right)-1=-1 \]

これより、

\[ \pi\left(m,n\right)-1=\begin{cases} \pi\left(m+1,n-1\right) & n\ne0\\ \pi\left(0,m-1\right) & n=0\land m\ne0\\ -1 & n=0\land m=0 \end{cases} \]

となるので、与式は成り立つ。

-

漸化式から関数を導出してみる。

\(m\ne0\)のとき、

\begin{align*} \pi\left(m,n\right) & =\pi\left(m-1,n+1\right)-1\\ & =\pi\left(0,n+m\right)+\sum_{k=0}^{m-1}\left\{ \pi\left(m-k,n+k\right)-\pi\left(m-k-1,n+k+1\right)\right\} \\ & =\pi\left(0,n+m\right)-\sum_{k=0}^{m-1}1\\ & =\pi\left(0,n+m\right)-m\\ & =\pi\left(n+m+1,0\right)-m-1\\ & =\pi\left(0,n+m+1\right)-\left(n+m+1\right)-m-1\\ & =\pi\left(0,n+m+1\right)-\left(n+2m+2\right)\\ & =-\left(n+2m+2\right)+\pi\left(0,0\right)+\sum_{k=0}^{n+m}\left\{ \pi\left(0,n+m+1-k\right)-\pi\left(0,n+m-k\right)\right\} \\ & =-\left(n+2m+2\right)+\pi\left(0,0\right)+\sum_{k=0}^{n+m}\left(\left(n-k\right)+2m+2-m\right)\\ & =-\left(n+2m+2\right)+\pi\left(0,0\right)+\sum_{k=0}^{n+m}\left(n+m+2-k\right)\\ & =-\left(n+2m+2\right)+\pi\left(0,0\right)+\sum_{k=0}^{n+m}\left(n+m+2\right)+\sum_{k=0}^{n+m}k\\ & =-\left(n+2m+2\right)+\pi\left(0,0\right)+\left(n+m+2\right)\left(n+m+1\right)+\frac{\left(n+m\right)\left(n+m+1\right)}{2}\\ & =-\left(n+2m+2\right)+\pi\left(0,0\right)+\frac{\left(n+m+4\right)\left(n+m+1\right)}{2}\\ & =-\left(n+2m+2\right)+\pi\left(0,0\right)+\frac{\left(n+m\right)\left(n+m+1\right)}{2}+2\left(n+m+1\right)\\ & =\frac{\left(n+m\right)\left(n+m+1\right)}{2}+n \end{align*}

となるが\(m=0\)でもこの式は成り立つ。
これより、漸化式より関数が導けた。

ページ情報

タイトル

カントールの対関数の漸化式

URL

https://www.nomuramath.com/up5giaub/

SNSボタン