# Stirling Numbers of Uniform Trees and Related Computational Experiments
## 3 Exact Computations
Figure 1: Full distribution of the \(k\) Stirling numbers of the first kind across all isomorphism classes of trees on 12 vertices. We focus on isomorphism classes since our intended application is to classify up to isomorphism. ## 4 Probabilistic Approach

Our next approach for computing Stirling numbers of the first kind is probabilistic, applying techniques from matrix algebra. Let \(F\) be a forest and let \(V\) and \(E\) be its vertex and edge set, respectively, with \(c\) connected components. Let us assume that \(|V|=n\); hence, \(|E|=n-c\). Suppose \(\mathcal{P}_{k}\) is a partition of \(F\) into \(k\) cycles. For \(v\in V\), denote the set of incident edges with \(v\) by \(I(v)\). For every \(e_{i}\in E\), where \(i\in\{1,\ldots,n-1\}\), define \(x_{e_{i}}\) as follows:

\[x_{e_{i}}= \begin{cases}1,&\text{if $e_{i}$ is a 2-cycle in $\mathcal{P}_{k}$;}\\ 0,&\text{otherwise.}\end{cases} \]

With this definition in mind, \(\genfrac{[}{]}{0.0 pt}{}{F}{k}=|\{(x_{e_{1}},\ldots,x_{e_{n-c}})\mid\text{ some conditions are met}\}|\), where these conditions are as follows:

* For every \(v\in V\), \[\sum_{e_{i}\in I(v)}x_{e_{i}}= \begin{cases}0,&\text{if $v$ is in a 1-cycle;}\\ 1,&\text{if $v$ is in a 2-cycle.}\end{cases} \]
* Subsequently, if \(x_{e_{i}}=1\) for some \(e_{i}=uv\in E\), then \(x_{e_{j}}=0\) for all \(e_{j}\in I(v)\cup I(u)\) and \(j\
eq i\). If we denoted the set of vertices in 1-cycles and 2-cycles by \(A\) and \(B\), respectively, then \(k=|A|+|B|/2\). Please note that \(A=\{v\mid\sum_{e_{i}\in I(v)}x_{e_{i}}=0\}\), \(B=\{v\mid\sum_{e_{i}\in I(v)}x_{e_{i}}=1\}\) and \(|A|+|B|=n\). It follows that \(|A|=2k-n,|B|=2(n-k)\). As a result, \(n\geq k\geq\frac{n}{2}\). Let

**A** be the incidence matrix for a forest \(F\) and **x** the column vector \((x_{e_{1}},\ldots,x_{e_{n-c}})^{T}\), then \(\textbf{b}=\textbf{A}\textbf{x}\) is a \(\{0,1\}\)-column vector with exactly \(|B|=2(n-k)\) many 1's and \(|A|=2k-n\) many 0's. Reversing the previous discussion gives the following result that we can use to develop an approximation algorithm. Lemma 1: _For any \(\{0,1\}\)-column vector \(\mathbf{b}\) with \(2(n-k)\) many 1's and \(2k-n\) many 0's, the probability that the linear equation \(\textbf{A}\textbf{x}=\textbf{b}\) has a \(\{0,1\}\)-solution is:_

\[\frac{\genfrac{[}{]}{0.0 pt}{}{F}{k}}{(\frac{n}{2(n-k)})},\]

_where \(F\) is the forest with incidence matrix **A**._

The previous result suggests an algorithm for estimating \(\genfrac{[}{]}{0.0 pt}{}{F}{k}\) by sampling uniformly from the set of binary vectors with exactly \(2(n-k)\) many 1's, and determining whether the solution to \(\textbf{A}\textbf{x}=\textbf{b}\) has binary entries. For \(1\leq j\leq m\), let \(\textbf{b}_{j}\) be a \(\{0,1\}\)-column vector with \(2(n-k)\) many 1's and \(2k-n\) many 0's random entries and let \(\textbf{B}=[\textbf{b}_{j}]\). Solving the equation \(\textbf{A}\textbf{X}=\textbf{B}\), where \(\textbf{X}=[\textbf{x}_{j}]\) is a \((n-c)\times m\) matrix of unknowns column vectors \(\textbf{x}_{j}\). The time complexity of applying Gaussian elimination to the augmented matrix \([\textbf{A}|\textbf{B}]\) is \(O((n-c+m)n^{2})\). Using back-substitution to find a solution \(\textbf{x}_{j}\) for \(\textbf{A}\textbf{x}_{j}=\textbf{b}_{j}\) is \(O(n^{2})\) and checking whether this solution consists of only 0s and 1s require \(O(n)\) operations. With \(m\) random vectors \(\textbf{b}_{j}\), we need \(O(mn^{2})\) operations. Therefore, the overall time complexity of checking which random column vectors \(\textbf{b}_{j}\) yield an allowable solution \(\textbf{x}_{j}\) requires \(O(n^{3}+mn^{2})\) operations, assuming \(c\) is fixed. This naive approach requires fully solving the associated linear system and checking whether the resulting solution vectors are binary. We can circumvent this computational hurdle by instead interpreting the system as a collection of Diophantine equations, motivated by interpreting the product as occurring over the edges of the tree, rather than the vertices.