cp's OEIS Frontend

A333311 a(n) is the total number of leaves of a binary tree of depth n on a square grid where each parent-node branches out in the two directions closest to the direction of the edge from which it sprang, either along the grid for even generations or across for odd generations ('L-toothpick'), yet only if the child-nodes' coordinates are not occupied already.

%I A333311 #13 Jul 09 2025 04:51:36
%S A333311 2,4,7,12,19,29,41,56,71,90,109,133,155,183,209,242,271,309,340,384,
%T A333311 418,466,505,555,600,651,703,758,813,874,931,999,1058,1133,1195,1277,
%U A333311 1343,1432,1502,1597,1671,1771,1849,1954,2036,2142
%N A333311 a(n) is the total number of leaves of a binary tree of depth n on a square grid where each parent-node branches out in the two directions closest to the direction of the edge from which it sprang, either along the grid for even generations or across for odd generations ('L-toothpick'), yet only if the child-nodes' coordinates are not occupied already.
%C A333311 The branching order is pre-order depth-first search.
%H A333311 Jan Koornstra, <a href="/A333311/a333311.pdf">The first 100 generations in rainbow colour-coding</a>
%e A333311 a(1) = 2, since two branches can be formed from the root-node at (0, 0) across the diagonals of the grid to (-1, 1) and (1, 1) respectively, hence:
%e A333311 Generation 1:      \/
%e A333311 a(2) = 4, yielding new leaves at respectively (-2, 1), (-1, 2), (1, 2) and (2, 1):
%e A333311 Generation 2:    _|  |_
%e A333311                    \/
%e A333311 a(3) = 7, since the node at (1, 2) cannot branch out, as one of its child-nodes would get coordinates (0, 3), which is already in use by a node branched from (-1, 2).
%e A333311 Generation 3:     \/
%e A333311                 \_|  |_/
%e A333311                 /  \/  \
%o A333311 (Python)
%o A333311 used = [[0, 0]] # nodes used in the tree
%o A333311 nodes = [[0, 0, 0]] # x, y, direction
%o A333311 gen = 0
%o A333311 terminations = [0]
%o A333311 leaves = [1]
%o A333311 directions = [[[-1, 0, 0, 1], [0, 1, 1, 0], [1, 0, 0, -1], [0, -1, -1, 0]], [[-1, 1, 1, 1], [1, 1, 1, -1], [1, -1, -1, -1], [-1, -1, -1, 1]]] # LU/RU/RD/DL, U/R/D/L
%o A333311 while gen < 100:
%o A333311   terminations.append(0)
%o A333311   length = len(nodes)
%o A333311   for n in range(length):
%o A333311     x1 = nodes[n][0] + directions[(gen+1)%2][nodes[n][2]][0]
%o A333311     y1 = nodes[n][1] + directions[(gen+1)%2][nodes[n][2]][1]
%o A333311     x2 = nodes[n][0] + directions[(gen+1)%2][nodes[n][2]][2]
%o A333311     y2 = nodes[n][1] + directions[(gen+1)%2][nodes[n][2]][3]
%o A333311     if [x1, y1] not in used and [x2, y2] not in used:
%o A333311       nodes += [[x1, y1, (nodes[n][2] - gen%2)%4]]
%o A333311       nodes += [[x2, y2, (nodes[n][2] + (gen+1)%2)%4]]
%o A333311       used += [[x1, y1], [x2, y2]]
%o A333311       leaves[gen] += 1
%o A333311     else:
%o A333311       terminations[gen] += 1
%o A333311   nodes = nodes[length:]
%o A333311   gen += 1
%o A333311   leaves.append(leaves[-1])
%o A333311 print(leaves[:-1]) # This sequence.
%o A333311 print(terminations[:-1])
%Y A333311 Cf. A172310.
%K A333311 nonn
%O A333311 1,1
%A A333311 _Jan Koornstra_, Mar 14 2020