カントールの対関数の逆関数
カントールの対関数の逆関数
カントールの対関数
\[ \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ボタン |