|
%I #72 Dec 30 2023 14:39:48
%S 0,1,10,0,1,11,100,101,10,110,0,1,11,111,1010,1000,1001,1011,1100,100,
%T 101,1101,10,110,1110,0,1,11,111,1111,10100,10101,10010,10110,10000,
%U 10001,10011,10111,11000,11001,1010,11010,1000,1001,1011,11011,1100,11100,100,101,1101,11101
%N Iterates of the Christmas tree pattern map, read by rows, with leading zeros removed and interpreted as decimal numbers (see description in Comments).
%C 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").
%C 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.
%C 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.
%C Chain lengths within an order-i pattern are given by row i of A363718.
%C For more properties, including connections to matching parentheses, trees, and Catalan numbers, refer to Knuth (2002 and 2011).
%D 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.
%H Paolo Xausa, <a href="/A367508/b367508.txt">Table of n, a(n) for n = 1..8190</a> (first 12 orders, flattened).
%H N. de Brujin, C. Tengbergen and D. Kruyswijk, <a href="https://pure.tue.nl/ws/portalfiles/portal/4373475/597494.pdf">On the set of divisors of a number</a>, Nieuw Arch. Wiskunde 23, 1951, pp. 191-193.
%H Curtis Greene and Daniel J. Kleitman, <a href="https://doi.org/10.1016/0097-3165(76)90079-0">Strong versions of Sperner's theorem</a>, Journal of Combinatorial Theory, Series A, Volume 20, Issue 1, 1976, pp. 80-88.
%H G. Hansel, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k6238594s/f120.item">Sur le nombre des fonctions booléennes monotones de variables</a>, Comptes Rendus Acad. Sci. 262, 1966, pp. 1088-1090.
%H Donald E. Knuth, <a href="https://www.youtube.com/watch?v=zyWe3lcfaYw">Stanford Lecture: Chains of Subsets</a>, YouTube video, 2002.
%H E. Sperner, <a href="https://doi.org/10.1007/BF01171114">Ein Satz über Untermengen einer endlichen Menge</a>, Math Z 27, 1928, pp. 544-548.
%H Paolo Xausa, <a href="/A367508/a367508_1.pdf">Illustration of first 8 orders</a>.
%e The first 4 tree pattern orders are shown below.
%e .
%e Order 1:
%e 0 1
%e .
%e Order 2:
%e 10
%e 00 01 11
%e .
%e Order 3:
%e 100 101
%e 010 110
%e 000 001 011 111
%e .
%e Order 4:
%e 1010
%e 1000 1001 1011
%e 1100
%e 0100 0101 1101
%e 0010 0110 1110
%e 0000 0001 0011 0111 1111
%e .
%t 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 *)
%o (Python)
%o from itertools import islice
%o from functools import reduce
%o def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
%o def agen(): # generator of terms
%o R = [["0", "1"]]
%o while R:
%o r = R.pop(0)
%o yield from map(lambda b: int(b), r)
%o if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
%o R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
%o print(list(islice(agen(), 62))) # _Michael S. Branicky_, Nov 23 2023
%o (Julia)
%o function A367508(rows::Int)
%o R = [["0", "1"]]
%o seq = Int[]
%o op = (r, n) -> [r[k] * n for k in 2:length(r)]
%o for _ in 1:rows
%o r = popfirst!(R)
%o append!(seq, map(b -> parse(Int, b), r))
%o length(r) > 1 && push!(R, op(r, "0"))
%o push!(R, [[r[1] * "0", r[1] * "1"]; op(r, "1")])
%o end
%o return seq end
%o println(A367508(20)) # _Peter Luschny_, Nov 28 2023
%Y Cf. A000108, A001405, A363718.
%Y Cf. A367555, A367562, A367951, A367953, A368175, A368398, A368399, A368400.
%Y Cf. A368427, A368463, A368464, A368465.
%K nonn,tabf,nice,base
%O 1,3
%A _Paolo Xausa_, Nov 21 2023
|
