Skip to main content

All Questions

Filter by
Sorted by
Tagged with
14 votes
1 answer
647 views

Bijective proof of recurrence for rooted unlabeled trees

Would've been a better question for Christmas than Thanksgiving, but alas... Let $t_n$ denote the number of rooted, unlabeled trees on $n$ vertices (OEIS A000081). These are the isomorphism classes of ...
Sam Hopkins's user avatar
  • 24.2k
8 votes
1 answer
344 views

Bijective proof of formula for rooted binary forests

For $n\ge 1$, let $f(n)$ be the number of rooted complete (unordered) binary trees with $n$ leaves labeled from $1$ to $n$ ("complete binary" means that every vertex has either $0$ or $2$ children and ...
Timothy Chow's user avatar
  • 82.7k
5 votes
1 answer
413 views

Bijectively counting labeled trees by number of leaves

A rooted, labeled tree on $n$ vertices is a tree with vertex set $[n] := \{1,2,\ldots,n\}$ in which one vertex has been designated the root. A leaf of a rooted tree is a vertex $v$ for which either: $...
Sam Hopkins's user avatar
  • 24.2k