[seqfan] Re: article by Paul Taurau on bijections to naturals

[Antti Karttunen]

On Tue, 23 Feb 2010 10:09:26 +0200,  Georgi Guninski
<guninski at guninski.com> wrote:

> Message: 7
> From: Georgi Guninski <guninski at guninski.com>
> Subject: [seqfan]  article by Paul Taurau on bijections to naturals
> To: seqfan at seqfan.eu
> Message-ID: <20100223080926.GA5435 at sivokote.iziade.m$>
> Content-Type: text/plain; charset=us-ascii
>
> Probably this is well known:
>
> Isomorphic Data Encodings and their
> Generalization to Hylomorphisms on
>   Hereditarily Finite Data Types
>               Paul Tarau

Wow, what a treasure! A few years ago I thought about writing or co-writing
an informal paper like "The OEIS user's guide for encoding various
enumerable combinatorial
structures as natural numbers", or something like that,
and it seems Tarau's paper is on the same tracks.
However, he doesn't link much to OEIS, referring just to the following
three A-numbers: A003188, A006068 (Binary Gray-code and its inverse)
and A060803.

Now, I'm not immediately going to print 158 pages, so maybe I wait
until I have an e-reader which can show A4/letter-size PDF's without
much pain. (Anybody on this list having any experience of reading
mathematical papers with e.g. Kindle DX or Sony PRS-900 Daily Edition?)

Cheers,

Antti


>
> http://logic.csci.unt.edu/tarau/research/2009/fISO.pdf
> Haskell code: http://logic.csci.unt.edu/tarau/research/2009/fISO.zip
>
> 158 pages, many figures and examples.
>
> The author gives bijections N <=>:
> Finite sets
> Finite multisets
> bijective base-k
> Graphs
> ...others
>
> For some types the author gives more than one bijection and this may be source for permutations of the naturals:
> a_n=b_2^-1(b_1(n))
>
>
> Experimentally "casting" the complete graph on n nodes to a(n) in haskell:
>
> *ISO> let cgr n = [(x,y) | x <- [0 .. n - 1],y <- [0..n-1],x<y] --complete graph on n vertices
> *ISO> let gra=[cgr i | i <- [1..6]]
> *ISO> gra
> [[],[(0,1)],[(0,1),(0,2),(1,2)],[(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],[(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],[(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)]]
> *ISO> [as nat graph i | i<-gra] -- graph to N
> [0,4,268,1868,4294975436,30065065932]
>
>
>