Why Pair the Natural Numbers?
To list the ordered pairs of natural numbers, we need an ordering that eventually reaches every pair. Listing first all pairs with first coordinate \(1\), then all pairs with first coordinate \(2\), and so on will not work: after beginning the first row, the list never finishes that row. Instead, group pairs by the sum of their coordinates. Each group is finite, and moving through these groups gives a systematic way to list all pairs.
Throughout, \(\mathbb{N}=\{1,2,3,\ldots\}\), and \(\mathbb{N}\times\mathbb{N}\) is the set of ordered pairs \((i,j)\) with \(i,j\in\mathbb{N}\). The order of the coordinates matters: \((i,j)\) and \((j,i)\) are different pairs when \(i\ne j\).
Within each diagonal, list pairs in increasing order of the first coordinate. The first few entries are therefore \((1,1)\), then \((1,2),(2,1)\), then \((1,3),(2,2),(3,1)\). To turn this listing into a formula, we count how many pairs occur before a diagonal and then count a pair's position within that diagonal.
Counting the Diagonals
Proof. A pair in \(D_t\) has \(i+j=t+2\). For each integer \(i\) from \(1\) through \(t+1\), there is exactly one possible second coordinate, namely \(j=t+2-i\), and it is positive. These are all the pairs in \(D_t\), so there are \(t+1\) of them. The diagonals before \(D_t\) are \(D_0,\ldots,D_{t-1}\), so their total number of pairs is \(1+2+\cdots+t=t(t+1)/2\). For \(t=0\), this is an empty sum and equals \(0\), as does \(T_0=0\). \(\square\)
The number \(T_t\) is a triangular number. The first entry of \(D_t\) has position \(T_t+1\), because precisely \(T_t\) entries come earlier. If \((i,j)\in D_t\), then \(i\) is its position within that diagonal: the pairs there have first coordinates \(1,2,\ldots,t+1\), in that order.
Worked Examples of the Diagonal Listing
Worked Example: Listing the First Six Pairs
We compute the first three diagonals and their positions. For \(t=0\), \(T_0=0(0+1)/2=0\). The only pair is \((1,1)\), and its code is \(c(1,1)=T_0+1=1\).
For \(t=1\), \(T_1=1(1+1)/2=1\). The pairs in order are \((1,2)\) and \((2,1)\), with codes \(T_1+1=2\) and \(T_1+2=3\). For \(t=2\), \(T_2=2(2+1)/2=3\). The pairs \((1,3),(2,2),(3,1)\) have codes \(T_2+1=4\), \(T_2+2=5\), and \(T_2+3=6\).
Check: The displayed codes are \(1,2,3,4,5,6\), with no repetition or gap. Each computed code agrees with \(T_t+i\), where \(t=i+j-2\). For example, \((2,2)\) has \(t=2+2-2=2\), so its code is \(T_2+2=3+2=5\).
To decode a natural number \(n\), first determine which diagonal contains position \(n\). Since diagonal \(D_t\) begins just after position \(T_t\) and ends at position \(T_{t+1}\), the correct diagonal is characterized by \(T_t<n\le T_{t+1}\). The strict inequality at the left is important: \(T_t\) counts the entries before the diagonal, not an entry in it.
Proof. Fix \(n\in\mathbb{N}\) and set \(y=(\sqrt{8n-7}-1)/2\). Since \(8n-7\ge1\), \(y\ge0\), so \(t=\lfloor y\rfloor\) is a nonnegative integer and \(t\le y<t+1\). Adding \(1\), multiplying by \(2\), and squaring the nonnegative quantities gives \((2t+1)^2\le 8n-7<(2t+3)^2\). The left inequality implies \(8n\ge4t^2+4t+8\), hence \(n\ge t(t+1)/2+1=T_t+1\). The right inequality implies \(8n<4t^2+12t+16\), hence \(n<T_{t+1}+1\). Since \(n\) and \(T_{t+1}\) are integers, \(n\le T_{t+1}\). Therefore \(T_t<n\le T_{t+1}\).
It follows that \(i=n-T_t\) satisfies \(1\le i\le T_{t+1}-T_t=t+1\). Thus \(i\) is positive, and \(j=t+2-i\ge1\); also \(i+j=t+2\), so \(E(n)\) lies in \(D_t\). Its code is \(c(i,j)=T_t+i=T_t+(n-T_t)=n\).
Conversely, take any \((i,j)\in\mathbb{N}\times\mathbb{N}\), put \(t=i+j-2\), and let \(n=c(i,j)=T_t+i\). Because \(1\le i\le t+1\), we have \(T_t<n\le T_t+t+1=T_{t+1}\). The floor formula therefore recovers this same \(t\): equivalently, the inequalities \(T_t<n\le T_{t+1}\) give \(t\le(\sqrt{8n-7}-1)/2<t+1\). The decoding then gives \(n-T_t=i\) and \(t+2-i=j\). Hence \(E(c(i,j))=(i,j)\). The two formulas are inverse in both directions, so \(E\) is a bijection. In particular, every pair occurs, and no pair occurs twice. \(\square\)
Encoding and Decoding in Practice
Worked Example: Encoding the Pair \((4,2)\)
For \((4,2)\), the diagonal index is \(t=4+2-2=4\). The number of entries before that diagonal is \(T_4=4(4+1)/2=10\), and the pair is fourth within its diagonal. Therefore \(c(4,2)=T_4+4=10+4=14\).
Now decode \(n=14\). The formula gives \(t=\lfloor(\sqrt{8(14)-7}-1)/2\rfloor=\lfloor(\sqrt{105}-1)/2\rfloor\). Since \(10^2=100<105<121=11^2\), we have \(10<\sqrt{105}<11\), and therefore \(4.5<(\sqrt{105}-1)/2<5\). Its floor is \(4\). Thus \(i=14-T_4=14-10=4\), and \(j=4+2-4=2\).
Check: Re-encoding the decoded pair gives \(c(4,2)=10+4=14\), the starting number. The inequalities also confirm the diagonal condition \(T_4=10<14\le15=T_5\).
Worked Example: Decoding \(17\)
Substitute \(n=17\) into the diagonal formula. The radicand is \(8(17)-7=136-7=129\), so \(t=\lfloor(\sqrt{129}-1)/2\rfloor\). Since \(11^2=121<129<144=12^2\), we have \(11<\sqrt{129}<12\), and hence \(5<(\sqrt{129}-1)/2<5.5\). Thus \(t=5\). Compute \(T_5=5(5+1)/2=15\), then \(i=17-15=2\) and \(j=5+2-2=5\). Therefore \(E(17)=(2,5)\).
Check: The pair has diagonal index \(2+5-2=5\). Its code is \(T_5+2=15+2=17\). Also \(T_5=15<17\le21=T_6\), as required for the fifth diagonal.
Worked Example: Decoding the End of a Diagonal
Take \(n=15\). The formula gives \(t=\lfloor(\sqrt{8(15)-7}-1)/2\rfloor=\lfloor(\sqrt{113}-1)/2\rfloor\). Since \(10^2=100<113<121=11^2\), we have \(10<\sqrt{113}<11\), so \(4.5<(\sqrt{113}-1)/2<5\). Thus \(t=4\). Now \(T_4=4(5)/2=10\), so \(i=15-10=5\) and \(j=4+2-5=1\). The decoded pair is \((5,1)\).
Check: The pair lies in diagonal \(D_4\), since \(5+1-2=4\), and its code is \(T_4+5=10+5=15\). This is the last position of that diagonal because \(T_5=5(6)/2=15\); the next diagonal starts at position \(T_5+1=16\).
A Common Off-by-One Error
Pitfall. A tempting alternative is to use \(\lfloor(\sqrt{8n+1}-1)/2\rfloor\) for the diagonal index. This mixes the diagonal numbering with a different triangular-number convention. For \(n=1\), it gives \(\lfloor(\sqrt{9}-1)/2\rfloor=\lfloor(3-1)/2\rfloor=1\). Then \(T_1=1\) and the decoding rule would give \(i=1-T_1=0\), which is not in \(\mathbb{N}\). That cannot decode the first position.
The correction is to use \(8n-7\), which comes from solving the actual diagonal condition \(T_t<n\le T_{t+1}\). At \(n=1\), it gives \(t=\lfloor(\sqrt{1}-1)/2\rfloor=0\), then \(i=1-T_0=1\) and \(j=0+2-1=1\). Re-encoding confirms \(c(1,1)=T_0+1=1\). Keeping track of whether a triangular number counts entries before a diagonal or through its end prevents this error.
What the Pairing Achieves
The diagonal construction is more than a visual ordering: the formulas prove that the list is complete and has no repetitions. The code sends each ordered pair to one natural-number position, while the floor formula recovers the pair at any specified position. Because the formulas are inverse, the construction establishes an explicit bijection between \(\mathbb{N}\) and \(\mathbb{N}\times\mathbb{N}\). It also illustrates a useful general strategy for explicit enumerations: divide an infinite set into finite layers, count the layers before a given element, and then count its position inside its layer.
Check Your Understanding
Use the diagonal index \(t=i+j-2\), the triangular number \(T_t=t(t+1)/2\), and the stated decoding formula.
- List the pairs in \(D_3\) in the prescribed order and compute the code of each.
- Encode \((3,4)\). State its diagonal index, the number of earlier pairs, and its position within the diagonal.
- Decode \(n=8\), showing the integer-square bounds used to determine the floor.
- Explain why the condition locating diagonal \(D_t\) is \(T_t<n\le T_{t+1}\), rather than \(T_t\le n<T_{t+1}\).
- Use the inverse formulas to explain why two different pairs cannot have the same code.