A333311 - OEIS

%I #11 Oct 24 2024 18:32:22

%S 2,4,7,12,19,29,41,56,71,90,109,133,155,183,209,242,271,309,340,384,

%T 418,466,505,555,600,651,703,758,813,874,931,999,1058,1133,1195,1277,

%U 1343,1432,1502,1597,1671,1771,1849,1954,2036,2142

%N 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 The branching order is pre-order depth-first search.

%H Jan Koornstra, <a href="/A333311/a333311.pdf">The first 100 generations in rainbow colour-coding</a>

%e 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 Generation 1:      \/

%e a(2) = 4, yielding new leaves at respectively (-2, 1), (-1, 2), (1, 2) and (2, 1):

%e Generation 2:    _|  |_

%e                    \/

%e 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 Generation 3:     \/

%e                 \_|  |_/

%e                 /  \/  \

%o (Python)

%o used = [[0, 0]] # nodes used in the tree

%o nodes = [[0, 0, 0]] # x, y, direction

%o gen = 0

%o terminations = [0]

%o leaves = [1]

%o 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 while gen < 100:

%o   terminations.append(0)

%o   length = len(nodes)

%o   for n in range(length):

%o     x1 = nodes[n][0] + directions[(gen+1)%2][nodes[n][2]][0]

%o     y1 = nodes[n][1] + directions[(gen+1)%2][nodes[n][2]][1]

%o     x2 = nodes[n][0] + directions[(gen+1)%2][nodes[n][2]][2]

%o     y2 = nodes[n][1] + directions[(gen+1)%2][nodes[n][2]][3]

%o     if [x1, y1] not in used and [x2, y2] not in used:

%o       nodes += [[x1, y1, (nodes[n][2] - gen%2)%4]]

%o       nodes += [[x2, y2, (nodes[n][2] + (gen+1)%2)%4]]

%o       used += [[x1, y1], [x2, y2]]

%o       leaves[gen] += 1

%o     else:

%o       terminations[gen] += 1

%o   nodes = nodes[length:]

%o   gen += 1

%o   leaves.append(leaves[-1])

%o print(leaves[:-1]) # This sequence.

%o print(terminations[:-1])

%Y Cf. A172310.

%K nonn

%O 1,1

%A _Jan Koornstra_, Mar 14 2020.