|
|
A367508
|
|
Iterates of the Christmas tree pattern map, read by rows, with leading zeros removed and interpreted as decimal numbers (see description in Comments).
|
|
18
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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))]))
(Julia)
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf,nice,base
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|