Canonical codings of \(\mathbb{N}{}^ k\) (Q1179119)

The author defines the functions \(f_ k:\omega^ k\to\omega\), \[ f_ k(x_ 1,\ldots,x_ k)=\sum^ i_{j=1}B\left(\sum^ i_{j=1}n_ j+(i-1),i\right),\qquad B(n,m)= n!/(m!\cdot(n-m)!). \] It is shown that \(f_ k\) is bijective. A MODULA-2 program for the computation of the inverse functions \(f_ k^{-1}(n)\) is presented and its running time is reported for a few values of \(k\) and \(n\), but there are no results about the complexity of this algorithm.