カントールの対関数の漸化式
カントールの対関数の漸化式
カントールの対関数は以下の漸化式を満たす。
\[ \pi\left(m,n\right)=\frac{\left(m+n\right)\left(m+n+1\right)}{2}+n \]
カントールの対関数は以下の漸化式を満たす。
(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ボタン |
カントールの対関数の逆関数
\[
\begin{cases}
m=\frac{t^{2}+3t}{2}-\pi\\
n=\pi-\frac{t^{2}+t}{2}
\end{cases}
\]
カントールの対関数の性質
\[
\pi\left(m+1,n\right)=\pi\left(m,n\right)+m+n+1
\]
カントールの対関数の定義
\[
\pi\left(m,n\right)=\frac{\left(m+n\right)\left(m+n+1\right)}{2}+n
\]