A363718 Irregular triangle read by rows. An infinite binary tree which has root node 1 in row n = 0. Each node then has left child m-1 if greater than 0 and right child m+1, where m is the value of the parent node.

1, 2, 1, 3, 2, 2, 4, 1, 3, 1, 3, 3, 5, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 1, 3, 1, 3, 3, 5, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 4, 4, 6, 2, 4, 4, 6, 4, 6, 6, 8, 1, 3, 1, 3, 3, 5, 1, 3, 1

Offset: 0

Author

John Tyler Rascoe, Jun 17 2023

Keywords

• nonn
• easy
• tabf

Comments

The paths through the tree represent the compositions counted in A173258 that have first part 1.

For rows n > 1, row n starts with row n-2.

Any positive number k will first appear in the (k-1)-th row and thereafter in rows of opposite parity to k. The number of times k will appear in row n is A053121(n,k-1).

Row n >= 1 gives the row lengths of the Christmas tree pattern of order n (cf. A367508). - Paolo Xausa, Nov 26 2023

A new row can be generated by applying the morphism 1 -> 2, t -> {t-1,t+1} (for t > 1) to the previous row. - Paolo Xausa, Dec 08 2023

Examples

			Triangle begins:
  n=0:  1;
  n=1:  2;
  n=2:  1, 3;
  n=3:  2, 2, 4;
  n=4:  1, 3, 1, 3, 3, 5;
  n=5:  2, 2, 4, 2, 2, 4, 2, 4, 4, 6;
  n=6:  1, 3, 1, 3, 3, 5, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7;
  ...
The binary tree starts with root 1 in row n = 0. In row n = 2, the parent node 2 has the first left child since 2 - 1 > 0.
The tree begins:
row
[n]
[0]                   1
                       \
[1]            _________2_________
              /                   \
[2]          1                _____3_____
              \              /           \
[3]          __2__        __2__         __4__
            /     \      /     \       /     \
[4]        1       3    1       3     3       5
            \     / \    \     / \   / \     / \
[5]          2   2   4    2   2   4 2   4   4   6
.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..13494 (rows 0..15 of the triangle, flattened).

Crossrefs

Cf. A001405 (row lengths), A000079 (row sums).

Cf. A000108, A007001, A053121, A173258, A367508, A367951, A367953.

Programs

Mathematica

SubstitutionSystem[{1->{2},t_/;t>1:>{t-1,t+1}},{1},8] (* Paolo Xausa, Dec 23 2023 *)

Python

def A363718_rowlist(root,row):
    A = [[root]]
    for i in range(0,row):
        A.append([])
        for j in range(0,len(A[i])):
            if A[i][j] != 1:
                A[i+1].append(A[i][j]-1)
            A[i+1].append(A[i][j]+1)
    return(A)
A363718_rowlist(1, 8)