カントールの対関数の逆関数

カントールの対関数の逆関数

カントールの対関数

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

の逆関数は

\[ t=\left\lfloor \frac{-1+\sqrt{1+8\pi}}{2}\right\rfloor \]

とおくと、

\[ \begin{cases} m=\frac{t^{2}+3t}{2}-\pi\\ n=\pi-\frac{t^{2}+t}{2} \end{cases} \]

となる。

逆関数が存在するので、カントールの対関数\(\pi:\mathbb{N}_{0}^{\;2}\rightarrow\mathbb{N}_{0}\)は全単射となる。

\(t=m+n\)とおくと、

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

カントールの対関数は

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

を満たす。
また、カントールの対関数は

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

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

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

を満たすので、

\[ \pi\left(m+n,0\right)\leq\pi\left(m,n\right)\leq\pi\left(0,m+n\right)<\pi\left(m+n+1,0\right) \]

となる。
これらを使うと、

\[ \pi\left(m+n,0\right)=\frac{t^{2}+t}{2}\leq\pi\left(m,n\right)=\frac{t^{2}+t}{2}+n<\pi\left(m+n+1,0\right)=\frac{\left(t+1\right)^{2}+t+1}{2} \]

となる。
これを整理すると、

\[ \begin{cases} t^{2}+t-2\pi\leq0\\ \left(t+1\right)^{2}+\left(t+1\right)-2\pi>0 \end{cases} \]

これを解くと、

\[ \begin{cases} \frac{-1-\sqrt{1+8\pi}}{2}\leq t\leq\frac{-1+\sqrt{1+8\pi}}{2}\\ t+1<\frac{-1-\sqrt{1+8\pi}}{2}\lor\frac{-1+\sqrt{1+8\pi}}{2}<t+1 \end{cases} \]

\(0\leq t\)なので、

\[ t\leq\frac{-1+\sqrt{1+8\pi}}{2}<t+1 \]

これより、

\[ t=\left\lfloor \frac{-1+\sqrt{1+8\pi}}{2}\right\rfloor \]

となるので、

\[ \begin{cases} m=t-n\\ n=\pi-\frac{t^{2}+t}{2} \end{cases} \]

故に

\[ \begin{cases} m=\frac{t^{2}+3t}{2}-\pi\\ n=\pi-\frac{t^{2}+t}{2} \end{cases} \]

となる。


ページ情報

タイトル

カントールの対関数の逆関数

URL

https://www.nomuramath.com/hvuopxsb/

SNSボタン