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).

%I A367508 #72 Dec 30 2023 14:39:48
%S A367508 0,1,10,0,1,11,100,101,10,110,0,1,11,111,1010,1000,1001,1011,1100,100,
%T A367508 101,1101,10,110,1110,0,1,11,111,1111,10100,10101,10010,10110,10000,
%U A367508 10001,10011,10111,11000,11001,1010,11010,1000,1001,1011,11011,1100,11100,100,101,1101,11101
%N A367508 Iterates of the Christmas tree pattern map, read by rows, with leading zeros removed and interpreted as decimal numbers (see description in Comments).
%C A367508 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 A367508 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 A367508 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 A367508 Chain lengths within an order-i pattern are given by row i of A363718.
%C A367508 For more properties, including connections to matching parentheses, trees, and Catalan numbers, refer to Knuth (2002 and 2011).
%D A367508 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 A367508 Paolo Xausa, <a href="/A367508/b367508.txt">Table of n, a(n) for n = 1..8190</a> (first 12 orders, flattened).
%H A367508 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 A367508 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 A367508 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 A367508 Donald E. Knuth, <a href="https://www.youtube.com/watch?v=zyWe3lcfaYw">Stanford Lecture: Chains of Subsets</a>, YouTube video, 2002.
%H A367508 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 A367508 Paolo Xausa, <a href="/A367508/a367508_1.pdf">Illustration of first 8 orders</a>.
%e A367508 The first 4 tree pattern orders are shown below.
%e A367508 .
%e A367508 Order 1:
%e A367508               0  1
%e A367508 .
%e A367508 Order 2:
%e A367508                10
%e A367508            00  01  11
%e A367508 .
%e A367508 Order 3:
%e A367508             100  101
%e A367508             010  110
%e A367508        000  001  011  111
%e A367508 .
%e A367508 Order 4:
%e A367508               1010
%e A367508         1000  1001  1011
%e A367508               1100
%e A367508         0100  0101  1101
%e A367508         0010  0110  1110
%e A367508   0000  0001  0011  0111  1111
%e A367508 .
%t A367508 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 A367508 (Python)
%o A367508 from itertools import islice
%o A367508 from functools import reduce
%o A367508 def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
%o A367508 def agen():  # generator of terms
%o A367508     R = [["0", "1"]]
%o A367508     while R:
%o A367508         r = R.pop(0)
%o A367508         yield from map(lambda b: int(b), r)
%o A367508         if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
%o A367508         R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
%o A367508 print(list(islice(agen(), 62))) # _Michael S. Branicky_, Nov 23 2023
%o A367508 (Julia)
%o A367508 function A367508(rows::Int)
%o A367508     R = [["0", "1"]]
%o A367508     seq = Int[]
%o A367508     op = (r, n) -> [r[k] * n for k in 2:length(r)]
%o A367508     for _ in 1:rows
%o A367508         r = popfirst!(R)
%o A367508         append!(seq, map(b -> parse(Int, b), r))
%o A367508         length(r) > 1 && push!(R, op(r, "0"))
%o A367508         push!(R, [[r[1] * "0", r[1] * "1"]; op(r, "1")])
%o A367508     end
%o A367508 return seq end
%o A367508 println(A367508(20))  # _Peter Luschny_, Nov 28 2023
%Y A367508 Cf. A000108, A001405, A363718.
%Y A367508 Cf. A367555, A367562, A367951, A367953, A368175, A368398, A368399, A368400.
%Y A367508 Cf. A368427, A368463, A368464, A368465.
%K A367508 nonn,tabf,nice,base
%O A367508 1,3
%A A367508 _Paolo Xausa_, Nov 21 2023