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

<p>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.</p>

<p>This sequence goes 2, 12, 120, 1680, 30240, and is listed in the Online Encyclopedia of Integer Sequences as <a href="http://oeis.org/A001813" rel="noreferrer">Quadruple Factorial Numbers</a>, with a simpler formula than I give above.</p>

<p>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. </p>

CC BY-SA 3.0
2015-04-21T20:27:46.750Z
2015-04-21T20:47:50.247Z
2015-04-21T20:47:50.247Z
Peter Shor 
<p>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}$.</p>

CC BY-SA 4.0
2018-07-13T22:01:03.103Z
2018-07-13T22:01:03.103Z
Qwert_y
<p>In Huffman coding, if we have two symbols to be encoded, we will get the result either <code>01</code> or <code>10</code>. 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?</p>

CC BY-SA 3.0
2015-04-21T20:41:57.347Z
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.
Peter Shor 
CC BY-SA 3.0
2015-04-22T03:15:26.030Z
@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.
Kaveh
<coding-theory><encoding>
How many different Huffman encoding for a given number of symbols
Yang Xia
# How many different Huffman encoding for a given number of symbols

(Asked by: username_0 on 2015-04-16)

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?

**Tags:** coding-theory, encoding
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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.  

---

## 2 answers

### Answer by username_1 on 2015-04-21. Score: 8 | Accepted answer

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](http://oeis.org/A001813), 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.


---

### Answer by username_3 on 2018-07-13. Score: 2

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}$.


---

