A363718 -id:A363718 - cp's OEIS frontend

A173258 Number of compositions of n where differences between neighboring parts are in {-1,1}.

1, 1, 1, 3, 2, 4, 5, 5, 7, 10, 9, 14, 16, 19, 24, 31, 35, 45, 55, 66, 84, 104, 124, 156, 192, 236, 292, 363, 444, 551, 681, 839, 1040, 1287, 1586, 1967, 2430, 3001, 3717, 4597, 5683, 7034, 8697, 10758, 13312, 16469, 20369, 25204, 31180, 38574, 47726, 59047

Offset: 0

Alois P. Heinz, Jul 08 2012

nonn

			a(3) = 3: [3], [2,1], [1,2].
a(4) = 2: [4], [1,2,1].
a(5) = 4: [5], [3,2], [2,3], [2,1,2].
a(6) = 5: [6], [3,2,1], [2,1,2,1], [1,2,3], [1,2,1,2].

Alois P. Heinz, Table of n, a(n) for n = 0..5000
John Tyler Rascoe, Illustration of n = 1..16

Column k=1 of A214247, A214249.
Row sums of A309938, A364039.
Cf. A227310, A291904, A291905, A343795, A362500, A363718, A364529.

b:= proc(n, i) option remember;
      `if`(n<1 or i<1, 0, `if`(n=i, 1, add(b(n-i, i+j), j=[-1, 1])))
    end:
a:= n-> `if`(n=0, 1, add(b(n, j), j=1..n)):
seq(a(n), n=0..70);

b[n_, i_] := b[n, i] = If[n < 1 || i < 1, 0, If[n == i, 1, Sum[b[n - i, i + j], {j, {-1, 1}}]]]; a[n_] := If[n == 0, 1, Sum[b[n, j], {j, 1, n}]]; Table[a[n], {n, 0, 70}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

step(R,n)={matrix(n, n, i, j, if(i>j, if(j>1, R[i-j, j-1]) + if(j+1<=n, R[i-j, j+1])) )}
a(n)={my(R=matid(n), t=(n==0), m=0); while(R, m++; t+=vecsum(R[n,]); R=step(R,n)); t} \\ Andrew Howroyd, Aug 23 2019

a(n) ~ c * d^n, where d=1.23729141259673487395949649334678514763130846902468..., c=1.134796087242490181499736234755111281606636700030106.... - Vaclav Kotesovec, May 01 2014

G.f.: 1 + Sum_{k>0} G(x,k) where G(x,k) = x^k*(1 + G(x,k+1) + G(x,k-1)) for k > 0 and G(x,0) = 0. - John Tyler Rascoe, Sep 16 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

A365968 Irregular triangle read by rows: T(n,k) (0 <= n, 0 <= k < 2^n). An infinite binary tree with root node 0 in row n = 0. Each node then has left child (2j) - k - 1 and right child (2j) - k + 1, where j and k are the values of the parent and grandparent nodes respectively.

Original entry on oeis.org

0, -1, 1, -3, -1, 1, 3, -6, -4, -2, 0, 0, 2, 4, 6, -10, -8, -6, -4, -4, -2, 0, 2, -2, 0, 2, 4, 4, 6, 8, 10, -15, -13, -11, -9, -9, -7, -5, -3, -7, -5, -3, -1, -1, 1, 3, 5, -5, -3, -1, 1, 1, 3, 5, 7, 3, 5, 7, 9, 9, 11, 13, 15, -21, -19, -17, -15, -15, -13, -11, -9

Offset: 0

John Tyler Rascoe, Sep 23 2023

For n in A014601 row n will contain all even numbers from 0 to A000217(n).

For n in A042963 row n will contain all odd numbers from 1 to A000217(n).

			Triangle begins:
        k=0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
  n=0:    0;
  n=1:   -1,  1;
  n=2:   -3, -1,  1,  3;
  n=3:   -6, -4, -2,  0,  0,  2,  4,  6;
  n=4:  -10, -8, -6, -4, -4, -2,  0,  2, -2,  0,  2,  4,  4,  6,  8, 10;
  ...
The binary tree starts with root 0 in row n = 0. For rows n < 2, k = 0.
In row n = 3, the parent node -3 has left child -6 = 2*(-3) - (-1) - 1.
The tree begins:
row
[n]
[0]                   ______0______
                     /             \
[1]              __-1__           __1__
                /      \         /     \
[2]           -3       -1       1       3
              / \      / \     / \     / \
[3]         -6  -4   -2   0   0   2   4   6
.

John Tyler Rascoe, Rows n = 0..12, flattened

Cf. A004718, A274575, A360173, A363718.

T(n,k) = sum(i=0,n-1, if(bittest(k,i), i+1, -(i+1))); \\ Kevin Ryde, Nov 14 2023

def A365968(n, k):
    b, x = bin(k)[2:].zfill(n), 0
    for i in range(0, n):
        x += (-1)**(int(b[n-(i+1)])+1)*(i+1)
    return(x) # John Tyler Rascoe, Nov 12 2023

T(n,k) = - Sum_{i=0..n-1} (i+1)*(-1)^b[i] where the binary expansion of k is k = Sum_{i=0..n-1} b[i]*2^i. - Kevin Ryde, Nov 14 2023

A367951 Fixed point of the morphism 1 -> {1,3}, t -> {t-2,t,t,t+2} (for t > 1), starting from {1}.

Original entry on oeis.org

1, 3, 1, 3, 3, 5, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7, 1, 3, 1, 3, 3, 5, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7, 1, 3, 3, 5, 3, 5, 5, 7, 3, 5, 5, 7, 5, 7, 7, 9, 1, 3, 1, 3, 3, 5, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7

Offset: 1

Paolo Xausa, Dec 05 2023

nonn

The first binomial(2*k,k) = A000984(k) terms (k >= 1) are the row lengths of the Christmas tree pattern (A367508) of order 2*k. See A367953 for the morphism that generates row lengths for odd orders.

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, exercise 76, pp. 479 and 800.

Paolo Xausa, Table of n, a(n) for n = 1..12870 (first 8 iterations).

Cf. A000984, A363718, A367508, A367953.

Nest[Flatten[ReplaceAll[#, {1->{1, 3}, t_/;t>1:>{t-2, t, t, t+2}}]]&, {1}, 5]

from itertools import islice
def A367951_gen(): # generator of terms
    a, l = [1], 0
    while True:
        yield from a[l:]
        c = sum(([1, 3] if d==1 else [d-2,d,d,d+2] for d in a), start=[])
        l, a = len(a), c
A367951_list = list(islice(A367951_gen(),30)) # Chai Wah Wu, Dec 26 2023

A367953 Fixed point of the morphism 2 -> {2,2,4}, t -> {t-2,t,t,t+2} (for t > 2), starting from {2}.

Original entry on oeis.org

2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 4, 4, 6, 2, 4, 4, 6, 4, 6, 6, 8, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 4, 4, 6, 2, 4, 4, 6, 4, 6, 6, 8, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 4, 4, 6, 2, 4, 4

Offset: 1

Paolo Xausa, Dec 05 2023

nonn

The first binomial(2*k+1,k+1) = A001700(k) terms (k >= 0) are the row lengths of the Christmas tree pattern (A367508) of order 2*k+1. See A367951 for the morphism that generates row lengths for even orders.

Paolo Xausa, Table of n, a(n) for n = 1..24310 (first 8 iterations).

Cf. A001700, A363718, A367508, A367951.

Nest[Flatten[ReplaceAll[#,{2->{2,2,4},t_/;t>2:>{t-2,t,t,t+2}}]]&,{2},5]

from itertools import islice
def A367953_gen(): # generator of terms
    a, l = [2], 0
    while True:
        yield from a[l:]
        c = sum(([2,2,4] if d==2 else [d-2,d,d,d+2] for d in a), start=[])
        l, a = len(a), c
A367953_list = list(islice(A367953_gen(),30)) # Chai Wah Wu, Dec 26 2023

A368464 Number of odd terms in each row of the iterates of the Christmas tree pattern map (A367508).

Original entry on oeis.org

1, 0, 2, 1, 0, 3, 0, 2, 0, 2, 0, 4, 1, 0, 3, 1, 0, 3, 0, 3, 0, 5, 0, 2, 0, 2, 0, 4, 0, 2, 0, 2, 0, 4, 0, 2, 0, 4, 0, 4, 0, 6, 1, 0, 3, 1, 0, 3, 0, 3, 0, 5, 1, 0, 3, 1, 0, 3, 0, 3, 0, 5, 1, 0, 3, 0, 3, 0, 5, 0, 3, 0, 5, 0, 5, 0, 7, 0, 2, 0, 2, 0, 4, 0, 2, 0, 2, 0

Offset: 1

Paolo Xausa, Dec 25 2023

nonn

See A367508 for the description of the Christmas tree patterns, references and links.

			The first 4 tree pattern orders are shown below (left), with the corresponding number of odd terms on the right.
.
Order 1:                        |
              0  1              |  1
                                |
Order 2:                        |
               10               |  0
           00  01  11           |  2
                                |
Order 3:                        |
            100  101            |  1
            010  110            |  0
       000  001  011  111       |  3
                                |
Order 4:                        |
              1010              |  0
        1000  1001  1011        |  2
              1100              |  0
        0100  0101  1101        |  2
        0010  0110  1110        |  0
  0000  0001  0011  0111  1111  |  4
.
Apparently, removing the 0 terms from the order i pattern (for i >= 2), gives the row lengths of the order i-1 pattern (cf. A363718).

Paolo Xausa, Table of n, a(n) for n = 1..13494 (first 15 orders).

Cf. A363718, A367508, A368463, A368465.

With[{imax=8},Map[Total,Map[Mod[FromDigits[#],2]&,NestList[Map[Delete[{If[Length[#]>1,Map[#<>"0"&,Rest[#]],Nothing],Join[{#[[1]]<>"0"},Map[#<>"1"&,#]]},0]&],{{"0","1"}},imax-1],{3}],{2}]] (* Generates terms up to order 8 *)

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 sum(1 for b in r if b[-1] == '1')
        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(), 88))) # Michael S. Branicky, Dec 25 2023

A368399 Irregular triangle read by rows: row n lists the indices of rows of the Christmas tree pattern (A367508) of order n, sorted by row length and, in case of ties, by row index.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 3, 2, 4, 5, 6, 1, 2, 4, 5, 7, 3, 6, 8, 9, 10, 1, 3, 7, 9, 13, 2, 4, 5, 8, 10, 11, 14, 15, 17, 6, 12, 16, 18, 19, 20, 1, 2, 4, 5, 7, 11, 12, 14, 15, 17, 21, 22, 24, 28, 3, 6, 8, 9, 13, 16, 18, 19, 23, 25, 26, 29, 30, 32, 10, 20, 27, 31, 33, 34, 35

Offset: 1

Paolo Xausa, Dec 23 2023

Row n is a permutation of the integers in the interval [1, binomial(n,floor(n/2))].

See A367508 for the description of the Christmas tree patterns, references and links.

			Triangle begins (vertical bars separate indices of rows having different lengths):
.
  [1]  1;
  [2]  1| 2;
  [3]  1  2| 3;
  [4]  1  3| 2  4  5| 6;
  [5]  1  2  4  5  7| 3  6  8  9|10;
  [6]  1  3  7  9 13| 2  4  5  8 10 11 14 15 17| 6 12 16 18 19|20;
  ...
For example, the order 4 of the Christmas tree pattern is the following:
.
            1010             Row 1 length = 1
       1000 1001 1011        Row 2 length = 3
            1100             Row 3 length = 1
       0100 0101 1101        Row 4 length = 3
       0010 0110 1110        Row 5 length = 3
  0000 0001 0011 0111 1111   Row 6 length = 5
.
and ordering the rows by length (and then by row index) gives 1, 3, 2, 4, 5, 6.

Paolo Xausa, Table of n, a(n) for n = 1..13494 (rows 1..15 of the triangle, flattened).

Cf. A001405, A363718 (row lengths), A367508, A368400.

With[{nmax=8},Map[Flatten[Values[PositionIndex[#]]]&,SubstitutionSystem[{1->{2},t_/;t>1:>{t-1,t+1}},{2},nmax-1]]]

cp's OEIS Frontend

A173258 Number of compositions of n where differences between neighboring parts are in {-1,1}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

A365968 Irregular triangle read by rows: T(n,k) (0 <= n, 0 <= k < 2^n). An infinite binary tree with root node 0 in row n = 0. Each node then has left child (2*j) - k - 1 and right child (2*j) - k + 1, where j and k are the values of the parent and grandparent nodes respectively.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A367951 Fixed point of the morphism 1 -> {1,3}, t -> {t-2,t,t,t+2} (for t > 1), starting from {1}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

A367953 Fixed point of the morphism 2 -> {2,2,4}, t -> {t-2,t,t,t+2} (for t > 2), starting from {2}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

A368464 Number of odd terms in each row of the iterates of the Christmas tree pattern map (A367508).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A368399 Irregular triangle read by rows: row n lists the indices of rows of the Christmas tree pattern (A367508) of order n, sorted by row length and, in case of ties, by row index.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A365968 Irregular triangle read by rows: T(n,k) (0 <= n, 0 <= k < 2^n). An infinite binary tree with root node 0 in row n = 0. Each node then has left child (2j) - k - 1 and right child (2j) - k + 1, where j and k are the values of the parent and grandparent nodes respectively.