A368427 -id:A368427 - cp's OEIS frontend

A368428 Inverse permutation to A368427.

1, 2, 3, 5, 6, 4, 7, 12, 13, 10, 14, 8, 9, 11, 15, 27, 28, 24, 29, 21, 22, 25, 30, 17, 18, 16, 19, 20, 23, 26, 31, 58, 59, 54, 60, 50, 51, 55, 61, 44, 45, 42, 46, 48, 52, 56, 62, 36, 37, 34, 38, 32, 33, 35, 39, 40, 41, 43, 47, 49, 53, 57, 63, 121, 122, 116

Offset: 1

Rémy Sigrist, Dec 24 2023

			A368427(67) = 107, so a(107) = 67.

Rémy Sigrist, Table of n, a(n) for n = 1..8191
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

Cf. A368427.

PARI
```
See Links section.
```

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 A368427gen(): # generator of terms of A368427
    R = [["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))]))
def agen(): # generator of terms
    adict, n = dict(), 1
    for i, k in enumerate(A368427gen(), 1):
        if k not in adict:
            adict[k] = i
        while n in adict: yield adict[n]; n += 1
print(list(islice(agen(), 66))) # Michael S. Branicky, Dec 24 2023

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

Original entry on oeis.org

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

cp's OEIS Frontend

A368428 Inverse permutation to A368427.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

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