A pairing function is a function that reversibly maps onto , where denotes nonnegative integers. Pairing functions arise naturally in the demonstration that the cardinalities of the rationals and the nonnegative integers are the same, i.e., , where is known as aleph-0, originally due to Georg Cantor. Pairing functions also arise in coding problems, where a vector of integer values is to be folded onto a single integer value reversibly.

5	15	20	26	33	41
4	10	14	19	25	32
3	6	9	13	18	24
2	3	5	8	12	17
1	1	2	4	7	11
	1	2	3	4	5

Let

(1)

then Hopcroft and Ullman (1979, p. 169) define the pairing function

			(2)
			(3)

illustrated in the table above, where . The inverse may computed from

			(4)
			(5)
			(6)
			(7)

where is the floor function.

5	15	22	30	39	49	60
4	10	16	23	31	40	50
3	6	11	17	24	32	41
2	3	7	12	18	25	33
1	1	4	8	13	19	26
0	0	2	5	9	14	20
	0	1	2	3	4	5

The Hopcroft-Ullman function can be reparameterized so that and are in rather than . This function is known as the Cantor function and is given by

(8)

illustrated in the table above. Its inverse is then given by

			(9)
			(10)
			(11)

A theorem due to Fueter and Pólya states that Cantor's pairing function and Hopcroft and Ullman's variant are the only quadratic functions with real-valued coefficients that maps onto reversibly (Stein 1999, pp. 448-452).

11	20	24	33	41
10	12	19	25	32
4	9	13	18	26
3	5	8	14	17
1	2	6	7	15

17	18	19	20	21
16	15	14	13	22
5	6	7	12	23
4	3	8	11	24
1	2	9	10	25

Stein (1999) proposed two boustrophedonic ("ox-plowing") variants, shown above, although without giving explicit formulas.

7	42	43	46	47	58	59	62	63
6	40	41	44	45	56	57	60	61
5	34	35	38	39	50	51	54	55
4	32	33	36	37	48	49	52	53
3	10	11	14	15	26	27	30	31
2	8	9	12	13	24	25	28	29
1	2	3	6	7	18	19	22	23
0	0	1	4	5	16	17	20	21
	0	1	2	3	4	5	6	7

There are also other ways of defining pairing functions. For example, Pigeon (2001, p. 115) proposed a pairing function based on bit interleaving. This "bitwise" pairing function, illustrated above, is defined

(12)

where (and ) are the least significant bit of (or ), is a concatenation operator, and the symbol is the empty bit string

To pair more than two numbers, pairings of pairings can be used. For example can be defined as or , but should be defined as to minimize the size of the number thus produced. The general scheme is then

			(13)
			(14)
			(15)
			(16)
			(17)

and so on.

This entry contributed by Steven Pigeon

Hopcroft, J. E. and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison Wesley, 1979.

Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001.

Stein, S. K. Mathematics: The Man-Made Universe. New York: McGraw-Hill, 1999.

CITE THIS AS:

Pigeon, Steven. "Pairing Function." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/PairingFunction.html