# Stirling Numbers of Uniform Trees and Related Computational Experiments
## 3 Exact Computations
Note that

\[\sum_{e_{i}\in E}x_{e_{i}}+\sum_{e_{i}\in E}(1-x_{e_{i}})=\sum_{e_{i}\in E}1=n-c.\]

It follows that

\[|B|/2+\sum_{e_{i}\in E}(1-x_{e_{i}})=n-c\]

and

\[n-k+\sum_{e_{i}\in E}(1-x_{e_{i}})=n-c.\]

Now define \(y_{e_{i}}\) as \(1-x_{e_{i}}\) for every \(e_{i}\in E\). It follows that

\[\sum_{e_{i}\in E}y_{e_{i}}=k-c.\]

Additionally, the restrictions on \(x_{e_{i}}\)'s translate to the following restrictions for \(y_{e_{i}}\):

* If \(\sum_{e_{i}\in I(v)}x_{e_{i}}=0\) for some \(v\in V\), then \(\sum_{e_{i}\in I(v)}y_{e_{i}}=\sum_{e_{i}\in I(v)}(1-x_{e_{i}})=d(v)\). * If \(\sum_{e_{i}\in I(v)}x_{e_{i}}=1\) for some \(v\in V\), then \(\sum_{e_{i}\in I(v)}y_{e_{i}}=\sum_{e_{i}\in I(v)}(1-x_{e_{i}})=d(v)-1\). It follows that \(A=\{v\mid\sum_{e_{i}\in I(v)}y_{e_{i}}=d(v)\}\) and \(B=\{v\mid\sum_{e_{i}\in I(v)}y_{e_{i}}=d(v)-1\}\), and \[ \begin{bmatrix}F\\ k\end{bmatrix} =|\{(y_{e_{1}},\ldots,y_{e_{n-c}})\mid|A|=2k-n,|B|=2(n-k)\}|.\] (1)

In general, without any restrictions, the number of \(\{0,1\}\)-solutions to the Diophantine equation

\[y_{e_{1}}+\cdots+y_{e_{n-c}}=k-c\]

is \((^{n-c}_{k-c})\). This implies the following result that allows for a more efficient randomized method. Lemma 2: _Let \(Y=(y_{e_{1}},\ldots,y_{e_{n-1}})\) be a binary vector indexed by the edges of \(F\). Then the probability that the positive entries of \(Y\) induce a partition of \(F\) into \(k\) cycles and hence correspond to edges that are not 2-cycles in \(\mathcal{P}_{k}\) is_

\[\frac{[\![F]\!]}{(^{n-c}_{k-c})}.\]

As with the previous approximation result, Lemma 2 suggests an algorithm for estimating \([\![F]\! ]\) by sampling uniformly from the set of binary vectors indexed by the edges of \(F\), and determining whether they induced a partition with the proper number of cycles. If \(\mathbf{1}\) is the column vector whose entries are \(1\)'s and \(\mathbf{A}\) is the incidence matrix of \(F\), then \(\mathbf{d}=\mathbf{A}\mathbf{1}\) is column vector containing the degree sequence of \(F\). On the other hand, if \(\mathbf{y}=(y_{e_{i}},\ldots,y_{e_{n-c}})^{T}\) satisfies the conditions in (1), then \(\mathbf{d}-\mathbf{A}\mathbf{y}=\mathbf{A}(\mathbf{1}-\mathbf{y})\) should consist of \(2(n-k)\) many \(1\)'s. If we have \(m\) many \(\{0,1\}\)-column vectors \(\mathbf{y}_{j}\) with random entries consisting of \(k-c\) many \(1\)'s, then the time complexity to check whether each one satisfies the conditions in (1) is \(O(n(n-c))\) and the overall time complexity is \(O(mn(n-c))\), which may be more efficient than our earlier approach. For an implementation of this approach in _Python_, on our GitHub repository, see the _Jupyter_ notebook TreeLearning-Testing_Probabilistic_Approach.ipynb. In this notebook, a random tree \(T\) is generated, so the number of components \(c\) is one. The code generates \(m\) trials. At each trial, a \(\{0,1\}\)-column vector with random entries is generated and a trial is considered a \"success\" if the condition that it contains exactly \(k-1\) many \(1\)'s is met. We use a Bernoulli random variable to represent the outcome of each trial. In other words, we denote the random variable representing the \(i\)th trial by

\[X_{i}= \begin{cases}1&\text{with probability $p$;}\\ 0&\text{with probability $1-p$,}\end{cases} \]where \(p\) is the probability of \"success\". The main objective is to estimate \([^{T}_{k}]\) via simulation. Let \(X=\sum_{i}X_{i}/m\). Since \(p=\mathbb{E}[X]\approx[^{T}_{k}]/(^{n-1}_{k-1})\), we calculate

\[ \begin{bmatrix}T\\ k\end{bmatrix} - \begin{pmatrix}n-1\\ k-1\end{pmatrix} X\]

in the code to see how well this probabilistic approach performs. #### Results

To make our code reproducible, we are using a random seed. The results for \(n\) between 7 and 15 and \(m=10\),000 is included in Table 1. For each \(n\), a random tree \(T\) of that order is generated and \([^{T}_{k}]\) is estimated for \(n-2\geq k\geq\lceil\frac{n}{2}\rceil\). One natural question is how the probabilistic approach performs compared to the exact computation of \([^{T}_{k}]\).