赋权二叉树

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

定义

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

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

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

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

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

分析

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

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

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

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

\begin{align}s\\&[] = \varepsilon_0\\&([]) = \varepsilon_0+1\\&(([])) = \varepsilon_0+2\\&([])() = \varepsilon_0+\omega\\&([])([]) = \varepsilon_0\times2\\&(([]))([]) = \varepsilon_0\times3\\&(([])())([]) = \varepsilon_0\times\omega\\&(([])([]))([]) = \varepsilon_0^2\\&(([]))(([])) = \varepsilon_0^\omega\\&(([])([]))(([])([])) = \varepsilon_0^\varepsilon_0\\&[]() = \varepsilon_0\\&[](()) = \varepsilon_0\\&[](()()) = \varepsilon_0\\&[]([]) = ε(\varepsilon_0)\\&[]([]([])) = ε(ε(\varepsilon_0))\\&[()] = \varepsilon_0\\&([()]) = \varepsilon_0+1\\&([()])([()]) = \varepsilon_0\times2\\&[]([()]) = ε(\varepsilon_0+1)\\&[](([()])) = ε(\varepsilon_0+2)\\&[]([]([()])) = ε(ε(\varepsilon_0+1))\\&[()]() = ζ(1)\\&[()]([()]) = ζ(\varepsilon_0)\\&[(())] = \vartheta(\Omega\times3) = φ(3,0)\\&[]([(())]) = \vartheta(\Omega+\vartheta(\Omega\times3))\\&[()]([(())]) = \vartheta(\Omega\times2+\vartheta(\Omega\times3))\\&[(())]() = \vartheta(\Omega\times3+1)\\&[((()))] = \vartheta(\Omega\times4)\\&[()()] = \vartheta(\Omega\times\omega)\\&[(()())] = \vartheta(\Omega\times(\omega+1))\\&[(()())(()())] = \vartheta(\Omega\times\omega^\omega^\omega)\\&[([])] = \vartheta(\Omega\times\vartheta(\Omega))\\&[([])]() = \vartheta(\Omega\times\vartheta(\Omega)+1)\\&[(([]))] = \vartheta(\Omega\times(\vartheta(\Omega)+1))\\&[([])([])] = \vartheta(\Omega\times\vartheta(\Omega)\times2)\\&[([]())] = \vartheta(\Omega\times\vartheta(\Omega+1))\\&[([()])] = \vartheta(\Omega\times\vartheta(\Omega\times2))\\&[([([])])] = \vartheta(\Omega\times\vartheta(\Omega\times\vartheta(\Omega)))\\&[[]] = \vartheta(\Omega^2) = Γ(0)\\&[]([[]]) = \vartheta(\Omega+\vartheta(\Omega^2))\\&[()]([[]]) = \vartheta(\Omega\times2+\vartheta(\Omega^2))\\&[([[]])] = \vartheta(\Omega\times\vartheta(\Omega^2))\\&[([([[]])])] = \vartheta(\Omega\times\vartheta(\Omega\times\vartheta(\Omega^2)))\\&[[]]() = \vartheta(\Omega^2+1)\\&[[]]([[]]) = \vartheta(\Omega^2+\vartheta(\Omega^2))\\&[[]()] = \vartheta(\Omega^2+\Omega)\\&[[]([[]])] = \vartheta(\Omega^2+\Omega\times\vartheta(\Omega^2))\\&() = \vartheta(\Omega^2\times2)\\&[[([[]])]] = \vartheta(\Omega^2\times\vartheta(\Omega^2))\\&[[[]]] = \vartheta(\Omega^3)\\&[[[]]]() = \vartheta(\Omega^3+1)\\&[[[]]()] = \vartheta(\Omega^3+\Omega)\\&[[[]()]] = \vartheta(\Omega^3+\Omega^2)\\&[[[()]]] = \vartheta(\Omega^3\times2)\\&[[[[]]]] = \vartheta(\Omega^4)\\&[][] = \vartheta(\Omega^\omega)\\&([][]) = \vartheta(\Omega^\omega)+1\\&[]([][]) = \vartheta(\Omega+\vartheta(\Omega^\omega))\\&[([][])] = \vartheta(\Omega\times\vartheta(\Omega^\omega))\\&[[([][])]] = \vartheta(\Omega^2\times\vartheta(\Omega^\omega))\\&[[][]] = \vartheta(\Omega^\omega+1)\\&[[][]]() = \vartheta(\Omega^\omega+2)\\&[[][]]([][]) = \vartheta(\Omega^\omega+\vartheta(\Omega^\omega))\\&[[[][]]] = \vartheta(\Omega^\omega+\Omega)\\&[[[][]]]() = \vartheta(\Omega^\omega+\Omega+1)\\&[[[][]]()] = \vartheta(\Omega^\omega+\Omega\times2)\\&[[[[][]]]] = \vartheta(\Omega^\omega+\Omega^2)\\&[[[[[][]]]]] = \vartheta(\Omega^\omega+\Omega^3)\\&[()][] = \vartheta(\Omega^\omega\times2)\\&[[()][]] = \vartheta(\Omega^\omega\times2+1)\\&[[[()][]]] = \vartheta(\Omega^\omega\times2+\Omega)\\&[[[[()][]]]] = \vartheta(\Omega^\omega\times2+\Omega^2)\\&[(())][] = \vartheta(\Omega^\omega\times3)\\&[([][])][] = \vartheta(\Omega^\omega\times\vartheta(\Omega^\omega))\\&[[]][] = \vartheta(\Omega^(\omega+1))\\&[[[]]][] = \vartheta(\Omega^(\omega+2))\\&[[][]][] = \vartheta(\Omega^(\omega\times2))\\&[[[][]][]] = \vartheta(\Omega^(\omega\times2)+1)\\&[[[[][]][]]] = \vartheta(\Omega^(\omega\times2)+\Omega)\\&[[[][]]][] = \vartheta(\Omega^(\omega\times2)+\Omega^\omega)\\&[[[][]]()][] = \vartheta(\Omega^(\omega\times2)+\Omega^\omega\times2)\\&[[[[][]]]][] = \vartheta(\Omega^(\omega\times2)+\Omega^(\omega+1))\\&[[()][]][] = \vartheta(\Omega^(\omega\times2)\times2)\\&[[[]][]][] = \vartheta(\Omega^(\omega\times2+1))\\&[[[][]][]][] = \vartheta(\Omega^(\omega\times3))\\&[[[[][]][]][]][] = \vartheta(\Omega^(\omega\times4))\\&[()][()] = \vartheta(\Omega^\omega^2)\\&[[()][()]] = \vartheta(\Omega^\omega^2+1)\\&[[[()][()]][]] = \vartheta(\Omega^\omega^2+\Omega^\omega)\\&[(())][()] = \vartheta(\Omega^\omega^2\times2)\\&[[]][()] = \vartheta(\Omega^(\omega^2+1))\\&[[()][()]][()] = \vartheta(\Omega^(\omega^2\times2))\\&[(())][(())] = \vartheta(\Omega^\omega^3)\\&[([])][([])] = \vartheta(\Omega^\vartheta(\Omega))\\&[[]][[]] = \vartheta(\Omega^\Omega) = LVO\end{align}

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

• ψ(Ω₂)={}
• ψ(Ω₂+Ω)=[{}]
• ψ(Ω₂+Ω^Ω^ω)=[{}][]
• ψ(Ω₂+ψ₁(Ω₂))=[{}][{}]
• ψ(Ω₂+ψ₁(Ω₂)+Ω)=[{}][[{}]]
• ψ(Ω₂+ψ₁(Ω₂)×2)=[{}][[{}][{}]]
• ψ(Ω₂+ψ₁(Ω₂)×3)=[{}][[{}][[{}][{}]]]
• ψ(Ω₂+ψ₁(Ω₂+1))=[[{}]][[{}]]
• ψ(Ω₂+ψ₁(Ω₂+2))=[[[{}]]][[[{}]]]
• ψ(Ω₂+ψ₁(Ω₂+ω))=[[{}]()][[{}]()]
• ψ(Ω₂+ψ₁(Ω₂+Ω))=[[{}][]][[{}][]]
• ψ(Ω₂+ψ₁(Ω₂+ψ₁(Ω₂)))=[[{}][{}]][[{}][{}]]
• ψ(Ω₂+ψ₁(Ω₂+ψ₁(Ω₂+ψ₁(Ω₂))))=[[[{}][{}]][[{}][{}]]][[[{}][{}]][[{}][{}]]]
• ψ(Ω₂×2)={}()
• ψ(Ω₂×ω)={}(()())
• ψ(Ω₂×Ω)={}[]
• ψ(Ω₂×ψ₁(Ω₂))={}[{}]
• ψ(Ω₂×ψ₁(Ω₂×ψ₁(Ω₂)))={}[{}[{}]]
• ψ(Ω₂²)={()}
• ψ(Ω₂^ω)={()()}
• ψ(Ω₂^Ω)={[]}
• ψ(Ω₂^Ω₂)={{}}
• ψ(Ω₂^Ω₂³)={{{{}}}}
• ψ(Ω₂^Ω₂^ω)={}{}
• ψ(Ω₂^Ω₂^Ω)={[]}{[]}
• ψ(Ω₂^Ω₂^Ω₂)={{}}{{}}
• ψ(Ω₂^Ω₂^Ω₂^ω)={{}{}}{{}{}}

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