赋权二叉树：修订间差异

←上一编辑下一编辑→

可视化wikitext

2026年2月21日 (六) 16:11的版本

赋权二叉树（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相同

[] = ε(0)
([]) = ε(0)+1
(([])) = ε(0)+2
([])() = ε(0)+ω
([])([]) = ε(0)·2
(([]))([]) = ε(0)·3
(([])())([]) = ε(0)·ω
(([])([]))([]) = ε(0)^2
(([]))(([])) = ε(0)^ω
(([])([]))(([])([])) = ε(0)^ε(0)
[]() = ε(1)
[](()) = ε(2)
[](()()) = ε(ω)
[]([]) = ε(ε(0))
[]([]([])) = ε(ε(ε(0)))
[()] = ζ(0)
([()]) = ζ(0)+1
([()])([()]) = ζ(0)·2
[]([()]) = ε(ζ(0)+1)
[](([()])) = ε(ζ(0)+2)
[]([]([()])) = ε(ε(ζ(0)+1))
[()]() = ζ(1)
[()]([()]) = ζ(ζ(0))
[(())] = ϑ(Ω·3) = φ(3,0)
[]([(())]) = ϑ(Ω+ϑ(Ω·3))
[()]([(())]) = ϑ(Ω·2+ϑ(Ω·3))
[(())]() = ϑ(Ω·3+1)
[((()))] = ϑ(Ω·4)
[()()] = ϑ(Ω·ω)
[(()())] = ϑ(Ω·(ω+1))
[(()())(()())] = ϑ(Ω·ω^ω^ω)
[([])] = ϑ(Ω·ϑ(Ω))
[([])]() = ϑ(Ω·ϑ(Ω)+1)
[(([]))] = ϑ(Ω·(ϑ(Ω)+1))
[([])([])] = ϑ(Ω·ϑ(Ω)·2)
[([]())] = ϑ(Ω·ϑ(Ω+1))
[([()])] = ϑ(Ω·ϑ(Ω·2))
[([([])])] = ϑ(Ω·ϑ(Ω·ϑ(Ω)))
[[]] = ϑ(Ω^2) = Γ(0)
[]([[]]) = ϑ(Ω+ϑ(Ω^2))
[()]([[]]) = ϑ(Ω·2+ϑ(Ω^2))
[([[]])] = ϑ(Ω·ϑ(Ω^2))
[([([[]])])] = ϑ(Ω·ϑ(Ω·ϑ(Ω^2)))
[[]]() = ϑ(Ω^2+1)
[[]]([[]]) = ϑ(Ω^2+ϑ(Ω^2))
[[]()] = ϑ(Ω^2+Ω)
[[]([[]])] = ϑ(Ω^2+Ω·ϑ(Ω^2))
[[()]]= ϑ(Ω^2·2)
[[([[]])]] = ϑ(Ω^2·ϑ(Ω^2))
[[[]]] = ϑ(Ω^3)
[[[]]]() = ϑ(Ω^3+1)
[[[]]()] = ϑ(Ω^3+Ω)
[[[]()]] = ϑ(Ω^3+Ω^2)
[[[()]]] = ϑ(Ω^3·2)
[[[[]]]] = ϑ(Ω^4)
[][] = ϑ(Ω^ω)
([][]) = ϑ(Ω^ω)+1
[]([][]) = ϑ(Ω+ϑ(Ω^ω))
[([][])] = ϑ(Ω·ϑ(Ω^ω))
[[([][])]] = ϑ(Ω^2·ϑ(Ω^ω))
[[][]] = ϑ(Ω^ω+1)
[[][]]() = ϑ(Ω^ω+2)
[[][]]([][]) = ϑ(Ω^ω+ϑ(Ω^ω))
[[[][]]] = ϑ(Ω^ω+Ω)
[[[][]]]() = ϑ(Ω^ω+Ω+1)
[[[][]]()] = ϑ(Ω^ω+Ω·2)
[[[[][]]]] = ϑ(Ω^ω+Ω^2)
[[[[[][]]]]] = ϑ(Ω^ω+Ω^3)
[()][] = ϑ(Ω^ω·2)
[[()][]] = ϑ(Ω^ω·2+1)
[[[()][]]] = ϑ(Ω^ω·2+Ω)
[[[[()][]]]] = ϑ(Ω^ω·2+Ω^2)
[(())][] = ϑ(Ω^ω·3)
[([][])][] = ϑ(Ω^ω·ϑ(Ω^ω))
[[]][] = ϑ(Ω^(ω+1))
[[[]]][] = ϑ(Ω^(ω+2))
[[][]][] = ϑ(Ω^(ω·2))
[[[][]][]] = ϑ(Ω^(ω·2)+1)
[[[[][]][]]] = ϑ(Ω^(ω·2)+Ω)
[[[][]]][] = ϑ(Ω^(ω·2)+Ω^ω)
[[[][]]()][] = ϑ(Ω^(ω·2)+Ω^ω·2)
[[[[][]]]][] = ϑ(Ω^(ω·2)+Ω^(ω+1))
[[()][]][] = ϑ(Ω^(ω·2)·2)
[[[]][]][] = ϑ(Ω^(ω·2+1))
[[[][]][]][] = ϑ(Ω^(ω·3))
[[[[][]][]][]][] = ϑ(Ω^(ω·4))
[()][()] = ϑ(Ω^ω^2)
[[()][()]] = ϑ(Ω^ω^2+1)
[[[()][()]][]] = ϑ(Ω^ω^2+Ω^ω)
[(())][()] = ϑ(Ω^ω^2·2)
[[]][()] = ϑ(Ω^(ω^2+1))
[[()][()]][()] = ϑ(Ω^(ω^2·2))
[(())][(())] = ϑ(Ω^ω^3)
[([])][([])] = ϑ(Ω^ϑ(Ω))
[[]][[]] = ϑ(Ω^Ω) = LVO

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

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

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

@@ 第28行： / 第28行： @@
 上述这些都跟ε(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}
+* [] = ε(0)
+* ([]) = ε(0)+1
+* (([])) = ε(0)+2
+* ([])() = ε(0)+ω
+* ([])([]) = ε(0)·2
+* (([]))([]) = ε(0)·3
+* (([])())([]) = ε(0)·ω
+* (([])([]))([]) = ε(0)^2
+* (([]))(([])) = ε(0)^ω
+* (([])([]))(([])([])) = ε(0)^ε(0)
+* []() = ε(1)
+* [](()) = ε(2)
+* [](()()) = ε(ω)
+* []([]) = ε(ε(0))
+* []([]([])) = ε(ε(ε(0)))
+* [()] = ζ(0)
+* ([()]) = ζ(0)+1
+* ([()])([()]) = ζ(0)·2
+* []([()]) = ε(ζ(0)+1)
+* [](([()])) = ε(ζ(0)+2)
+* []([]([()])) = ε(ε(ζ(0)+1))
+* [()]() = ζ(1)
+* [()]([()]) = ζ(ζ(0))
+* [(())] = ϑ(Ω·3) = φ(3,0)
+* []([(())]) = ϑ(Ω+ϑ(Ω·3))
+* [()]([(())]) = ϑ(Ω·2+ϑ(Ω·3))
+* [(())]() = ϑ(Ω·3+1)
+* [((()))] = ϑ(Ω·4)
+* [()()] = ϑ(Ω·ω)
+* [(()())] = ϑ(Ω·(ω+1))
+* [(()())(()())] = ϑ(Ω·ω^ω^ω)
+* [([])] = ϑ(Ω·ϑ(Ω))
+* [([])]() = ϑ(Ω·ϑ(Ω)+1)
+* [(([]))] = ϑ(Ω·(ϑ(Ω)+1))
+* [([])([])] = ϑ(Ω·ϑ(Ω)·2)
+* [([]())] = ϑ(Ω·ϑ(Ω+1))
+* [([()])] = ϑ(Ω·ϑ(Ω·2))
+* [([([])])] = ϑ(Ω·ϑ(Ω·ϑ(Ω)))
+* [[]] = ϑ(Ω^2) = Γ(0)
+* []([[]]) = ϑ(Ω+ϑ(Ω^2))
+* [()]([[]]) = ϑ(Ω·2+ϑ(Ω^2))
+* [([[]])] = ϑ(Ω·ϑ(Ω^2))
+* [([([[]])])] = ϑ(Ω·ϑ(Ω·ϑ(Ω^2)))
+* [[]]() = ϑ(Ω^2+1)
+* [[]]([[]]) = ϑ(Ω^2+ϑ(Ω^2))
+* [[]()] = ϑ(Ω^2+Ω)
+* [[]([[]])] = ϑ(Ω^2+Ω·ϑ(Ω^2))
+* <nowiki>[[()]]</nowiki>= ϑ(Ω^2·2)
+* [[([[]])]] = ϑ(Ω^2·ϑ(Ω^2))
+* [[[]]] = ϑ(Ω^3)
+* [[[]]]() = ϑ(Ω^3+1)
+* [[[]]()] = ϑ(Ω^3+Ω)
+* [[[]()]] = ϑ(Ω^3+Ω^2)
+* [[[()]]] = ϑ(Ω^3·2)
+* [[[[]]]] = ϑ(Ω^4)
+* [][] = ϑ(Ω^ω)
+* ([][]) = ϑ(Ω^ω)+1
+* []([][]) = ϑ(Ω+ϑ(Ω^ω))
+* [([][])] = ϑ(Ω·ϑ(Ω^ω))
+* [[([][])]] = ϑ(Ω^2·ϑ(Ω^ω))
+* [[][]] = ϑ(Ω^ω+1)
+* [[][]]() = ϑ(Ω^ω+2)
+* [[][]]([][]) = ϑ(Ω^ω+ϑ(Ω^ω))
+* [[[][]]] = ϑ(Ω^ω+Ω)
+* [[[][]]]() = ϑ(Ω^ω+Ω+1)
+* [[[][]]()] = ϑ(Ω^ω+Ω·2)
+* [[[[][]]]] = ϑ(Ω^ω+Ω^2)
+* [[[[[][]]]]] = ϑ(Ω^ω+Ω^3)
+* [()][] = ϑ(Ω^ω·2)
+* [[()][]] = ϑ(Ω^ω·2+1)
+* [[[()][]]] = ϑ(Ω^ω·2+Ω)
+* [[[[()][]]]] = ϑ(Ω^ω·2+Ω^2)
+* [(())][] = ϑ(Ω^ω·3)
+* [([][])][] = ϑ(Ω^ω·ϑ(Ω^ω))
+* [[]][] = ϑ(Ω^(ω+1))
+* [[[]]][] = ϑ(Ω^(ω+2))
+* [[][]][] = ϑ(Ω^(ω·2))
+* [[[][]][]] = ϑ(Ω^(ω·2)+1)
+* [[[[][]][]]] = ϑ(Ω^(ω·2)+Ω)
+* [[[][]]][] = ϑ(Ω^(ω·2)+Ω^ω)
+* [[[][]]()][] = ϑ(Ω^(ω·2)+Ω^ω·2)
+* [[[[][]]]][] = ϑ(Ω^(ω·2)+Ω^(ω+1))
+* [[()][]][] = ϑ(Ω^(ω·2)·2)
+* [[[]][]][] = ϑ(Ω^(ω·2+1))
+* [[[][]][]][] = ϑ(Ω^(ω·3))
+* [[[[][]][]][]][] = ϑ(Ω^(ω·4))
+* [()][()] = ϑ(Ω^ω^2)
+* [[()][()]] = ϑ(Ω^ω^2+1)
+* [[[()][()]][]] = ϑ(Ω^ω^2+Ω^ω)
+* [(())][()] = ϑ(Ω^ω^2·2)
+* [[]][()] = ϑ(Ω^(ω^2+1))
+* [[()][()]][()] = ϑ(Ω^(ω^2·2))
+* [(())][(())] = ϑ(Ω^ω^3)
+* [([])][([])] = ϑ(Ω^ϑ(Ω))
+* [[]][[]] = ϑ(Ω^Ω) = LVO
 看上去[]可以作为Ω的角色了，这样只使用权重1~2就能达到至少BHO的序型