You are here
Homenumeration system
Primary tabs
numeration system
A numeration system is a triple $N=(b,\Sigma,d)$, where $b>1$ is a positive integer, $\Sigma$ is a nonempty alphabet, and $d$ is a onetoone function from $\Sigma$ to the set of nonnegative integers $\mathbb{N}\cup\{0\}$. Order elements of $\Sigma$ so that their values are in increasing order:
$\Sigma=\{a_{1},\ldots,a_{k}\}$, where $d(a_{i})<d(a_{{i+1}})$ for $i=1,\ldots,k1$.
$b$ is called the base of numeration system $N$, and the elements $a_{1},\ldots,a_{k}$ the digits of $N$. Words over $\Sigma$ are called numeral words.
Given a numeral word $u=c_{1}\cdots c_{m}$ with $c_{j}\in\Sigma$, the integer nonnegative $n$ is said to be represented by $u$ if
$n=c_{1}b^{{m1}}+\cdots+c_{j}b^{{mj}}+\cdots+c_{m}.$ 
An integer $n$ is said to be representable in $N$ if there is a numeral word $u$ representing $n$.
Examples.

The most common numeration system is the decimal system:
$D=(10,\{0,1,2,3,4,5,6,7,8,9\},d)$ where $d(i)=i$ is the identity function.

Just as common is the binary digital system: $B=(2,\{0,1\},d)$ where $d$ again is the identity function.

In fact, any digital system is a numeration system $(n,\Sigma,d)$, where $\Sigma=\{a_{0},\ldots,a_{{n1}}\}$ and $d(a_{i})=i$.

Consider the system $B_{1}=(2,\{1\},d)$, where $d(1)=1$. Since any word over $\{1\}$ is just a string of $1$’s, $n$ consecutive strings of $1$ represent $1+2+\cdots+2^{{n1}}=2^{{n1}}$. We conclude that the integers representable by $N$ have the form $2^{n}1$ for any positive integer $n$.

Consider the system
$D_{1}=(10,\{[0],[1],\ldots,[9],[10],[100],[1000],[10000],[10000000],[100000000% 00]\},d)$ where $d([i])=i$. It is easy to see that every integer is representable by $D_{1}$. However, some integers may be represented by more than one numeral words. For example,
$[1000]=[100][0]=[10][0][0]=[1][0][0][0].$ The numeration system $D_{1}$ is used by the Chinese.

Consider the system $N=(3,\{[1],[2],[4]\},d)$ where $d([i])=i$. Then $[2][1][4][1]=2\times 3^{3}+1\times 3^{2}+4\times 3+1=184$. Notice that $0$ can not be represented $N$. Also, note that $[4]=4=1\times 3+1=[1][1]$.
A numeration system $N$ is said to be complete if every nonnegative integer has at least one representation in $N$; and unambiguous if every nonnegative integer has at most one representation in $N$. $N$ is ambiguous if $N$ is not unambiguous. Every digital system is complete and unambiguous. In the examples above, $D_{1}$ is complete but ambiguous; $B_{1}$ is unambiguous but not complete; $N$ is neither complete nor unambiguous.
Remark. Representation nonnegative integers by a numeration system can be extended to rational numbers. The corresponding concepts of completeness and ambiguity may be defined similarly.
References
 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
Mathematics Subject Classification
11A67 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections