Counting Positive Rational Numbers

Date: 09/09/2001 at 15:43:35
From: Alfred Lauzon
Subject: Counting the positive rational numbers

In Hardy's book _Pure Mathematics_, on p. 1, he gives a formula for 
counting the positive rational numbers p/q when they are arranged in a 
triangular matrix and counted down diagonally from the top row, 
resulting in the series

 1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4, ... 

Then p/q is the [1/2(p+q-1)(p+q-2)+q]th term of the series.

I can see that the formula does work for the few numbers I've tried, 
but how can it be proved for all such numbers?

Date: 09/10/2001 at 15:22:23
From: Doctor Peterson
Subject: Re: Counting the positive rational numbers

Hi, Alfred!

This is the sort of thing that is "obvious" if you are looking at it 
the right way. If we make a chart of the index in this sequence, we 
have

     \p|
    q \| 1  2  3  4  5
   ----+---------------
    1  | 1  2  4  7 11
    2  | 3  5  8 12
    3  | 6  9 13
    4  |10 14
    5  |15  

and so on. We are making a sequence of diagonal rows, each of which 
ends (at the lower left) with the triangular number T[n], where n is 
the row number (1 for the first row, containing only "1"), and

    T[n] = n(n+1)/2

The fraction p/q is in row number p+q-1; for instance, to get to 3/2 
from 1 we go down two rows and across 1 more, making a total of 3 rows 
away from row 1: (3-1)+(2-1)+1 = 4.

The previous row, row p+q-2, ends with T[p+q-2]; in my example this is 
the 6 at the end of row 3. Now we have to add q to this index to get 
to the entry for p/q in the next row: 6 + 2 = 8 gives us the index for 
3/2. In general, the index for p/q is

    T[p+q-2] + q = (p+q-2)(p+q-1)/2 + q

And that's what Hardy probably saw immediately, and expects us to see, 
too.

(I don't have the book; I assume he does something about the fact that 
this count doesn't take into account equivalent fractions.)

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/