<p><a href="https://memoria-framework.dev/docs/data-zoo/louds-tree/" rel="nofollow noreferrer">LOUDS encoding</a> is widely cited as succinct, e.g., in <a href="https://www.cs.le.ac.uk/people/ond1/XMLcomp/confersWEA06_LOUDS.pdf" rel="nofollow noreferrer">the papers</a>, in <a href="https://github.com/topics/succinct-data-structure" rel="nofollow noreferrer">Github repos</a>, etc.</p>
<p>It is straightforward that LOUDS takes <code>2n</code> bits for encoding an ordered tree with <code>n</code> vertices.
But I found few formula counts trees like <span class="math-container">$4^n$</span> .
For example, <a href="https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Combinatorics_(Keller_and_Trotter)/05%3A_Graph_Theory/5.06%3A_Counting_Labeled_Trees" rel="nofollow noreferrer">Cayley's Formula</a> counts <span class="math-container">$n^{n-2}$</span> labeled trees with <code>n</code> nodes, which is obviously not the correct counting formula.</p>
<p>Then it comes to my question: why is it considered as succinct?
Or which counting formula does it correspond to?</p>

CC BY-SA 4.0
2024-06-12T11:17:34.887Z
The number of ordered trees on $n$ vertices is $C_{n-1}$. See e.g. https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics .
Emil Jeřábek
CC BY-SA 4.0
2024-06-12T11:26:48.757Z
@EmilJeřábek Oh thank you again!  Now I know that what puzzled me is the difference between `labeled` and `ordered`, I found these words are really misused sometimes. Once it is spotted out, the question solved.
Xavier Z
<co.combinatorics><ds.data-structures><it.information-theory><tree><encoding>
Why LOUDS is considered succinct coding?
Xavier Z
# Why LOUDS is considered succinct coding?

(Asked by: username_0 on 2024-06-12)

[LOUDS encoding](https://memoria-framework.dev/docs/data-zoo/louds-tree/) is widely cited as succinct, e.g., in [the papers](https://www.cs.le.ac.uk/people/ond1/XMLcomp/confersWEA06_LOUDS.pdf), in [Github repos](https://github.com/topics/succinct-data-structure), etc.

It is straightforward that LOUDS takes `2n` bits for encoding an ordered tree with `n` vertices.
But I found few formula counts trees like $4^n$ .
For example, [Cayley's Formula](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Combinatorics_(Keller_and_Trotter)/05%3A_Graph_Theory/5.06%3A_Counting_Labeled_Trees) counts $n^{n-2}$ labeled trees with `n` nodes, which is obviously not the correct counting formula.

Then it comes to my question: why is it considered as succinct?
Or which counting formula does it correspond to?

**Tags:** co.combinatorics, ds.data-structures, it.information-theory, tree, encoding
> **Comments:**
> **username_1**: The number of ordered trees on $n$ vertices is $C_{n-1}$. See e.g. https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics .  
> **username_0**: @EmilJeřábek Oh thank you again!  Now I know that what puzzled me is the difference between `labeled` and `ordered`, I found these words are really misused sometimes. Once it is spotted out, the question solved.  

---

## 0 answers

