On the proportion of prefix codes in the set of three-element codes

Abstract

Let $L$ be a finite sequence of natural numbers. In Woryna (2017,2018), we derived some interesting properties for the ratio ${\rho }_{n,L}=|P{R}_n(L)|/|U{D}_n(L)|$, where $U{D}_n(L)$ denotes the set of all codes over an $n$-letter alphabet and with length distribution $L$, and $P{R}_n(L)\subseteq U{D}_n(L)$ is the corresponding subset of prefix codes. In the present paper, we study the case when the length distributions are three-element sequences. We show in this case that the ratio ${\rho }_{n,L}$ is always greater than ${\alpha }_n$, where ${\alpha }_n=(n-2)/n$ for $n>2$ and ${\alpha }_2=1/6$. Moreover, the number ${\alpha }_n$ is the best possible lower bound for this ratio, as the length distributions of the form $L=(1,1,c)$ and $L=(1,2,c)$ assure that the ratios asymptotically approach ${\alpha }_n$. Namely, if $L=(1,1,c)$, then ${\rho }_{n,L}$ tends to $(n-2)/n$ with $c\to \infty$, and, if $L=(1,2,c)$, then ${\rho }_{2,L}$ tends to $1/6$ with $c\to \infty$.

References in corpus (1)

• On the set of uniquely decodable codes with a given sequence of code word lengths