[seqfan] article by Paul Taurau on bijections to naturals

Georgi Guninski guninski at guninski.com
Tue Feb 23 09:09:26 CET 2010


Probably this is well known:

Isomorphic Data Encodings and their
Generalization to Hylomorphisms on
   Hereditarily Finite Data Types
               Paul Tarau

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]





More information about the SeqFan mailing list