4.5: Альтернативна функція сполучення

Template:MathJaxZach

Є й інші перерахування\(\Nat^2\), які полегшують з'ясування, які їх зворотні. Ось один. Замість того, щоб візуалізувати зчислення в масиві, почніть зі списку натуральних чисел, пов'язаних з (спочатку) порожніми пробілами. Уявіть, що ці простори заповнюють послідовно парами\(\tuple{n,m}\), як показано нижче. Починаючи з пар, які мають\(0\) на першому місці (тобто пари\(\tuple{0,m}\)), поставте першу (тобто\(\tuple{0,0}\)) на перше порожнє місце, потім пропустіть порожній простір, другу (тобто\(\tuple{0,2}\)) поставте на наступне порожнє місце, пропустіть ще раз, і так вперед. (Неповний) початок нашого перерахування тепер виглядає так\[\small \begin{array}{@{}c c c c c c c c c c c@{}} \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\ \tuple{0,1} & & \tuple{0,2} & & \tuple{0,3} & & \tuple{0,4} & & \tuple{0,5} & & \dots \\ \end{array}\nonumber\] Повторіть це з парами\(\tuple{1,m}\) для місць, які все ще залишаються порожніми, знову пропускаючи кожне інше порожнє місце:\[\small \begin{array}{@{}c c c c c c c c c c c@{}} \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\ \tuple{0,0} & \tuple{1,0} & \tuple{0,1} & & \tuple{0,2} & \tuple{1,1} & \tuple{0,3} & & \tuple{0,4} & \tuple{1,2} & \dots \\ \end{array}\nonumber\] Введіть пари\(\tuple{2,m}\),\(\tuple{2,m}\), і т.д., таким же чином. Наше завершене перерахування, таким чином, починається так:\[\small \begin{array}{@{}cc c c c c c c c c c@{}} \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\ \tuple{0,0} & \tuple{1,0} & \tuple{0,1} & \tuple{2,0} & \tuple{0,2} & \tuple{1,1} & \tuple{0,3} & \tuple{3,0} & \tuple{0,4} & \tuple{1,2} & \dots \\ \end{array}\nonumber\] Якщо ми пронумеруємо осередки в масиві вище відповідно до цього перерахування, ми не знайдемо акуратну зигзагоподібну лінію, але таке розташування:\[\begin{array}{ c | c | c | c | c | c | c | c } & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \dots \\ \hline \mathbf 0 & 1 & 3 & 5 & 7 & 9 & 11 & \dots \\ \hline \mathbf 1 & 2 & 6 & 10 & 14 & 18 & \dots & \dots \\ \hline \mathbf 2 & 4 & 12 & 20 & 28 & \dots & \dots & \dots \\ \hline \mathbf 3 & 8 & 24 & 40 & \dots & \dots & \dots & \dots \\ \hline \mathbf 4 & 16 & 48 & \dots & \dots & \dots & \dots & \dots \\ \hline \mathbf 5 & 32 & \dots & \dots & \dots & \dots & \dots & \dots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array}\nonumber\] Ми бачимо, що пари в рядку\(0\) знаходяться в непарній пронумеровані місця нашого перерахування, тобто пара\(\tuple{0,m}\) знаходиться на місці\(2m+1\); пари в другому ряду,\(\tuple{1,m}\), знаходяться в місцях, чиє число двійник непарного числа, конкретно,\(2 \cdot (2m+1)\); пари в третьому ряду,\(\tuple{2,m}\), знаходяться в місцях, чиє число в чотири рази непарне число\(4 \cdot (2m+1)\), і так далі. Фактори\((2m+1)\) для кожного ряду,,,\(1\),\(2\),\(4\),\(8\),,,,,,,\(1= 2^0\),,,,,\(2 = 2^1\),\(4 = 2^2\),\(2\) \(8 = 2^3\),... Насправді відповідний показник завжди є першим членом пари, про яку йде мова. Таким чином, для пари\(\tuple{n,m}\) фактор є\(2^n\). Це дає нам загальну формулу:\(2^n \cdot (2m+1)\). Однак це відображення пар з додатними цілими числами, тобто\(\tuple{0,0}\) має позицію\(1\). Якщо ми хочемо почати з позиції,\(0\) ми повинні відняти\(1\) від результату. Це дає нам:

Приклад\(\PageIndex{1}\)

Функція,\(h\colon \Nat^2 \to \Nat\) задана\[h(n,m) = 2^n (2m+1) - 1\nonumber\], є функцією сполучення для множини пар натуральних чисел\(\Nat^2\).

Відповідно, в нашому другому перерахуванні\(\Nat^2\), пара\(\tuple{0,0}\) має код\(h(0,0) = 2^0(2\cdot 0+1) - 1 = 0\);\(\tuple{1,2}\) має код\(2^{1} \cdot (2 \cdot 2 + 1) - 1 = 2 \cdot 5 - 1 = 9\);\(\tuple{2,6}\) має код\(2^{2} \cdot (2 \cdot 6 + 1) - 1 = 51\).

Іноді досить закодувати пари натуральних чисел,\(\Nat^2\) не вимагаючи, щоб кодування було суб'єктивним. Такі кодування мають зворотні, які є лише частковими функціями.

Приклад\(\PageIndex{2}\)

Функція,\(j\colon \Nat^2 \to \Nat^+\) задана\[j(n,m) = 2^n3^m\nonumber\], є ін'єкційною функцією\(\Nat^2 \to \Nat\).