Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 1 more comment

1 Answer 1

up vote 1 down vote accepted

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.