Нумерація Кантора

Нумерація — це бієкція між певною множиною об'єктів, та множиною натуральних чисел.

Введемо однозначні ефективні нумерації пар та n-ок натуральних чисел, які називаються канторовими нумераціями.

Всі пари натуральних чисел розташуємо в послідовність так: пара (x, y) передує парі (u, v) ⇔ x+y<u+v або (x+y = u+v та x<u).

Номер пари (x, y) в такій послідовності позначають C(x, y) та називають канторовим номером пари (x, y). Неважко переконатись, що C(x, y) = [(x+y+1)⋅(x+y)/2]+x^[1].

Ось її табулювання:

 0   1   3   6  10  15  21  28  36  45
 2   4   7  11  16  22  29  37  46  56
 5   8  12  17  23  30  38  47  57  68
 9  13  18  24  31  39  48  58  69  81
14  19  25  32  40  49  59  70  82  95
20  26  33  41  50  60  71  83  96 110
27  34  42  51  61  72  84  97 111 126
35  43  52  62  73  85  98 112 127 143
44  53  63  74  86  99 113 128 144 161
54  64  75  87 100 114 129 145 162 180

Ліву та праву компоненти пари з номером n позначають відповідно l(n) та r(n). Функції l(n) та r(n) називають відповідно лівою та правою координатними функціями.

Подібна нумерація застосовувалась при доведенні зліченності множини раціональних чисел, якщо їх вважати їх парами з цілих чисельника і знаменника.

Функції C, l та r зв'язані тотожностями:

C(l(n), r(n)) = n;
l(C(x, y)) = x;
r(C(x, y)) = y.

Маючи нумерацію пар натуральних чисел, можна ввести нумерацію n-ок натуральних чисел для довільного n>2:

Cn(x1, x2,..., xn) = Cn-1(C(x1, x2), x3,..., xn) = C(...С(C(x1, x2), x3),...), xn).

Обернена нумерація обчислюється так^[2]:

def C_1(S):
	n = int((sqrt(1+8*S)-1)/2)
	k = S - (n+1)*n/2
	return (k, n-k)

1. ↑ CybWiki - кодування і нумерації
2. ↑ CybWiki джерело неавторитетне, але дані можна підтвердити експериментами