# Stirling Numbers of Uniform Trees and Related Computational Experiments
## 3 Exact Computations  
In this section, we describe algorithms for the exact enumeration of Stirling numbers of the first kind on trees. We note that using the loop-erased random walk algorithm of [PERSON] [13], we can generate uniform spanning trees on \(n\) vertices beginning with \(K_{n}\). This allows us to empirically estimate the distribution of Stirling numbers of the first kind for these trees as well as the expected distributions of several common metrics studied on graphs. We use these values to inform our parameter selection and classification of trees below. Additionally, as mentioned in Section 1, trees of a fixed size interpolate between being path-like and star-like with respect to many graph metrics. To sample more efficiently from these extremes, it is possible to implement a weighted version of the cycle basis walk on spanning trees, and the autocorrelation of this model is analyzed in the first section of the Supplementary Information. The Supplementary Information is posted on our corresponding GitHub repository for this paper; for a link to this repository, see our Data Availability Statement. In addition to uniform trees, it is also possible to efficiently sample uniform cycle covers for bipartite, planar graphs, building on the method of [PERSON] and [PERSON] [14; 15] for sampling uniform perfect matchings. This is described in Algorithm 1 below. Next, we observe that while computing the \(k\)-Stirling numbers of the first kind can be computationally intensive, computing the graph factorial, which is the sum of these numbers over \(k\), can be done with a single matrix determinant for planar graphs using the FKT algorithm described in Section 1.2 and Theorem 1.4 in a book by [PERSON] [16]. This algorithm, introduced in a paper by [PERSON] [17], counts the number of perfect matchings in a planar graph by constructing a Pfaffian orientation in polynomial time. This is a simple example of the permanent-determinant method [18]. By modifying the Pfaffian with polynomial entrieswe can compute the number of 2-cycles that appear in the cycle cover as the coefficient of \(x^{k}\). We provide implementations of these algorithms in our corresponding GitHub repository and present examples in the section below motivating conjectures for uniform trees. ```
Input: A planar, bipartite graph \(G=(A,B)\) Output: A uniform cycle cover of \(G\) Select: two uniform perfect matchings \(M_{1}\) and \(M_{2}\) on \(G\) Initialize:\(M=\{\}\) for edge (a,b) in \(M_{1}\)do  Add (a,b) to \(M\) end for edge (a,b) in \(M_{2}\)do  Add (b,a) to \(M\) end Return:\(M\)
```  
**Algorithm 1**Uniform Cycle Cover  
Theorem 4.1: _Algorithm 2 returns the number of \(k-\)matchings of \(T\) across all \(0\leq k\leq|V(T)|\)._  
Proof: The permanent adjacency matrix of a tree \(T\) counts the cycle covers of \(T\). These correspond to matchings since the only possible cycle lengths are 1 and 2. Let \(A(T)\) be the adjacency matrix of \(T\). We note that viewing \(A(T)\) as a biadjacency matrix gives \(T\square P_{2}\), which is planar since \(T\) is outerplanar. Thus, we can apply the FKT algorithm to \(T\square P_{2}\) to obtain a Pfaffian orientation of \(A(T\square P_{2})\). This means that the number of perfect matchings in the product can be computed as the square root of this number, which is exactly the number of cycle covers that we were trying to compute. There is also an algebraic method for computing these values by representing the terms with a symbolic determinant. Theorem 4.2: _The determinant of \(ixA(T)+I_{n}\) returns the number of \(k-\)matchings of \(T\) across all \(0\leq k\leq|V(T)|\) as the coefficient of \(x^{2k}\)._  
Proof: A non-zero term in the determinant of \(ixA(T)+I_{n}\) consists of a set of diagonal elements \(S\) counted with a weight of positive one and a perfect matching of \(T\backslash S\) where each term collects a weight of \(-x\). The product of these terms is then equal to \(x^{2k}\) where \(k\) is the number of edges of \(T\) that occur in the matching.