Bell Numbers and Stirling Numbers of the Mycielskian of Trees

2025/12/07 by Allagan, J., Morgan, G., Sinclair, D.
Mathematics · #Advanced Combinatorial Mathematics #Markov Chains and Monte Carlo Methods #Graph theory and applications

paper · doi:10.48550/arxiv.2512.06980

Abstract

We establish explicit formulas for Bell numbers and graphical Stirling numbers of complete multipartite graphs, complete bipartite graphs with removed perfect matchings, and Mycielskian trees. For complete multipartite graphs K(n₁,…,n_ℓ), we provide a simplified proof that B(G) = ∏_i=1^ℓ \belln_i. We derive B(K_n,n - M) = ∑_k=0ⁿ \binomnk \bellk² for removed perfect matching M, and for Mycielskian star graphs, B(M(St_n); 3) = 2ⁿ + 1 and B(M(St_n); 2n) = 2n² - 3n + 3. Results extend to Mycielskians of arbitrary trees. Our computational verifications establish links between graphical Bell numbers and fundamental sequences in combinatorics and pattern avoidance, including identification of several OEIS entries: A000051, A096376, A116735, A384980, A384981, A384988, A385432, and A385437.

Citations

• MXNet: A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systems
• Caffe: Convolutional Architecture for Fast Feature Embedding
• Stirling numbers of forests and cycles

Related

• Cyclic and Linear Graph Partitions and Normal Ordering
• Combinatorially interpreting generalized Stirling numbers
• Restricted r-Stirling Numbers and their Combinatorial Applications
• Partial Deranged Bell Numbers and Their Combinatorial Properties
• Refinements of the Bell and Stirling numbers