# Find number of codes using Kraft inequality

Let $$A$$ be the alphabet of the codes, with $$|A| = D$$, and codelengths $$1 \leq l_1 \leq ... \leq l_n$$. Those codelengths satisfy the inequality of Kraft:

$$\sum_{i=1}^n D^{-l_i} \leq 1$$

On how many ways can we choose codewords $$c(w_i) \in A^*$$ so that $$c(w_i)$$ had length $$l_i$$, and that the code is a prefix code? ($$A^*$$ is the concatenation of ''characters'' in the alphabet, and $$w_i$$ is just a word)

I don't exactly know where to start. It is not very difficult to show that a code is a prefix code. But how can I find the number of ways we can choose that codewords $$c(w_i)$$? I hope somebody can help me with that.

• Do you mean $D_i^{-L_i}$? As written your inequality is almost always false. – Samuel Bodansky Sep 11 at 9:56
• Yes, you are right. Thank you for mentioning – Pieter Sep 11 at 10:01

There are $$D^{l_1}$$ ways of picking $$c(w_1)$$, now fixing it, there are $$D^{l_2}-D^{l_2-l_1}$$ ways of picking $$c(w_2)$$. Going further, if we fix $$c(w_1)$$ to $$c(w_{k-1})$$, then we have $$D^{l_{k}}-\sum_{i=1}^{k-1} D^{l_k-l_i}$$ ways of choosing $$c(w_k)$$. The numbers of way to choose the whole code is the product of that and I cannot find a way of simplifying it.
• This looks correct, but it when $l_i=l_{i+1}$ it counts as different codes that differ merely in permutation of codes $c_i$ $c_{i+1}$. You might want that or not, it's not clear. – leonbloy Sep 11 at 18:37