A072643 -id:A072643 - cp's OEIS frontend

A126303 a(n) = number of nodes with odd distance to the root in the n-th plane general tree encoded by A014486(n). Both internal and terminal nodes (leaves) are counted.

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

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

			A014486(27) = 696 (1010111000 in binary), encodes the following general plane tree, where the root is marked with * and nodes with even or odd distance to root with 'e's and 'o's, respectively.
.......o
.......|
.......e
.......|
...o.o.o
....\|/.
.....*..
there are four nodes marked with 'o', thus a(27)=4.

a(n) = A072643(n)-A126305(n). Cf. A126304. Scheme-function A014486->parenthesization given in A014486.

A153250 Array A(x,y): A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ... formed by growing a bud (a single V-node) on the y-th leaf of the binary tree A014486(x).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 22 2008

Note: the leaf positions are indexed so that the rightmost one in the tree is leaf 0, etc., up to the leftmost one, which is the leaf with index A072643(x). In this manner, terms on each row stay in monotone order. Row n (starting from row 0) contains A072643(n)+1 nonzero terms and then an infinite number of zeros after that. A153249 gives only the nonzero terms. Can be used to compute "fleeing tree" sequences for Catalan bijections. See comments at A153246.

			Top left corner of array:
1,  0,  0,  0,  0, ...
2,  3,  0,  0,  0, ...
4,  5,  6,  0,  0, ...
6,  7,  8,  0,  0, ...
9,  10, 11, 14, 0, ...
11, 12, 13, 15, 0, ...
14, 15, 16, 19, 0, ...
By inserting a bud (\/) at leaf position 1 of binary tree A014486(2) (leaf positions numbered for clarification):
....1....0
.....\../
..2...\/
...\../
....\/
we obtain a binary tree:
.......
.\../..
..\/...
...\../
....\/
.\../
..\/
which is the 5th binary tree encoded by A014486. Thus A(2,1)=5.

A. Karttunen, Table of n, a(n) for n = 0..1274

Cf. A002262, A025581.

A213704 Catalan Unranking function U(size,rank) for totally balanced binary strings (converted to decimal). Each row 'size' of an array lists all A000108(size) such items in standard lexicographic order, followed by an infinite number of zeros.

Original entry on oeis.org

0, 0, 2, 0, 0, 10, 0, 0, 12, 42, 0, 0, 0, 44, 170, 0, 0, 0, 50, 172, 682, 0, 0, 0, 52, 178, 684, 2730, 0, 0, 0, 56, 180, 690, 2732, 10922, 0, 0, 0, 0, 184, 692, 2738, 10924, 43690, 0, 0, 0, 0, 202, 696, 2740, 10930, 43692, 174762, 0, 0, 0, 0, 204, 714, 2744, 10932, 43698, 174764, 699050, 0

Offset: 0

Antti Karttunen, Aug 10 2012

The Scheme-function CatalanUnrank has been adapted from Frank Ruskey's thesis. This gives essentially the same information as A014486 which can be obtained from this array by concatenating all A000108(s) nonzero terms from the beginning of each row s to one sequence.

See the comments and pictures at A014486 for more information.

Antti Karttunen, Rows n=0..54 of triangle, flattened
Antti Karttunen et al., Ranking and unranking functions, OEIS Wiki.
Frank Ruskey, Algorithmic Solution of Two Combinatorial Problems, Thesis, Department of Applied Physics and Information Science, University of Victoria, 1978.

The leftmost column: A020988. For all n>1, A014486(n) = A213704bi(A072643(n),(n - A014137(A072643(n)-1))). Cf. A009766, A215406, A153250.

(define (A213704 n) (A213704bi (A002262 n) (A025581 n)))
(define (A213704bi row col) (cond ((zero? row) 0) ((>= col (A000108 row)) 0) (else (CatalanUnrank row col))))
(define (CatalanUnrank size rank) (let loop ((a 0) (m (-1+ size)) (y size) (rank rank) (c (A009766tr (-1+ size) size))) (if (negative? m) a (if (>= rank c) (loop (1+ (* 2 a)) m (-1+ y) (- rank c) (A009766tr m (-1+ y))) (loop (* 2 a) (-1+ m) y rank (A009766tr (-1+ m) y))))))

A370219 Irregular triangle T(n,k) read by rows: row n lists run-length encoding d_k values (see comments) for the properly nested string of parentheses encoded by A063171(n).

Original entry on oeis.org

1, 1, 1, 0, 2, 1, 1, 1, 1, 0, 2, 0, 2, 1, 0, 1, 2, 0, 0, 3, 1, 1, 1, 1, 1, 1, 0, 2, 1, 0, 2, 1, 1, 0, 1, 2, 1, 0, 0, 3, 0, 2, 1, 1, 0, 2, 0, 2, 0, 1, 2, 1, 0, 1, 1, 2, 0, 1, 0, 3, 0, 0, 3, 1, 0, 0, 2, 2, 0, 0, 1, 3, 0, 0, 0, 4, 1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 1, 1, 0, 2, 1

Offset: 1

Paolo Xausa, Feb 12 2024

As explained by Knuth (2011), a string of properly nested parentheses of length 2*m (for m >= 1) can be run-length encoded as ()d_1()d_2 ... ()d_m, where d_k are nonnegative integers such that d_1 + d_2 + ... + d_k <= k for 1 <= k < m and d_1 + d_2 + ... + d_m = m.

			The following table lists d_k values for properly nested strings having lengths up to 8, along with z_k, p_k and c_k values from related combinatorial objects (see related sequences for more information). Cf. Knuth (2011), p. 442, Table 1.
.
      | Properly |          |         | A370220 | A370221 | A370222
      | Nested   | A063171  | d d d d | z z z z | p p p p | c c c c
    n | String   |   (n)    | 1 2 3 4 | 1 2 3 4 | 1 2 3 4 | 1 2 3 4
  ----+----------+----------+---------+---------+---------+---------
    1 | ()       | 10       | 1       | 1       | 1       | 0
    2 | ()()     | 1010     | 1 1     | 1 3     | 1 2     | 0 0
    3 | (())     | 1100     | 0 2     | 1 2     | 2 1     | 0 1
    4 | ()()()   | 101010   | 1 1 1   | 1 3 5   | 1 2 3   | 0 0 0
    5 | ()(())   | 101100   | 1 0 2   | 1 3 4   | 1 3 2   | 0 0 1
    6 | (())()   | 110010   | 0 2 1   | 1 2 5   | 2 1 3   | 0 1 0
    7 | (()())   | 110100   | 0 1 2   | 1 2 4   | 2 3 1   | 0 1 1
    8 | ((()))   | 111000   | 0 0 3   | 1 2 3   | 3 2 1   | 0 1 2
    9 | ()()()() | 10101010 | 1 1 1 1 | 1 3 5 7 | 1 2 3 4 | 0 0 0 0
   10 | ()()(()) | 10101100 | 1 1 0 2 | 1 3 5 6 | 1 2 4 3 | 0 0 0 1
   11 | ()(())() | 10110010 | 1 0 2 1 | 1 3 4 7 | 1 3 2 4 | 0 0 1 0
   12 | ()(()()) | 10110100 | 1 0 1 2 | 1 3 4 6 | 1 3 4 2 | 0 0 1 1
   13 | ()((())) | 10111000 | 1 0 0 3 | 1 3 4 5 | 1 4 3 2 | 0 0 1 2
   14 | (())()() | 11001010 | 0 2 1 1 | 1 2 5 7 | 2 1 3 4 | 0 1 0 0
   15 | (())(()) | 11001100 | 0 2 0 2 | 1 2 5 6 | 2 1 4 3 | 0 1 0 1
   16 | (()())() | 11010010 | 0 1 2 1 | 1 2 4 7 | 2 3 1 4 | 0 1 1 0
   17 | (()()()) | 11010100 | 0 1 1 2 | 1 2 4 6 | 2 3 4 1 | 0 1 1 1
   18 | (()(())) | 11011000 | 0 1 0 3 | 1 2 4 5 | 2 4 3 1 | 0 1 1 2
   19 | ((()))() | 11100010 | 0 0 3 1 | 1 2 3 7 | 3 2 1 4 | 0 1 2 0
   20 | ((())()) | 11100100 | 0 0 2 2 | 1 2 3 6 | 3 2 4 1 | 0 1 2 1
   21 | ((()())) | 11101000 | 0 0 1 3 | 1 2 3 5 | 3 4 2 1 | 0 1 2 2
   22 | (((()))) | 11110000 | 0 0 0 4 | 1 2 3 4 | 4 3 2 1 | 0 1 2 3

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 440-444.

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

Cf. A000108, A063171, A072643 (row lengths and row sums).

Cf. A370220, A370221, A370222.

zlist[m_] := With[{r = 2*Range[2, m]}, Reverse[Map[Join[{1}, #] &, Select[Subsets[Range[2, 2*m-1], {m-1}], Min[r-#] > 0 &]]]];
dlist[m_] := Map[Append[#, m - Total[#]] &, Map[Differences, zlist[m]] - 1];
Array[Delete[dlist[#], 0] &, 5]
(* 2nd program: uses Algorithm Z from Knuth's TAOCP section 7.2.1.6, exercise 2 *)
zlist[m_] := Block[{z = 2*Range[m] - 1, j},
    Reap[
    While[True,
        Sow[z];
        If[z[[m-1]] < z[[m]] - 1,
            z[[m]]--,
            j = m - 1; z[[m]] = 2*m - 1;
            While[j > 1 && z[[j-1]] == z[[j]] - 1, z[[j]] = 2*j - 1; j--];
            If[j == 1,Break[]];
            z[[j]]--]
    ]][[2]][[1]]];
dlist[m_] := Map[Append[#, m - Total[#]] &, Map[Differences, zlist[m]] - 1];
Join[{{1}}, Array[Delete[dlist[#], 0] &, 4, 2]] (* Paolo Xausa, Mar 25 2024 *)

T(n,k) = A370220(n,k+1) - A370220(n,k) - 1, for 1 <= k < A072643(n).

A126305 a(n) = number of nodes with even distance to the root in the n-th plane general tree encoded by A014486(n). The root node itself is also included.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 3, 2, 1, 2, 2, 3, 2, 2, 3, 3, 4, 3, 2, 3, 2, 3, 1, 2, 2, 3, 2, 2, 3, 3, 4, 3, 2, 3, 2, 3, 2, 3, 3, 4, 3, 3, 4, 4, 5, 4, 3, 4, 3, 4, 2, 3, 3, 4, 3, 2, 3, 2, 3, 3, 4, 3, 4, 3, 1, 2, 2, 3, 2, 2, 3, 3, 4, 3, 2, 3, 2, 3, 2, 3, 3, 4, 3, 3, 4, 4, 5, 4, 3, 4, 3, 4, 2, 3, 3, 4, 3, 2, 3, 2, 3

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

a(n) = A126304(n)+1 = A072643(n)-A126303(n). a(n) = A057514(A125982(n)) for all n >=1.

A130918 Simple self-inverse permutation of natural numbers: List each block of A000108(n) numbers from A014137(n-1) to A014138(n-1) in reverse order.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 11 2007

nonn

In principle this involution is the signature permutation of yet another Catalan automorphism. However, the question remains what is the most "natural" way to create such an automorphism acting e.g. on S-expressions (i.e. rooted plane binary trees), which would produce this sequence as its signature permutation.

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Signature permutations of Catalan bijections
Index entries for signature-permutations of Catalan automorphisms

Inverse: A130918. Cf. A054429, A057163. The number of cycles and the number of fixed points in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A130380 and A036987.

(define (A130918 n) (if (zero? n) n (- (A014138 (- (A072643 n) 1)) (A082853 n))))

a(0)=0, a(n) = A014138(A072643(n)-1) - A082853(n).

A154475 Number of opening (equally: closing) brackets in each term of Wolfram's Symbolic Rewriting system A154473-A154474.

Original entry on oeis.org

5, 7, 7, 8, 8, 14, 19, 24, 28, 31, 36, 42, 45, 47, 49, 50, 50, 50, 51, 51, 51, 54, 55, 55, 55, 56, 56, 56, 58, 60, 61, 61, 61, 62, 62, 62, 65, 66, 66, 66, 67, 67, 67, 70, 72, 74, 75, 75, 75, 76, 76, 76, 79, 80, 80, 80, 81, 81, 81, 83, 85, 86, 86, 86, 87, 87, 87, 92, 93, 93

Offset: 0

Antti Karttunen, Jan 11 2009

nonn

2*a(n) gives the number of bits in A154474(n).

			The iteration starts from the initial term e[e[e][e]][e][e], which contains 5 ['s (and also 5 ]'s), thus a(0)=5.

A. Karttunen, Table of n, a(n) for n = 0..100
S. Wolfram, A New Kind of Science, Wolfram Media Inc., (2002), p. 102, p. 103 and pages 104, 896-898.

a(n) = A029837(1+A154473(n))/2. a(n) = A154476(n)-1.

a(n) = A072643(A154472(n)).

A154476 Number of e's in each iteration of Wolfram's e[x_][y_] -> x[x[y]] symbolic rewriting system, starting from the initial state e[e[e][e]][e][e].

Original entry on oeis.org

6, 8, 8, 9, 9, 15, 20, 25, 29, 32, 37, 43, 46, 48, 50, 51, 51, 51, 52, 52, 52, 55, 56, 56, 56, 57, 57, 57, 59, 61, 62, 62, 62, 63, 63, 63, 66, 67, 67, 67, 68, 68, 68, 71, 73, 75, 76, 76, 76, 77, 77, 77, 80, 81, 81, 81, 82, 82, 82, 84, 86, 87, 87, 87, 88, 88, 88, 93, 94, 94

Offset: 0

Antti Karttunen, Jan 11 2009

nonn

			The iteration starts from the initial term e[e[e][e]][e][e], which contains 6 e's, thus a(0)=6.

A. Karttunen, Table of n, a(n) for n = 0..100
S. Wolfram, A New Kind of Science, Wolfram Media Inc., (2002), p. 102, p. 103 and pages 104, 896-898.

a(n) = A154475(n)+1.

a(n) = A072643(A154471(n)) - A072643(A154472(n)).

A371409 Irregular triangle T(n,k) read by rows: row n lists the positions of right parentheses in the properly nested string of parentheses encoded by A063171(n).

Original entry on oeis.org

2, 2, 4, 3, 4, 2, 4, 6, 2, 5, 6, 3, 4, 6, 3, 5, 6, 4, 5, 6, 2, 4, 6, 8, 2, 4, 7, 8, 2, 5, 6, 8, 2, 5, 7, 8, 2, 6, 7, 8, 3, 4, 6, 8, 3, 4, 7, 8, 3, 5, 6, 8, 3, 5, 7, 8, 3, 6, 7, 8, 4, 5, 6, 8, 4, 5, 7, 8, 4, 6, 7, 8, 5, 6, 7, 8, 2, 4, 6, 8, 10, 2, 4, 6, 9, 10, 2, 4, 7, 8, 10

Offset: 1

Paolo Xausa, Mar 22 2024

See A370220 for the positions of left parentheses.

			The following table lists the positions of right parentheses for properly nested strings having lengths up to 8, along with the positions of left parentheses.
.
      | Properly |          | Pos. of right | Pos. of left
      | Nested   | A063171  | parentheses   | parentheses
    n | String   |   (n)    | (this seq.)   | (A370220)
  ----+----------+----------+---------------+---------------
    1 | ()       | 10       | 2             | 1
    2 | ()()     | 1010     | 2 4           | 1 3
    3 | (())     | 1100     | 3 4           | 1 2
    4 | ()()()   | 101010   | 2 4 6         | 1 3 5
    5 | ()(())   | 101100   | 2 5 6         | 1 3 4
    6 | (())()   | 110010   | 3 4 6         | 1 2 5
    7 | (()())   | 110100   | 3 5 6         | 1 2 4
    8 | ((()))   | 111000   | 4 5 6         | 1 2 3
    9 | ()()()() | 10101010 | 2 4 6 8       | 1 3 5 7
   10 | ()()(()) | 10101100 | 2 4 7 8       | 1 3 5 6
   11 | ()(())() | 10110010 | 2 5 6 8       | 1 3 4 7
   12 | ()(()()) | 10110100 | 2 5 7 8       | 1 3 4 6
   13 | ()((())) | 10111000 | 2 6 7 8       | 1 3 4 5
   14 | (())()() | 11001010 | 3 4 6 8       | 1 2 5 7
   15 | (())(()) | 11001100 | 3 4 7 8       | 1 2 5 6
   16 | (()())() | 11010010 | 3 5 6 8       | 1 2 4 7
   17 | (()()()) | 11010100 | 3 5 7 8       | 1 2 4 6
   18 | (()(())) | 11011000 | 3 6 7 8       | 1 2 4 5
   19 | ((()))() | 11100010 | 4 5 6 8       | 1 2 3 7
   20 | ((())()) | 11100100 | 4 5 7 8       | 1 2 3 6
   21 | ((()())) | 11101000 | 4 6 7 8       | 1 2 3 5
   22 | (((()))) | 11110000 | 5 6 7 8       | 1 2 3 4

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 440-444.

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

Cf. A063171, A370220, A072643 (row lengths), A371410 (row sums).

zlist[m_] := With[{r = 2*Range[2, m]}, Reverse[Map[Join[{1}, #] &, Select[Subsets[Range[2, 2*m-1], {m-1}], Min[r-#] > 0 &]]]];
Table[Delete[Map[Complement[Range[2*m], #] &, zlist[m]], 0], {m, 5}] (* Paolo Xausa, Mar 27 2024 *)
(* 2nd program: uses Algorithm Z from Knuth's TAOCP section 7.2.1.6, exercise 2 *)
zlist[m_] := Block[{z = 2*Range[m] - 1, j},
    Reap[
    While[True,
        Sow[z];
        If[z[[m-1]] < z[[m]] - 1,
            z[[m]]--,
            j = m - 1; z[[m]] = 2*m - 1;
            While[j > 1 && z[[j-1]] == z[[j]] - 1, z[[j]] = 2*j - 1; j--];
            If[j == 1,Break[]];
            z[[j]]--]
    ]][[2]][[1]]];
Join[{{2}}, Table[Delete[Map[Complement[Range[2*m], #] &, zlist[m]], 0], {m, 2, 5}]] (* Paolo Xausa, Mar 27 2024 *)

A075172 Number of edges in each rooted plane tree produced with the binary run length unranking algorithm presented in A075171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 13 2002

nonn

Also the digital length of A075171(n)/ 2. Each value v occurs A000108(v) times.

Permutation of A072643.

cp's OEIS Frontend

A126303 a(n) = number of nodes with odd distance to the root in the n-th plane general tree encoded by A014486(n). Both internal and terminal nodes (leaves) are counted.

Views

Author

Keywords

Examples

Crossrefs

A153250 Array A(x,y): A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ... formed by growing a bud (a single V-node) on the y-th leaf of the binary tree A014486(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A213704 Catalan Unranking function U(size,rank) for totally balanced binary strings (converted to decimal). Each row 'size' of an array lists all A000108(size) such items in standard lexicographic order, followed by an infinite number of zeros.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

A370219 Irregular triangle T(n,k) read by rows: row n lists run-length encoding d_k values (see comments) for the properly nested string of parentheses encoded by A063171(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A126305 a(n) = number of nodes with even distance to the root in the n-th plane general tree encoded by A014486(n). The root node itself is also included.

Views

Author

Keywords

Crossrefs

A130918 Simple self-inverse permutation of natural numbers: List each block of A000108(n) numbers from A014137(n-1) to A014138(n-1) in reverse order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A154475 Number of opening (equally: closing) brackets in each term of Wolfram's Symbolic Rewriting system A154473-A154474.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A154476 Number of e's in each iteration of Wolfram's e[x_][y_] -> x[x[y]] symbolic rewriting system, starting from the initial state e[e[e][e]][e][e].

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A371409 Irregular triangle T(n,k) read by rows: row n lists the positions of right parentheses in the properly nested string of parentheses encoded by A063171(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A075172 Number of edges in each rooted plane tree produced with the binary run length unranking algorithm presented in A075171.