today I've been thinking about this problem. I hope somebody can help or give me some hints to find a solution.
Given:
- the set $x = \{\text{the first n natural number}\}$, $|x| = n$.
- the set $X = \{\text{all possible couple of element in x}\}$, $|X| = 1+2+3+...+(n-1)$.
Find: two functions $f, g$ such that:
- for any number $w$ in $\{1, 2, \ldots, |X|\}$, $\{f(w),g(w)\}$ is a couple in $X$
- 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 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$