# Bijection between $\Bigl\{1, 2, \dots, \frac{N(N+1)}{2}\Bigr\}$ and $\{ (i, j) \in \mathbb{N} : i \le j \le N\}$

Let $N$ be some positive integer and $A$ be the following set

$\{ (i, j) \in \mathbb{N}^2 : 1 \le i \le j \le N\} = \{ (1, 1), (1, 2), \ldots, (1, N), (2, 2), (2, 3), \ldots, (2, N), \ldots, (N, N) \}$

I know that $A$ has $\frac{N(N+1)}{2}$ elements.

Also, let $B$ be the set $\Bigl\{1, 2, 3, \ldots, \frac{N(N+1)}{2} \Bigr\}$.

The function $f(i, j) = j + i \cdot N - \frac{i(i+1)}{2}$ is an injective function from $A$ to $B$ but I'm trying to find a injection from $B$ to $A$ and I am not having success.

I need this function to optimize a for loop in a program that only needs to care about the upper triangular part of a matrix (if you pay attention, you will see that $A$ has the indexes of a $N \times N$ upper triangular matrix...).

Does someone have any idea?

Thank you very much!

I will try to create a bijection for you. What we do is we count by rows. So the row $(1,1),\ldots,(1,N)$ ends on spots $1,\ldots,N$. We then start the next row at $(2,2)$ which needs to be put on $N+1$ and finish the row. So:

• $(1,1)\mapsto 1$
• $(2,2)\mapsto N+1$
• $(3,3)\mapsto 2N$
• $(4,4)\mapsto 3N-2$
• $(5,5)\mapsto 4N-5$
• $(6,6)\mapsto 5N-9$

etc.

What we need to do is to create a formula which determines the right starting position and adds 1 if we add one to our second coordinate. Ie $$(i,j)\mapsto(i-1)N + (j-i+1),$$ where the first term determines how many times $N$ we need and the second term starts counting from $+1$ for each step we move to the right/add 1 to $j$. However, as we see from the list we also need to subtract some value for each row from $i=3$ onward. Notice that this value equals $$\sum_{k=1}^{i-2}k = \frac{(i-2)(i-1)}{2}.$$ Therefore we add this term to get the result \begin{align*} \color{red}{(i-1)N + (j-i+1) - \frac{(i-2)(i-1)}{2}} \end{align*} Note that this function is strictly increasing in both $i$ and $j$ and that it equals $\frac{N(N+1)}{2}$ for $(i,j)=(N,N)$, making it a bijection.

• first of all, thank you for answering. So, what is the inverse function of this bijection? This is the point: I want a injection from $B$ to $A$... – Hilder Vítor Lima Pereira Sep 7 '15 at 17:29
• Suppose we have the number $1\le x \le \frac{N(N+1)}{2}$. We can choose $i$ the biggest integer such that $\sum_{k=1}^{i-1}(N+1-k) \le x$. Then set $j = (i-1) + x - \sum_{k=1}^{i-1}(N+1-k)$. – Marc Sep 9 '15 at 10:02

An injection from A to B is: $f(i,j) = i + j(j-1)/2 = n$

So solve $x^2-x-2(n-1)=0$ to find $j=\lfloor x\rfloor$ and use that to find $i$ .

In more detail, noting that we have for all (valid) $i$ and $j$: $f(1, j) \leq f(i,j)< f(1, j+1)$, then we can then assume there is some continuous function $g$ and some remainder $r_i: 0\leq r_i < 1$ where $f(i, j) = g(j+r_i)$.

Since $f(i, j) = i + j(j-1)/2$ a candidate is simply, $g(j) = j(j-1)/2$

Then we let $x=j+r_i$, find $x$ that solves $n = g(x)$, and thus obtain $j= \lfloor x\rfloor$ .

• Hi, @Graham Kemp. Could you please explain how you eliminated the variable $i$ to write the equation $x^2 - x - 2(n - 1) = 0$? – Hilder Vítor Lima Pereira Sep 7 '15 at 17:41
• @Vitor added some detail. – Graham Kemp Sep 7 '15 at 23:25

As I said in the question

I'm trying to find a injection from B to A.

I managed to do it in the following way: Fix some value for $N$ and distribute the values of the set $B = \Bigl\{1, 2, \ldots, \frac{N(N+1)}{2} \Bigr\}$ on the upper-triangular part of a $N \times N$ matrix. For instance, to $N = 5$, $B$ is $\{1, 2, 3, ..., 15\}$, so

$$\begin{bmatrix} 1 & 2 & 4 & 7 & 11\\ * & 3 & 5 & 8 & 12\\ * & * & 6 & 9 & 13\\ * & * & * & 10 & 14\\ * & * & * & * & 15\\ \end{bmatrix}$$

Now, note that each column $j$ has exactly $j$ elements. So, the first element of a given column $j$ is equal to the number of elements in all the previous column plus one: $(1 + 2 + 3 + ... + j - 1) + 1$.

Using the following formula to the sum of elements in a arithmetic progression:

$$1 + 2 + 3 + ... + j - 1 = \frac{j(j - 1)}{2}$$

we find that the first element of a given column $j$ is the value $\frac{j(j - 1)}{2} + 1$.

With the same analysis, we can see that the second element is $\frac{j(j - 1)}{2} + 2$ and so on.

Then, a value $k \in B$ is in column $j$ if and only if $k = \frac{j(j - 1)}{2} + l$ for some $1 \le l \le j$. Using Baskara to invert this equality, we get $j(k) = \frac{1 + \sqrt{1 + 8(k - l)}}{2}$.

Since this function $j$ grows assuming non integer values for $l \not = 1$, we can use $l = 1$ and take the floor:

$$j(k) = \Big\lfloor \frac{1 + \sqrt{1 + 8(k - 1)}}{2} \Big\rfloor$$

Finally, any value $k \in B$ that lies in a column $j$ is of the form $\frac{j(j - 1)}{2} + i$, then, the index $i$ (the line) is given by

$$i(k) = k - \frac{j(k)(j(k) - 1)}{2}$$

and the injection from $B$ to $A$ is

$$f(k) = (i(k), j(k))$$