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_1,\ldots,n_\ell)$, we provide a simplified proof that $B(G) = \prod_{i=1}^\ell \bell{n_i}$. We derive $B(K_{n,n} - M) = \sum_{k=0}^{n} \binom{n}{k} \bell{k}^2$ for removed perfect matching $M$, and for Mycielskian star graphs, $B(M(St_n); 3) = 2^n + 1$ and $B(M(St_n); 2n) = 2n^2 - 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.
翻译：我们建立了完全多部图、移除完美匹配的完全二部图以及米歇尔斯基树的贝尔数和图斯特林数的显式公式。对于完全多部图 $K(n_1,\ldots,n_\ell)$，我们给出了 $B(G) = \prod_{i=1}^\ell \bell{n_i}$ 的简化证明。对于移除完美匹配 $M$ 的完全二部图，我们推导出 $B(K_{n,n} - M) = \sum_{k=0}^{n} \binom{n}{k} \bell{k}^2$；对于米歇尔斯基星图，得到 $B(M(St_n); 3) = 2^n + 1$ 和 $B(M(St_n); 2n) = 2n^2 - 3n + 3$。结果可推广至任意树的米歇尔斯基图。我们的计算验证建立了图贝尔数与组合数学及模式规避中基本序列的联系，包括识别了多个OEIS条目：A000051、A096376、A116735、A384980、A384981、A384988、A385432 和 A385437。
相关内容
微信扫码咨询专知VIP会员