Dtyjlui

If you ignore its root, a Binary Search Tree generated by some permutation of ${1, ldots, n}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found that there are A000245 distinct Prufer sequences.

import itertools



def generate_tree(l):

    '''Return the root and a set of edges'''

    if len(l) == 0:

        return None, None

    if len(l) == 1:

        return l[0], set()

    left_root, left_edges = generate_tree([x for x in l if x < l[0]])

    right_root, right_edges = generate_tree([x for x in l if x > l[0]])

    edges = set()

    if left_root is not None:

        edges.add((left_root, l[0]))

        edges.update(left_edges)

    if right_root is not None:

        edges.add((l[0], right_root))

        edges.update(right_edges)

    return l[0], edges



def pruffer_sequence(edge_set):

    degrees = {}

    for v1, v2 in edge_set:

        degrees[v1] = degrees.get(v1, 0) + 1

        degrees[v2] = degrees.get(v2, 0) + 1

    r = 

    while len(edge_set) > 1:

        smallest_leaf = min([v for v in degrees.keys() if degrees[v] == 1])

        degrees[smallest_leaf] -= 1

        for e in edge_set:

            if smallest_leaf in e:

                edge_set = edge_set - {e}

                neighbor = [v for v in e if v != smallest_leaf][0]

                degrees[neighbor] -= 1

                r.append(neighbor)

                break

    return r



for number_of_vertices in range(2, 10):

    R = set()

    for l in itertools.permutations(range(number_of_vertices)):

        root, edge_set = generate_tree(l)

        R.add( tuple( pruffer_sequence(edge_set) ))

    print number_of_vertices, len(R)

Is there some way to characterize a BST by its Prufer sequence without first calculating its tree?

Is there a reason you chose to take the BST of the permutations? There are multiple ways to uniquely represent a permutation as a tree, where you would end up with $n!$ different Prufer sequences. Categorizing such sequences might be more interesting.

But in any case, I couldn't find a way to enumerate without iterating all the $n!$ permutations. I tried to find a bijection between Prufer sequences and something counted by the difference of Catalan numbers $C_n-C_{n-1}$, but to no avail. I was however, able to speed up your code.

Given two permutations $p_1, p_2 in S_n$

$$ text{Prufer}(p_1) ;;;= ;;; text{Prufer}(p_2) \
Longleftrightarrow \
text{Tree}(p_1) ;;; = ;;; text{Tree}(p_2) \
Longleftrightarrow \
text{Edges}(text{BST}(p_1)) ;;; = ;;; text{Edges}(text{BST}(p_2)) \
$$
So you only need to find the Prufer sequence when you come across a new edge set. Also, if you actually construct the BST, you can find the Prufer sequence in linear time. Here is my python code (takes 6 seconds rather than 18).