2
$\begingroup$

In Huffman coding, if we have two symbols to be encoded, we will get the result either 01 or 10. If we have three symbols, we will get 12 different encoding. I am wondering if I give a arbitrary number of symbol, is there a formula to calculate how many different encoding we will have by Huffman coding?

$\endgroup$
  • 1
    $\begingroup$ Why on earth are people downvoting and closevoting this as "not a research question"? I am willing to bet none of you figured out an answer (I give one below), and decided that it was too easy to be a research question. If you had closevoted this as "not enough effort on the part of the OP", I might have supported that; the question should at least have explained the 12 different encodings for three symbols, and given the number for four symbols. $\endgroup$ – Peter Shor Apr 21 '15 at 20:41
  • 2
    $\begingroup$ @PeterShor, I voted to close because it is not research-level. I figured it out under a min and decided that this is at the level of a simple undergrad assignment. Please be more respectful when disagreeing with close votes. $\endgroup$ – Kaveh Apr 22 '15 at 3:15
6
$\begingroup$

The answer is $C_{n-1} n!$ . That is, the $(n-1)$st Catalan number times $n$ factorial.

There are $C_{n-1}$ ways of making a complete binary tree with $n$ leaves, and there are $n!$ ways of assigning these leaves to the symbols to get a Huffman code.

This sequence goes 2, 12, 120, 1680, 30240, and is listed in the Online Encyclopedia of Integer Sequences as Quadruple Factorial Numbers, with a simpler formula than I give above.

The above argument shows that the quadruple factorial numbers give the number of ways of assigning $n$ symbols to codewords in a complete binary prefix code. It's not hard to show that you can assign probabilities to the symbols to make this encoding optimal (so it satisfies the definition of a Huffman code). It's not clear that a given Huffman coding algorithm will generate all of these, however.

$\endgroup$
1
$\begingroup$

The answer by Peter Shor is correct. But for an optimal case when the symbols can only be placed at unique leaf nodes the number of possible Huffman codes drops to $C_{n-1}2^{n-1}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.