カントールの対関数の逆関数
カントールの対関数の逆関数
カントールの対関数
\[ \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}\)は全単射となる。
カントールの対関数
\[ \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} \] となる。
\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ボタン |
カントールの対関数の漸化式
\[
\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}
\]
カントールの対関数の性質
\[
\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
\]