# Stirling Numbers of Uniform Trees and Related Computational Experiments
## 2 Mathematical Preliminaries  
Let \(G\) be a graph on \(n\) vertices. The \(k\)-th Stirling number of the first kind of \(G\), denoted by \([^{G}_{k}]\), is the number of partitions of \(G\) into exactly \(k\) disjoint cycles, where a single vertex is a 1-cycle, an edge is a 2-cycle, and cycles of order three or higher have two orientations. The graphical factorial of \(G\), denoted by \(G!\), is the total number of such decompositions without any restrictions on the number of cycles involved, i.e., \(G!=\sum_{k}\genfrac{[}{]}{0.0 pt}{}{C}{k}\). For results regarding the Stirling numbers of the first kind and graphical factorials for families including paths, cycles, complete bipartite graphs, and fans, among others, see articles by [PERSON] [5] and [PERSON] [6]. These results were initially motivated by a combinatorial model of seating rearrangements presented by [PERSON] [7] and further analyzed by [PERSON] and [PERSON] [8] and [PERSON], [PERSON], and [PERSON] [9]. We showed [1] that for any tree \(T\) on \(n\) vertices and any integer \(n\geq k\geq\lceil\frac{n}{2}\rceil\),  
\[\genfrac{[}{]}{0.0 pt}{}{S_{n}}{k}\leq\genfrac{[}{]}{0.0 pt}{}{T}{k}\leq \genfrac{[}{]}{0.0 pt}{}{P_{n}}{k},\]  
where \(S_{n}\) and \(P_{n}\) are the star and path of order \(n\). Consequently, we have  
\[S_{n}!\leq T!\leq P_{n}!.\]  
We now define global closeness and between centralities. Let \(G\) be a connected graph. For a vertex \(v\), closeness is defined as  
\[\operatorname{cls}_{G}(v)=\frac{n-1}{\sum_{u\in V}d(u,v)},\]  
where \(d(u,v)\) is the distance between \(u\) and \(v\). The global closeness centrality, which is a Freeman centrality measure [10; 11], can be defined as  
\[C_{\operatorname{cls}}(G)=\frac{\sum_{i=1}^{n}(\operatorname{cls}_{G}(v^{*}) -\operatorname{cls}_{G}(v_{i}))}{H},\]  
where \(n=|V(G)|\), \(v^{*}\) is a vertex in \(G\) such that \(\operatorname{cls}(v^{*})=\max_{v\in V}\operatorname{cls}(v)\), and \(H\) is the maximum value the nominator of \(C_{\operatorname{cls}}(G)\) realizes for all connected graphs of order \(n\). For a vertex \(v\) in a graph \(G\), the betweenness centrality is defined as  
\[\operatorname{btw}(v)=\frac{1}{\binom{n-1}{2}}\sum_{u,v\in V-v}\frac{P(u,w;v) }{P(u,w)},\]  
where \(P(u,w)\) is the number of shortest paths from \(u\) to \(w\) and \(P(u,w;v)\) are such paths that go through \(v\). We divide by \(\binom{n-1}{2}\) to normalize this centrality measure. The global betweenness centrality, which is a Freeman centralization [10; 11], is defined as  
\[C_{\operatorname{btw}}(G)=\frac{\sum_{i=1}^{n}(\operatorname{btw}_{G}(v^{*} )-\operatorname{btw}_{G}(v_{i}))}{H},\]  
where \(n=|V(G)|\), \(v^{*}\) is a vertex in \(G\) such that \(\operatorname{btw}_{G}(v^{*})=\max_{v\in V}\operatorname{btw}_{G}(v)\), and \(H\) is the maximum value the nominator of \(C_{\operatorname{btw}}(G)\) realizes for all connected graphs of order \(n\). In the case of \(C_{\operatorname{btw}}(G)\) it does not matter whether we use a normalized or nonnormalized definition for \(C_{\operatorname{btw}}(v)\). We showed [1] that for any tree \(T\) of order \(n\), where \(n\geq 2\),  
\[C_{\operatorname{cls}}(P_{n})\leq C_{\operatorname{cls}}(T)\leq C_{ \operatorname{cls}}(S_{n})\]and  
\[C_{\rm btw}(P_{n})\leq C_{\rm btw}(T)\leq C_{\rm btw}(S_{n}).\]  
For more information on different centrality measures, especially in the context of social networks, see a paper by [PERSON] [12]. We now define distinguishing polynomials for trees. First, we need to define them for rooted unlabeled trees. For a rooted tree \(T_{r}\), where \(r\) is the root, the primary subtree is a subtree \(S\) of \(T_{r}\) such that \(S\) has the same root as \(T_{r}\) and every leaf of \(T_{r}\) is either a leaf of \(S\) or is a descendant of a leaf of \(S\). For a primary subtree \(S\) of \(T_{r}\), we define \(Q(S;x,y)=x^{\alpha}y^{\beta}\), where \(\alpha\) is the number of leaves of \(S\) that are leaves in \(T_{r}\) and \(\beta\) is the number of leaves of \(S\) that are internal vertices in \(T_{r}\).