# how to identify uniquely a couple in a set

today I've been thinking about this problem. I hope somebody can help or give me some hints to find a solution.

Given:

1. the set $x = \{\text{the first n natural number}\}$, $|x| = n$.
2. the set $X = \{\text{all possible couple of element in x}\}$, $|X| = 1+2+3+...+(n-1)$.

Find: two functions $f, g$ such that:

1. for any number $w$ in $\{1, 2, \ldots, |X|\}$, $\{f(w),g(w)\}$ is a couple in $X$
2. there are no two numbers $z,y$ in $\{1, 2, \ldots, |X|\}$ such that: $z \ne y$ and $\{f(z),g(z)\} = \{f(y),g(y)\}$

For example: if $n = 4$, $x = \{1,2,3,4\}$, $X = \{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}\}$, $|X| = 1+2+3 = 6$. I want to find two (linear?) functions so that:

• 1: $\{f(1),g(1)\} = \{1,2\}$
• 2: $\{f(2),g(2)\} = \{1,3\}$
• ...
• 6: $\{f(6),g(6)\} = \{3,4\}$

roughly speaking, the goal is to find a way to identify the couple of the set.

-
It might help if you could say why you are interested in this problem. Where does it come from? – Chris Godsil Jan 29 '13 at 0:41
Welcome to MSE! The site uses MathJax to improve the layout of your questions, which helps those trying to answer your question parse it. I took the liberty to edit it into this question. – gnometorule Jan 29 '13 at 0:44
If I understand correctly, you just want a way to "count" all couples. Am I right? – Tunococ Jan 29 '13 at 0:47
@ChrisGodsil: I'm a computer scientist, I'm writing my thesis and I had to solve this problem in my code. I found a way to code a function that does that using a simple iteration of the couples but I've started wondering if that could have been done in a more elegant way. It is mostly to satisfy my curiosity. – Luka Jan 29 '13 at 8:51
@gnometorule: thank you – Luka Jan 29 '13 at 8:51

It helps to pick an ordering of $X$ and the one you have indicated is a natural one. We have that $|X|=\frac 12 (n-1)n$, the $(n-1)^{\text{st}}$ triangular number, $T_{n-1}$. There are $n-1$ pairs with first entry $1$, then $n-2$ that have first entry $2$, etc. So $$f(k)=\begin {cases} 1 & 1 \le k \le n-1 \\ 2 & n \le k \le 2n-3 \\ 3 & 2n-2 \le k \le 3n-6 \\ \ldots \end {cases}$$ or, more compactly, $f(k)$ is the $j$ such that $(j-1)n-T_{j-1}+1 \le k \le jn-T_j$. You can use the expression of $T_j$ in terms of $j$ to yield an expression that solves a quadratic equation and takes the integer part to find $j$.
$g$ is harder to express, but has much the same feel. Let us define $p=|X|-k+1$, so $p$ counts in reverse from $1$ to $T_{n-1}$. Note that $g(p)$ goes $n,n,n-1,n,n-1,n-2,n,n-1,n-2,n-3,\ldots 2$. The "tier" $j$ that $g(p)$ is in is the $j$ such that $T_{j-1} +1\le p \le T_j$ and $g(p)=n-(p-T_{j-1})+1$