OFFSET
1,3
COMMENTS
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).
REFERENCES
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.
LINKS
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.
EXAMPLE
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
.
MATHEMATICA
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 *)
PROG
(Python)
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
(Julia)
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
CROSSREFS
KEYWORD
nonn,tabf,nice,base
AUTHOR
Paolo Xausa, Nov 21 2023
STATUS
approved