カンターのペアリング機能

対角引数に加えて、Georg CantorはCantorペアリング関数\(\mathbb{N}^2 \to \mathbb{W}, \quad c(x,y) = \binom{x+y+1}{2}+x = z\)も開発しました\(\mathbb{N}^2 \to \mathbb{W}, \quad c(x,y) = \binom{x+y+1}{2}+x = z\) 、これは任意の2つの数値\(x,y \in \mathbb{N}\)を新しい数値\(z \in \mathbb{N}\)エンコードします。 たとえば、 \(c(3,4)=\binom{3+4+1}{2}+3 = \binom{8}{2}+3=\frac{8!}{6!\cdot 2!} +3 = 31 = z\)数値\(31\)内の数値\(3\)および\(4\)一意のコーディング。 表示:値のセット\(\mathbb{W} = \mathbb{N}\) 。つまり、 \(z\)はすべて自然数と見なします。


次の表の特別な構造を証明します:

  0 1 2 3 ...
0 0 2 5 9 ...
1 1 4 8 13 ...
2 3 7 12 18 ...
3 6 11 17 24 ...
... ... ... ... ... ...

したがって、 \(x > 0, y \geq 0\)
$$
c(x + 1、y)-c(x、y + 1)=
$$
$$
\ binom {x + 1 + y + 1} {2} + x + 1-\ left(\ binom {x + y + 1 + 1} {2} + x \ right))= \ binom {x + y + 2} {2}-\ binom {x + y + 2} {2} + x-x + 1 = 1
$$
同様に\(x \geq 0\)
$$
c(0、x + 1)-c(x、0)=
$$
$$
\ binom {0 + x + 1 + 1} {2} + 0-\ binom {x + 0 + 1} {2}-x = \ binom {x + 2} {2}-\ binom {x + 1} {2}-x =
$$
$$
\ frac {(x + 2)!} {2! x!}-\ frac {(x + 1)!} {2!(x-1)!}-x =
$$
$$
\ frac {(x + 2)(x + 1)} {2}-\ frac {(x + 1)x} {2}-x = \ frac {(x + 1)\ left((x + 2) -x \ right)} {2}-x = x + 1-x = 1
$$
つまり、すべての自然数が達成されます。

バック