OFFSET
0,3
COMMENTS
A binary tree is either 0 or a pair [s,t] of binary trees. Binary trees are counted by Catalan numbers A000108 and ordered by their binary code as given by A014486. Subtrees s and t correspond to A072771 and A072772.
Patcail defined the predecessor of [0,t] as t, and of [s,t], where s has predecessor s', as the result of replacing with [s',t] each occurrence of t within [s',t].
a(7), corresponding to [[0,[0,0]],0], is too large to show, exceeding an exponential tower of 2^63 2's. a(8), corresponding to [[[0,0],0],0], is much larger still, starting to approach Graham's Number. The next 3 terms are modest again, at a(9)=4, a(10)=7, a(11)=5.
The (A014138 indexed) subsequence for left skewed binary trees 0, [0,0], [[0,0],0], [[[0,0],0],0] ... forms an extremely fast growing sequence, at Buchholz's Ordinal in the Fast Growing Hierarchy.
Initial predecessors of these left skewed trees have sizes a(n) satisfying
a(n+1) = (a(n)+1)*(a(n)+3), which is A056207 counting the number of binary trees of height <= n.
LINKS
EXAMPLE
a(3)=5, since the 3rd binary tree is [[0,0],0] and its 5 successive Patcail predecessors are [[0,0],[0,0]], [0,[0,[0,0]]], [0,[0,0]], [0,0], and 0:
Index n 3 6 4 2 1 0
A014486(n) 12 50 42 10 2 0
A063171(n) 1100 110010 101010 1010 10 0
Tree [[0,0],0] [[0,0],[0,0]] [0,[0,[0,0]]] [0,[0,0]] [0,0] 0
A367433(n) 5 4 3 2 1 0
PROG
(Haskell)
data T = N | C T T deriving (Eq, Show)
a014486 = [0..] >>= at where
at 0 = [N]
at n = [C s t | (ns, s) <- to$n-1, t <- at$n-1-ns]
to n = (0, N):[(1+ns+nt, C s t)|n>0, (ns, s)<-to$n-1, (nt, t)<-to$n-1-ns]
predT (C N t) = t
predT (C s t) = go u where
u = [predT s) t
go v = if v==t then u else case v of
N -> N
C s t -> [go s) (go t)
a367433 = map nPred a014486 where
nPred N = 0
nPred t = 1 + nPred (predT t)
CROSSREFS
KEYWORD
nonn
AUTHOR
John Tromp, Nov 18 2023
STATUS
approved