The following is from a paper by Joel Spencer, called Enumerating Graphs and Brownian Motion.
Let us look at a tree $T$ on vertex set $\{1, \ldots, n\}$ from a computer science perspective. We'll take $n=7$ and the tree with edges 13,15,16,27,34,37 as an example throughout. Start with vertex 1 and find the tree through a breadth-first search (BFS), all lists being in numerical order. To do this we have a queue $Q$, that is initially (1). At each stage we take the vertex $x$ at the head of the queue, remove $x$ from the queue, and add all "new" neighbors of $x$ to the queue. We'll call that operation "processing $x$ " and say that $x$ finds $y$ if $y$ is a new vertex adjacent to $x$. In our example, 1 finds $3,5,6,$ then 3 finds $4,7,$ then 5 finds nothing, 6 finds nothing, 4 finds nothing, 7 finds $2,$ and finally 2 finds nothing. After 2 is processed, the queue becomes empty and the BFS ends.
Let $x_{t}$ be the number of vertices found by the $t^{\text {th }}$ vertex processed (not vertex number $t$ ), which, in our example, is 3,2,0,0,0,1,0 . Let $q_{t}$ be the size of the queue after the $t^{\text {th }}$ vertex is processed. Then $q_{0}=1$ and $q_{t}= q_{t-1}+x_{t}-1$, which, in our example, is $1,3,4,3,2,1,1,0$ . The necessary and sufficient conditions on the sequence $q_{t}$ are $$ q_{n}=0 \quad \text { and } \quad q_{i}>0 \quad \text { for } i<n $$ Now note that there are precisely $(n-1) ! / \prod x_{i} !$ trees with a given sequence $x_{t}$. Indeed, any partition of the vertex set excluding source vertex 1 into sets of sizes $x_{1}, \ldots, x_{n}$ gives a unique such tree $T$.
Can someone explain to me how we derive the last two sentences? I have tried with an example but can't seem to figure it out.
$(n-1)!/\prod_{i=1}^kx_i!$ where $\sum_{i=1}^k x_i = n - 1$ is also called a multinomial coefficient written $\binom{n-1}{x_1 \ldots x_k}$. It gives the number of ways of distributing $n-1$ objects into $k$ bins with $x_i$ objects in bin $k$. You will find more details on this Wikipedia page.
Hence, given a distribution of $\{2, 3, \ldots n\}$ into subsets (bins) $X_1$, $X_2, \ldots X_k$ of sizes $x_1, x_2, \ldots x_k$, there is a unique tree such that the children of $1$ are the elements of $X_1$, the children of the least element of $X_1$ are the elements of $X_2$ and so on, where if we encounter an empty $X_i$, we backtrack to the most recent $X_j$ that we have considered that contains an element whose children we haven't investigated.