Skip to main content
added 162 characters in body
Source Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

I believe this is the proof Postnikov suggested at CCCC LXI. Let us say that $K_n$ has vertices $1,2,\ldots,n$. Imagine a spanning tree of $K_n$ as being rooted at $1$. To any spanning tree $T$, we associate $T'$, the part of the tree at or below the vertex $2$ in this tree, and $T''$, the other part of the tree (which at least contains the root vertex $1$). Say $|T'| = k$ with $1 \leq k \leq n-1$. Then there are $\binom{n-2}{k-1}$ possible sets of labels for $T'$, $t_k$ possible trees for $T'$ given such labels, $t_{n-k}$ trees for $T''$ (whose set of labels is now determined), and $n-k$ places to "stick" $T'$ into $T''$ (which amounts to a choice of which vertex in $T''$ the vertex $2$ is a child of). This proves $$t_n = \sum_{k=1}^{n-1} (n-k) \binom{n-2}{k-1} t_k t_{n-k}.$$

Your equation then follows by grouping the term $k$ with the term $n-k$ in that sum, and then redistributing.

I believe this is the proof Postnikov suggested at CCCC LXI. Let us say that $K_n$ has vertices $1,2,\ldots,n$. Imagine a spanning tree of $K_n$ as being rooted at $1$. To any spanning tree $T$, we associate $T'$, the part of the tree at or below the vertex $2$ in this tree, and $T''$, the other part of the tree. Say $|T'| = k$. Then there are $\binom{n-2}{k-1}$ sets of labels for $T'$, $t_k$ possible trees for $T'$ given such labels, $t_{n-k}$ trees for $T''$ (whose set of labels is now determined), and $n-k$ places to "stick" $T'$ into $T''$. This proves $$t_n = \sum_{k=1}^{n-1} (n-k) \binom{n-2}{k-1} t_k t_{n-k}.$$

Your equation then follows by grouping the term $k$ with the term $n-k$ in that sum, and then redistributing.

I believe this is the proof Postnikov suggested at CCCC LXI. Let us say that $K_n$ has vertices $1,2,\ldots,n$. Imagine a spanning tree of $K_n$ as being rooted at $1$. To any spanning tree $T$, we associate $T'$, the part of the tree at or below the vertex $2$ in this tree, and $T''$, the other part of the tree (which at least contains the root vertex $1$). Say $|T'| = k$ with $1 \leq k \leq n-1$. Then there are $\binom{n-2}{k-1}$ possible sets of labels for $T'$, $t_k$ possible trees for $T'$ given such labels, $t_{n-k}$ trees for $T''$ (whose set of labels is now determined), and $n-k$ places to "stick" $T'$ into $T''$ (which amounts to a choice of which vertex in $T''$ the vertex $2$ is a child of). This proves $$t_n = \sum_{k=1}^{n-1} (n-k) \binom{n-2}{k-1} t_k t_{n-k}.$$

Your equation then follows by grouping the term $k$ with the term $n-k$ in that sum, and then redistributing.

Source Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

I believe this is the proof Postnikov suggested at CCCC LXI. Let us say that $K_n$ has vertices $1,2,\ldots,n$. Imagine a spanning tree of $K_n$ as being rooted at $1$. To any spanning tree $T$, we associate $T'$, the part of the tree at or below the vertex $2$ in this tree, and $T''$, the other part of the tree. Say $|T'| = k$. Then there are $\binom{n-2}{k-1}$ sets of labels for $T'$, $t_k$ possible trees for $T'$ given such labels, $t_{n-k}$ trees for $T''$ (whose set of labels is now determined), and $n-k$ places to "stick" $T'$ into $T''$. This proves $$t_n = \sum_{k=1}^{n-1} (n-k) \binom{n-2}{k-1} t_k t_{n-k}.$$

Your equation then follows by grouping the term $k$ with the term $n-k$ in that sum, and then redistributing.