赋权二叉树

赋权二叉树（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.<>表示权值4.根节点不写。

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

• 单根=0
• $()=1$
• $(())=2$
• $()()=\omega$

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

$\begin{array}{r}.\\ & []={\epsilon }_0\\ & ([])={\epsilon }_0+1\\ & (([]))={\epsilon }_0+2\\ & ([])()={\epsilon }_0+\omega \\ & ([])([])={\epsilon }_0\times 2\\ & (([]))([])={\epsilon }_0\times 3\\ & (([])())([])={\epsilon }_0\times \omega \\ & (([])([]))([])={\epsilon }_0^2\\ & (([]))(([]))={\epsilon }_0^{\omega }\\ & (([])([]))(([])([]))={\epsilon }_0^{\epsilon }{}_0\\ & []()={\epsilon }_1\\ & [](())={\epsilon }_2\\ & [](()())={\epsilon }_{\omega }\\ & []([])={\epsilon }_{{\epsilon }_0}\\ & []([]([]))={\epsilon }_{{\epsilon }_{{\epsilon }_0}}\\ & [()]={\zeta }_0\\ & ([()])={\zeta }_0+1\\ & ([()])([()])={\zeta }_0\times 2\\ & []([()])={\epsilon }_{{\zeta }_0+1}\\ & [](([()]))={\epsilon }_{{\zeta }_0+2}\\ & []([]([()]))={\epsilon }_{{\epsilon }_{{\zeta }_0+1}}\\ & [()]()={\zeta }_1\\ & [()]([()])={\zeta }_{{\zeta }_0}\\ & [(())]=\vartheta (\mathrm{\Omega }\times 3)=\phi (3,0)\\ & []([(())])=\vartheta (\mathrm{\Omega }+\vartheta (\mathrm{\Omega }\times 3))\\ & [()]([(())])=\vartheta (\mathrm{\Omega }\times 2+\vartheta (\mathrm{\Omega }\times 3))\\ & [(())]()=\vartheta (\mathrm{\Omega }\times 3+1)\\ & [((()))]=\vartheta (\mathrm{\Omega }\times 4)\\ & [()()]=\vartheta (\mathrm{\Omega }\times \omega )\\ & [(()())]=\vartheta (\mathrm{\Omega }\times (\omega +1))\\ & [(()())(()())]=\vartheta (\mathrm{\Omega }\times {\omega }^{{\omega }^{\omega }})\\ & [([])]=\vartheta (\mathrm{\Omega }\times \vartheta (\mathrm{\Omega }))\\ & [([])]()=\vartheta (\mathrm{\Omega }\times \vartheta (\mathrm{\Omega })+1)\\ & [(([]))]=\vartheta (\mathrm{\Omega }\times (\vartheta (\mathrm{\Omega })+1))\\ & [([])([])]=\vartheta (\mathrm{\Omega }\times \vartheta (\mathrm{\Omega })\times 2)\\ & [([]())]=\vartheta (\mathrm{\Omega }\times \vartheta (\mathrm{\Omega }+1))\\ & [([()])]=\vartheta (\mathrm{\Omega }\times \vartheta (\mathrm{\Omega }\times 2))\\ & [([([])])]=\vartheta (\mathrm{\Omega }\times \vartheta (\mathrm{\Omega }\times \vartheta (\mathrm{\Omega })))\\ & [[]]=\vartheta ({\mathrm{\Omega }}^2)={\mathrm{\Gamma }}_0\\ & []([[]])=\vartheta (\mathrm{\Omega }+\vartheta ({\mathrm{\Omega }}^2))\\ & [()]([[]])=\vartheta (\mathrm{\Omega }\times 2+\vartheta ({\mathrm{\Omega }}^2))\\ & [([[]])]=\vartheta (\mathrm{\Omega }\times \vartheta ({\mathrm{\Omega }}^2))\\ & [([([[]])])]=\vartheta (\mathrm{\Omega }\times \vartheta (\mathrm{\Omega }\times \vartheta ({\mathrm{\Omega }}^2)))\\ & [[]]()=\vartheta ({\mathrm{\Omega }}^2+1)\\ & [[]]([[]])=\vartheta ({\mathrm{\Omega }}^2+\vartheta ({\mathrm{\Omega }}^2))\\ & [[]()]=\vartheta ({\mathrm{\Omega }}^2+\mathrm{\Omega })\\ & [[]([[]])]=\vartheta ({\mathrm{\Omega }}^2+\mathrm{\Omega }\times \vartheta ({\mathrm{\Omega }}^2))\\ & [[()]]=\vartheta ({\mathrm{\Omega }}^2\times 2)\\ & [[([[]])]]=\vartheta ({\mathrm{\Omega }}^2\times \vartheta ({\mathrm{\Omega }}^2))\\ & [[[]]]=\vartheta ({\mathrm{\Omega }}^3)\\ & [[[]]]()=\vartheta ({\mathrm{\Omega }}^3+1)\\ & [[[]]()]=\vartheta ({\mathrm{\Omega }}^3+\mathrm{\Omega })\\ & [[[]()]]=\vartheta ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2)\\ & [[[()]]]=\vartheta ({\mathrm{\Omega }}^3\times 2)\\ & [[[[]]]]=\vartheta ({\mathrm{\Omega }}^4)\\ & [][]=\vartheta ({\mathrm{\Omega }}^{\omega })\\ & ([][])=\vartheta ({\mathrm{\Omega }}^{\omega })+1\\ & []([][])=\vartheta (\mathrm{\Omega }+\vartheta ({\mathrm{\Omega }}^{\omega }))\\ & [([][])]=\vartheta (\mathrm{\Omega }\times \vartheta ({\mathrm{\Omega }}^{\omega }))\\ & [[([][])]]=\vartheta ({\mathrm{\Omega }}^2\times \vartheta ({\mathrm{\Omega }}^{\omega }))\\ & [[][]]=\vartheta ({\mathrm{\Omega }}^{\omega }+1)\\ & [[][]]()=\vartheta ({\mathrm{\Omega }}^{\omega }+2)\\ & [[][]]([][])=\vartheta ({\mathrm{\Omega }}^{\omega }+\vartheta ({\mathrm{\Omega }}^{\omega }))\\ & [[[][]]]=\vartheta ({\mathrm{\Omega }}^{\omega }+\mathrm{\Omega })\\ & [[[][]]]()=\vartheta ({\mathrm{\Omega }}^{\omega }+\mathrm{\Omega }+1)\\ & [[[][]]()]=\vartheta ({\mathrm{\Omega }}^{\omega }+\mathrm{\Omega }\times 2)\\ & [[[[][]]]]=\vartheta ({\mathrm{\Omega }}^{\omega }+{\mathrm{\Omega }}^2)\\ & [[[[[][]]]]]=\vartheta ({\mathrm{\Omega }}^{\omega }+{\mathrm{\Omega }}^3)\\ & [()][]=\vartheta ({\mathrm{\Omega }}^{\omega }\times 2)\\ & [[()][]]=\vartheta ({\mathrm{\Omega }}^{\omega }\times 2+1)\\ & [[[()][]]]=\vartheta ({\mathrm{\Omega }}^{\omega }\times 2+\mathrm{\Omega })\\ & [[[[()][]]]]=\vartheta ({\mathrm{\Omega }}^{\omega }\times 2+{\mathrm{\Omega }}^2)\\ & [(())][]=\vartheta ({\mathrm{\Omega }}^{\omega }\times 3)\\ & [([][])][]=\vartheta ({\mathrm{\Omega }}^{\omega }\times \vartheta ({\mathrm{\Omega }}^{\omega }))\\ & [[]][]=\vartheta ({\mathrm{\Omega }}^{\omega +1})\\ & [[[]]][]=\vartheta ({\mathrm{\Omega }}^{\omega +2})\\ & [[][]][]=\vartheta ({\mathrm{\Omega }}^{\omega \times 2})\\ & [[[][]][]]=\vartheta ({\mathrm{\Omega }}^{\omega \times 2}+1)\\ & [[[[][]][]]]=\vartheta ({\mathrm{\Omega }}^{\omega \times 2}+\mathrm{\Omega })\\ & [[[][]]][]=\vartheta ({\mathrm{\Omega }}^{\omega \times 2}+{\mathrm{\Omega }}^{\omega })\\ & [[[][]]()][]=\vartheta ({\mathrm{\Omega }}^{\omega \times 2}+{\mathrm{\Omega }}^{\omega }\times 2)\\ & [[[[][]]]][]=\vartheta ({\mathrm{\Omega }}^{\omega \times 2}+{\mathrm{\Omega }}^{\omega +1})\\ & [[()][]][]=\vartheta ({\mathrm{\Omega }}^{\omega \times 2}\times 2)\\ & [[[]][]][]=\vartheta ({\mathrm{\Omega }}^{\omega \times 2+1})\\ & [[[][]][]][]=\vartheta ({\mathrm{\Omega }}^{\omega \times 3})\\ & [[[[][]][]][]][]=\vartheta ({\mathrm{\Omega }}^{\omega \times 4})\\ & [()][()]=\vartheta ({\mathrm{\Omega }}^{{\omega }^2})\\ & [[()][()]]=\vartheta ({\mathrm{\Omega }}^{{\omega }^2}+1)\\ & [[[()][()]][]]=\vartheta ({\mathrm{\Omega }}^{{\omega }^2}+{\mathrm{\Omega }}^{\omega })\\ & [(())][()]=\vartheta ({\mathrm{\Omega }}^{{\omega }^2}\times 2)\\ & [[]][()]=\vartheta ({\mathrm{\Omega }}^{{\omega }^2+1})\\ & [[()][()]][()]=\vartheta ({\mathrm{\Omega }}^{{\omega }^2\times 2})\\ & [(())][(())]=\vartheta ({\mathrm{\Omega }}^{{\omega }^3})\\ & [([])][([])]=\vartheta ({\mathrm{\Omega }}^{\vartheta (\mathrm{\Omega })})\\ & [[]][[]]=\vartheta ({\mathrm{\Omega }}^{\mathrm{\Omega }})=LVO\end{array}$

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

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

于是得到ψ(Ω_ω)是wbtree的极限。