Any permutation $P_n$ (we are talking about small $n$, since I have to generate all $n!$ ones for my work - tree costs - anyway) can be uniquely turned into a binary tree $T_n$ by starting with an empty tree and inserting the nodes in the order given by $P_n$. (That's called a canonical tree.) Of course, since there are $Catalan$ trees, numerous $P_n$ map to the same $T_n$, an example being $2134,2314,2341$. I now like to compute an unique number for any $T_n$ directly by using $P_n$ as input. Ideally, $1234\rightarrow 1,1243\rightarrow 2,\dots,2134+2314+2341\rightarrow 6$ etc., but a hash value would suffice. The problem of course is not hashing but forcing hash collisions such that two $P_n$ with same $T_n$ hash to the same value. I could generate the $T_n$ one by one and compare if they are identical to an earlier one but with already $O(n!)$ runtime I don't want an additional $n^2$ factor and take any shortcut I can get.
Any suggestions? I have a vague idea (take $2314$; the $3$ is before $1$, both are after $2$, you may swap $3,1$ without affecting $T_n$) but am no profi mathematician.