A367951 -id:A367951 - cp's OEIS frontend

A367508 Iterates of the Christmas tree pattern map, read by rows, with leading zeros removed and interpreted as decimal numbers (see description in Comments).

0, 1, 10, 0, 1, 11, 100, 101, 10, 110, 0, 1, 11, 111, 1010, 1000, 1001, 1011, 1100, 100, 101, 1101, 10, 110, 1110, 0, 1, 11, 111, 1111, 10100, 10101, 10010, 10110, 10000, 10001, 10011, 10111, 11000, 11001, 1010, 11010, 1000, 1001, 1011, 11011, 1100, 11100, 100, 101, 1101, 11101

Offset: 1

Paolo Xausa, Nov 21 2023

These patterns are described by Knuth (2002 and 2011), who calls them "Christmas tree patterns" because, when arranged appropriately (i.e., with their columns center-aligned), they resemble a Christmas tree (see Example), and also because they were presented in Knuth's ninth annual "Christmas Tree Lecture" at Stanford University (although in that lecture they were shown "upside-down").
The idea is to take all of the subsets of i elements (e_1...e_i) and arrange them into disjoint chains of maximal length, each subset in a chain being a bit string of length i, where the b-th bit is 1 if the element e_b is in the subset, 0 otherwise. Each subset must contain one element less than the next within a chain. It turns out such an arrangement has binomial(i, floor(i/2)) = A001405(i) rows (chains) and i+1 columns; when the columns are center-aligned, all of the subsets in a given column contain the same number of elements.
To iteratively generate these patterns, we can start with the chain "0 1", which is the pattern of order 1. Subsequent iterations generate patterns of order 2, 3, ..., i. At each iteration, and for each chain c of the previous order pattern, we generate one or two new chains, as follows. If chain c has just one subset, we generate one new chain: (c_1)0, (c_1)1; if chain c has more than one subset, we generate two new chains: (c_2)0, ..., (c_s)0 and (c_1)0, (c_1)1, ..., (c_s)1, where s is the number of subsets of chain c and (c_k)b is the k-th subset of chain c joined with b. The new chains thus generated form the following order pattern.
Chain lengths within an order-i pattern are given by row i of A363718.
For more properties, including connections to matching parentheses, trees, and Catalan numbers, refer to Knuth (2002 and 2011).

			The first 4 tree pattern orders are shown below.
.
Order 1:
              0  1
.
Order 2:
               10
           00  01  11
.
Order 3:
            100  101
            010  110
       000  001  011  111
.
Order 4:
              1010
        1000  1001  1011
              1100
        0100  0101  1101
        0010  0110  1110
  0000  0001  0011  0111  1111
.

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 457-460.

Paolo Xausa, Table of n, a(n) for n = 1..8190 (first 12 orders, flattened).
N. de Brujin, C. Tengbergen and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskunde 23, 1951, pp. 191-193.
Curtis Greene and Daniel J. Kleitman, Strong versions of Sperner's theorem, Journal of Combinatorial Theory, Series A, Volume 20, Issue 1, 1976, pp. 80-88.
G. Hansel, Sur le nombre des fonctions booléennes monotones de variables, Comptes Rendus Acad. Sci. 262, 1966, pp. 1088-1090.
Donald E. Knuth, Stanford Lecture: Chains of Subsets, YouTube video, 2002.
E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math Z 27, 1928, pp. 544-548.
Paolo Xausa, Illustration of first 8 orders.

Cf. A000108, A001405, A363718.
Cf. A367555, A367562, A367951, A367953, A368175, A368398, A368399, A368400.
Cf. A368427, A368463, A368464, A368465.

function A367508(rows::Int)
    R = [["0", "1"]]
    seq = Int[]
    op = (r, n) -> [r[k] * n for k in 2:length(r)]
    for _ in 1:rows
        r = popfirst!(R)
        append!(seq, map(b -> parse(Int, b), r))
        length(r) > 1 && push!(R, op(r, "0"))
        push!(R, [[r[1] * "0", r[1] * "1"]; op(r, "1")])
    end
return seq end
println(A367508(20))  # Peter Luschny, Nov 28 2023

With[{imax=6},Map[FromDigits,NestList[Map[Delete[{If[Length[#]>1,Map[#<>"0"&,Rest[#]],Nothing],Join[{#[[1]]<>"0"},Map[#<>"1"&,#]]},0]&],{{"0","1"}},imax-1],{3}]] (* Generates terms up to order 6 *)

from itertools import islice
from functools import reduce
def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
def agen():  # generator of terms
    R = [["0", "1"]]
    while R:
        r = R.pop(0)
        yield from map(lambda b: int(b), r)
        if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
        R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
print(list(islice(agen(), 62))) # Michael S. Branicky, Nov 23 2023

A367562 Iterates of the Christmas tree pattern map (A367508), read by rows and converted to decimal.

Original entry on oeis.org

0, 1, 2, 0, 1, 3, 4, 5, 2, 6, 0, 1, 3, 7, 10, 8, 9, 11, 12, 4, 5, 13, 2, 6, 14, 0, 1, 3, 7, 15, 20, 21, 18, 22, 16, 17, 19, 23, 24, 25, 10, 26, 8, 9, 11, 27, 12, 28, 4, 5, 13, 29, 2, 6, 14, 30, 0, 1, 3, 7, 15, 31, 42, 40, 41, 43, 44, 36, 37, 45, 34, 38, 46, 32, 33, 35, 39, 47

Offset: 1

Paolo Xausa, Nov 23 2023

See A367508 for the description of the Christmas tree patterns, references and links.

			The first 4 tree pattern orders are shown below (on the right their elements are converted to decimal: the present sequence is obtained by reading the right half of the diagram left to right, top to bottom).
The sequence of the terms in chains of length 1 (marked with asterisks) coincides with the positive terms of A014486.
.
Order 1:                        |
              0  1              |      0  1
                                |
Order 2:                        |
               10               |        2*
           00  01  11           |     0  1  3
                                |
Order 3:                        |
            100  101            |      4  5
            010  110            |      2  6
       000  001  011  111       |   0  1  3  7
                                |
Order 4:                        |
              1010              |       10*
        1000  1001  1011        |     8  9 11
              1100              |       12*
        0100  0101  1101        |     4  5 13
        0010  0110  1110        |     2  6 14
  0000  0001  0011  0111  1111  |  0  1  3  7 15
.

Paolo Xausa, Table of n, a(n) for n = 1..8190 (first 12 orders, flattened).

Cf. A014486, A367508, A367555, A367726, A367951, A367953, A368400, A368431.

With[{imax=6},Map[FromDigits[#,2]&,NestList[Map[Delete[{If[Length[#]>1,Map[#<>"0"&,Rest[#]],Nothing],Join[{#[[1]]<>"0"},Map[#<>"1"&,#]]},0]&],{{"0","1"}},imax-1],{3}]] (* Generates terms up to order 6 *)

from itertools import islice
from functools import reduce
def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
def agen():  # generator of terms
    R = [["0", "1"]]
    while R:
        r = R.pop(0)
        yield from map(lambda b: int(b, 2), r)
        if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
        R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
print(list(islice(agen(), 77))) # Michael S. Branicky, Nov 23 2023

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.

Original entry on oeis.org

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

John Tyler Rascoe, Jun 17 2023

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

			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
.

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

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

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

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

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)

A367953 Fixed point of the morphism 2 -> {2,2,4}, t -> {t-2,t,t,t+2} (for t > 2), starting from {2}.

Original entry on oeis.org

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, 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, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 4, 4, 6, 2, 4, 4

Offset: 1

Paolo Xausa, Dec 05 2023

nonn

The first binomial(2*k+1,k+1) = A001700(k) terms (k >= 0) are the row lengths of the Christmas tree pattern (A367508) of order 2*k+1. See A367951 for the morphism that generates row lengths for even orders.

Paolo Xausa, Table of n, a(n) for n = 1..24310 (first 8 iterations).

Cf. A001700, A363718, A367508, A367951.

Nest[Flatten[ReplaceAll[#,{2->{2,2,4},t_/;t>2:>{t-2,t,t,t+2}}]]&,{2},5]

from itertools import islice
def A367953_gen(): # generator of terms
    a, l = [2], 0
    while True:
        yield from a[l:]
        c = sum(([2,2,4] if d==2 else [d-2,d,d,d+2] for d in a), start=[])
        l, a = len(a), c
A367953_list = list(islice(A367953_gen(),30)) # Chai Wah Wu, Dec 26 2023

cp's OEIS Frontend

A367508 Iterates of the Christmas tree pattern map, read by rows, with leading zeros removed and interpreted as decimal numbers (see description in Comments).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

Mathematica

Python

A367562 Iterates of the Christmas tree pattern map (A367508), read by rows and converted to decimal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A367953 Fixed point of the morphism 2 -> {2,2,4}, t -> {t-2,t,t,t+2} (for t > 2), starting from {2}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python