赋权二叉树：修订间差异

←上一编辑下一编辑→

可视化wikitext

2026年2月21日 (六) 17:05的版本

赋权二叉树（Weighted Binary Tree）是FataliS1024提出的大数函数。

定义

对于有根二叉树，令其每条边都有一个正整数权值，即得到赋权二叉树，记作wb

对于两个wb A和B，如果A能通过以下操作得到B，就称B嵌入A，A容纳B，A大于B，B小于A：

删掉一个度为1的顶点和它连接的边
删掉一个度为2的非根顶点和它连接的两条边，并将它原本连接的两个顶点连起来，权值等于min(原来两条边的权值)
将任意一个大于1的权值-1

符合以下条件的最长的有序wb列的长度记作wbtree(n)：

第k个wb最多有k+1个顶点
所有wb的边权值不超过n
前面的wb不小于后面的wb

分析

用()表示权值1的边与它的子节点（远离根的一端）。用[]表示权值2。{}表示权值3.根节点不写

以下提供了wbtree中的一个序型分析

单根=0
$() = 1$
$(()) = 2$
$() () = ω$

上述这些都跟ε(0)以下的tree相同

$\begin{aligned} . \\ [] = ε_{0} \\ ([]) = ε_{0} + 1 \\ (([])) = ε_{0} + 2 \\ ([]) () = ε_{0} + ω \\ ([]) ([]) = ε_{0} \times 2 \\ (([])) ([]) = ε_{0} \times 3 \\ (([]) ()) ([]) = ε_{0} \times ω \\ (([]) ([])) ([]) = ε_{0}^{2} \\ (([])) (([])) = ε_{0}^{ω} \\ (([]) ([])) (([]) ([])) = ε_{0}^{ε}_{0} \\ [] () = ε_{1} \\ [] (()) = ε_{2} \\ [] (() ()) = ε_{ω} \\ [] ([]) = ε_{ε_{0}} \\ [] ([] ([])) = ε_{ε_{ε_{0}}} \\ [()] = ζ_{0} \\ ([()]) = ζ_{0} + 1 \\ ([()]) ([()]) = ζ_{0} \times 2 \\ [] ([()]) = ε_{ζ_{0} + 1} \\ [] (([()])) = ε_{ζ_{0} + 2} \\ [] ([] ([()])) = ε_{ε_{ζ_{0} + 1}} \\ [()] () = ζ_{1} \\ [()] ([()]) = ζ_{ζ_{0}} \\ [(())] = ϑ (Ω \times 3) = φ (3, 0) \\ [] ([(())]) = ϑ (Ω + ϑ (Ω \times 3)) \\ [()] ([(())]) = ϑ (Ω \times 2 + ϑ (Ω \times 3)) \\ [(())] () = ϑ (Ω \times 3 + 1) \\ [((()))] = ϑ (Ω \times 4) \\ [() ()] = ϑ (Ω \times ω) \\ [(() ())] = ϑ (Ω \times (ω + 1)) \\ [(() ()) (() ())] = ϑ (Ω \times ω^{ω^{ω}}) \\ [([])] = ϑ (Ω \times ϑ (Ω)) \\ [([])] () = ϑ (Ω \times ϑ (Ω) + 1) \\ [(([]))] = ϑ (Ω \times (ϑ (Ω) + 1)) \\ [([]) ([])] = ϑ (Ω \times ϑ (Ω) \times 2) \\ [([] ())] = ϑ (Ω \times ϑ (Ω + 1)) \\ [([()])] = ϑ (Ω \times ϑ (Ω \times 2)) \\ [([([])])] = ϑ (Ω \times ϑ (Ω \times ϑ (Ω))) \\ [[]] = ϑ (Ω^{2}) = Γ_{0} \\ [] ([[]]) = ϑ (Ω + ϑ (Ω^{2})) \\ [()] ([[]]) = ϑ (Ω \times 2 + ϑ (Ω^{2})) \\ [([[]])] = ϑ (Ω \times ϑ (Ω^{2})) \\ [([([[]])])] = ϑ (Ω \times ϑ (Ω \times ϑ (Ω^{2}))) \\ [[]] () = ϑ (Ω^{2} + 1) \\ [[]] ([[]]) = ϑ (Ω^{2} + ϑ (Ω^{2})) \\ [[] ()] = ϑ (Ω^{2} + Ω) \\ [[] ([[]])] = ϑ (Ω^{2} + Ω \times ϑ (Ω^{2})) \\ [[()]] = ϑ (Ω^{2} \times 2) \\ [[([[]])]] = ϑ (Ω^{2} \times ϑ (Ω^{2})) \\ [[[]]] = ϑ (Ω^{3}) \\ [[[]]] () = ϑ (Ω^{3} + 1) \\ [[[]] ()] = ϑ (Ω^{3} + Ω) \\ [[[] ()]] = ϑ (Ω^{3} + Ω^{2}) \\ [[[()]]] = ϑ (Ω^{3} \times 2) \\ [[[[]]]] = ϑ (Ω^{4}) \\ [] [] = ϑ (Ω^{ω}) \\ ([] []) = ϑ (Ω^{ω}) + 1 \\ [] ([] []) = ϑ (Ω + ϑ (Ω^{ω})) \\ [([] [])] = ϑ (Ω \times ϑ (Ω^{ω})) \\ [[([] [])]] = ϑ (Ω^{2} \times ϑ (Ω^{ω})) \\ [[] []] = ϑ (Ω^{ω} + 1) \\ [[] []] () = ϑ (Ω^{ω} + 2) \\ [[] []] ([] []) = ϑ (Ω^{ω} + ϑ (Ω^{ω})) \\ [[[] []]] = ϑ (Ω^{ω} + Ω) \\ [[[] []]] () = ϑ (Ω^{ω} + Ω + 1) \\ [[[] []] ()] = ϑ (Ω^{ω} + Ω \times 2) \\ [[[[] []]]] = ϑ (Ω^{ω} + Ω^{2}) \\ [[[[[] []]]]] = ϑ (Ω^{ω} + Ω^{3}) \\ [()] [] = ϑ (Ω^{ω} \times 2) \\ [[()] []] = ϑ (Ω^{ω} \times 2 + 1) \\ [[[()] []]] = ϑ (Ω^{ω} \times 2 + Ω) \\ [[[[()] []]]] = ϑ (Ω^{ω} \times 2 + Ω^{2}) \\ [(())] [] = ϑ (Ω^{ω} \times 3) \\ [([] [])] [] = ϑ (Ω^{ω} \times ϑ (Ω^{ω})) \\ [[]] [] = ϑ (Ω^{ω + 1}) \\ [[[]]] [] = ϑ (Ω^{ω + 2}) \\ [[] []] [] = ϑ (Ω^{ω \times 2}) \\ [[[] []] []] = ϑ (Ω^{ω \times 2} + 1) \\ [[[[] []] []]] = ϑ (Ω^{ω \times 2} + Ω) \\ [[[] []]] [] = ϑ (Ω^{ω \times 2} + Ω^{ω}) \\ [[[] []] ()] [] = ϑ (Ω^{ω \times 2} + Ω^{ω} \times 2) \\ [[[[] []]]] [] = ϑ (Ω^{ω \times 2} + Ω^{ω + 1}) \\ [[()] []] [] = ϑ (Ω^{ω \times 2} \times 2) \\ [[[]] []] [] = ϑ (Ω^{ω \times 2 + 1}) \\ [[[] []] []] [] = ϑ (Ω^{ω \times 3}) \\ [[[[] []] []] []] [] = ϑ (Ω^{ω \times 4}) \\ [()] [()] = ϑ (Ω^{ω^{2}}) \\ [[()] [()]] = ϑ (Ω^{ω^{2}} + 1) \\ [[[()] [()]] []] = ϑ (Ω^{ω^{2}} + Ω^{ω}) \\ [(())] [()] = ϑ (Ω^{ω^{2}} \times 2) \\ [[]] [()] = ϑ (Ω^{ω^{2} + 1}) \\ [[()] [()]] [()] = ϑ (Ω^{ω^{2} \times 2}) \\ [(())] [(())] = ϑ (Ω^{ω^{3}}) \\ [([])] [([])] = ϑ (Ω^{ϑ (Ω)}) \\ [[]] [[]] = ϑ (Ω^{Ω}) = L V O \end{aligned}$

看上去[]可以作为Ω的角色了，这样只使用权重1~2就能达到至少BHO的序型

\begin{align}.\\&\psi(\Omega_2)=\{\}\\&\psi(\Omega_2+\Omega)=[\{\}]\\&\psi(\Omega_2+\Omega^\Omega^\omega)=[\{\}][]\\&\psi(\Omega_2+\psi_1(\Omega_2))=[\{\}][\{\}]\\&\psi(\Omega_2+\psi_1(\Omega_2)+\Omega)=[\{\}][[\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2)\times2)=[\{\}][[\{\}][\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2)\times3)=[\{\}][[\{\}][[\{\}][\{\}]]]\\&\psi(\Omega_2+\psi_1(\Omega_2+1))=[[\{\}]][[\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2+2))=[[[\{\}]]][[[\{\}]]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\omega))=[[\{\}]()][[\{\}]()]\\&\psi(\Omega_2+\psi_1(\Omega_2+\Omega))=[[\{\}][]][[\{\}][]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2)))=[[\{\}][\{\}]][[\{\}][\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2))))=[[[\{\}][\{\}]][[\{\}][\{\}]]][[[\{\}][\{\}]][[\{\}][\{\}]]]\\&\psi(\Omega_2\times2)=\{\}()\\&\psi(\Omega_2\times\omega)=\{\}(()())\\&\psi(\Omega_2\times\Omega)=\{\}[]\\&\psi(\Omega_2\times\psi_1(\Omega_2))=\{\}[\{\}]\\&\psi(\Omega_2\times\psi_1(\Omega_2\times\psi_1(\Omega_2)))=\{\}[\{\}[\{\}]]\\&\psi(\Omega_2^2=\{()\}\\&\psi(\Omega_2^\omega)=\{()()\}\\&\psi(\Omega_2^\Omega)=\{[]\}\\&\psi(\Omega_2^{\Omega_2})=\{\{\}\}\\&\psi(\Omega_2^{\Omega_2^2})=\{\{\{\}\}\}\\&\psi(\Omega_2^{\Omega_2^3})=\{\{\{\{\}\}\}\}\\&\psi(\Omega_2^{\Omega_2^\omega})=\{\}\{\}\\&\psi(\Omega_2^{\Omega_2^\Omega})=\{[]\}\{[]\}\\&\psi(\Omega_2^{\Omega_2^{\Omega_2}})=\{\{\}\}\{\{\}\}\\&\psi(\Omega_2^{\Omega_2^{\Omega_2^\omega}})=\{\{\}\{\}\}\{\{\}\{\}\}\\&\psi(\Omega₃)=\cdots\end{align}

于是得到ψ(Ω_ω)=极限

@@ 第31行： / 第31行： @@
 看上去[]可以作为Ω的角色了，这样只使用权重1~2就能达到至少BHO的序型
-<math>\begin{align}.\\&\psi(\Omega_2)=\{\}\\&\psi(\Omega_2+\Omega)=[\{\}]\\&\psi(\Omega_2+\Omega^\Omega^\omega)=[\{\}][]\\&\psi(\Omega_2+\psi_1(\Omega_2))=[\{\}][\{\}]\\&\psi(\Omega_2+\psi_1(\Omega_2)+\Omega)=[\{\}][[\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2)\times2)=[\{\}][[\{\}][\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2)\times3)=[\{\}][[\{\}][[\{\}][\{\}]]]\\&\psi(\Omega_2+\psi_1(\Omega_2+1))=[[\{\}]][[\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2+2))=[[[\{\}]]][[[\{\}]]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\omega))=[[\{\}]()][[\{\}]()]\\&\psi(\Omega_2+\psi_1(\Omega_2+\Omega))=[[\{\}][]][[\{\}][]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2)))=[[\{\}][\{\}]][[\{\}][\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2))))=[[[\{\}][\{\}]][[\{\}][\{\}]]][[[\{\}][\{\}]][[\{\}][\{\}]]]\\&\psi(\Omega_2\times2)=\{\}()\\&\psi(\Omega_2\times\omega)=\{\}(()())\\&\psi(\Omega_2\times\Omega)=\{\}[]\\&\psi(\Omega_2\times\psi_1(\Omega_2))=\{\}[\{\}]\\&\psi(\Omega_2\times\psi_1(\Omega_2\times\psi_1(\Omega_2)))=\{\}[\{\}[\{\}]]\\&\psi(\Omega_2^2=\{()\}\\&\psi(\Omega_2^\omega)=\{()()\}\\&\psi(\Omega_2^\Omega)=\{[]\}\\&\psi(\Omega_2^{\Omega_2})=\{\{\}\}\\&\psi(\Omega_2^{\Omega_2^2})=\{\{\{\}\}\}\\&\psi(\Omega_2^{\Omega_2^3})=\{\{\{\{\}\}\}\}\\&\psi(\Omega_2^{\Omega_2^\omega})=\{\}\{\}\\&\psi(\Omega_2^{\Omega_2^\Omega})=\{[]\}\{[]\}\\&\psi(\Omega_2^{\Omega_2^{\Omega_2}})=\{\{\}\}\{\{\}\}\\&\psi(\Omega_2^{\Omega_2^{\Omega_2^\omega}})=\{\{\}\{\}\}\{\{\}\{\}\}\\&\psi(\Omega₃)=\cdots\end{align}</math>
 <nowiki>\begin{align}.\\&\psi(\Omega_2)=\{\}\\&\psi(\Omega_2+\Omega)=[\{\}]\\&\psi(\Omega_2+\Omega^\Omega^\omega)=[\{\}][]\\&\psi(\Omega_2+\psi_1(\Omega_2))=[\{\}][\{\}]\\&\psi(\Omega_2+\psi_1(\Omega_2)+\Omega)=[\{\}][[\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2)\times2)=[\{\}][[\{\}][\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2)\times3)=[\{\}][[\{\}][[\{\}][\{\}]]]\\&\psi(\Omega_2+\psi_1(\Omega_2+1))=[[\{\}]][[\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2+2))=[[[\{\}]]][[[\{\}]]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\omega))=[[\{\}]()][[\{\}]()]\\&\psi(\Omega_2+\psi_1(\Omega_2+\Omega))=[[\{\}][]][[\{\}][]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2)))=[[\{\}][\{\}]][[\{\}][\{\}]]\\&\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2))))=[[[\{\}][\{\}]][[\{\}][\{\}]]][[[\{\}][\{\}]][[\{\}][\{\}]]]\\&\psi(\Omega_2\times2)=\{\}()\\&\psi(\Omega_2\times\omega)=\{\}(()())\\&\psi(\Omega_2\times\Omega)=\{\}[]\\&\psi(\Omega_2\times\psi_1(\Omega_2))=\{\}[\{\}]\\&\psi(\Omega_2\times\psi_1(\Omega_2\times\psi_1(\Omega_2)))=\{\}[\{\}[\{\}]]\\&\psi(\Omega_2^2=\{()\}\\&\psi(\Omega_2^\omega)=\{()()\}\\&\psi(\Omega_2^\Omega)=\{[]\}\\&\psi(\Omega_2^{\Omega_2})=\{\{\}\}\\&\psi(\Omega_2^{\Omega_2^2})=\{\{\{\}\}\}\\&\psi(\Omega_2^{\Omega_2^3})=\{\{\{\{\}\}\}\}\\&\psi(\Omega_2^{\Omega_2^\omega})=\{\}\{\}\\&\psi(\Omega_2^{\Omega_2^\Omega})=\{[]\}\{[]\}\\&\psi(\Omega_2^{\Omega_2^{\Omega_2}})=\{\{\}\}\{\{\}\}\\&\psi(\Omega_2^{\Omega_2^{\Omega_2^\omega}})=\{\{\}\{\}\}\{\{\}\{\}\}\\&\psi(\Omega₃)=\cdots\end{align}</nowiki>