A057515 -id:A057515 - cp's OEIS frontend

A126307 a(n) is the length of the leftmost ascent (i.e., height of the first peak) in the n-th Dyck path encoded by A014486(n).

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

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

In other words, this sequence gives the number of leading 1's in the terms of A063171.

			A014486(20) = 228 (11100100 in binary), encodes the following Dyck path:
    /\
   /  \/\
  /      \
and the first rising (left-hand side) slope has length 3, thus a(20)=3.

a(n) = A099563(A071156(n)) = A057515(A125985(n)) = A080237(A057164(n)) = A057515(A057504(A057164(n))).

a(n) = A090996(A014486(n)).

A079436 Full Łukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by A014486 (or A063171).

Original entry on oeis.org

0, 10, 200, 110, 3000, 2010, 2100, 1200, 1110, 40000, 30010, 30100, 20200, 20110, 31000, 21010, 22000, 13000, 12010, 21100, 12100, 11200, 11110, 500000, 400010, 400100, 300200, 300110, 401000, 301010, 302000, 203000, 202010, 301100, 202100

Offset: 0

Antti Karttunen, Jan 09 2003

Note: Here the last leaf is explicit, i.e. the terms are obtained from those of A071153 by multiplying them by 10.

Note: this finite decimal representation works only up to the 6917th term, as the 6918th such word is already "x0000000000" (where x stands for digit "ten").

Antti Karttunen, Illustration of initial terms
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz

a(n) = 10*A071153(n).
For n > 1, the number of zeros in the term a(n) is given by A057514(n).
The first digit of each term is given by A057515.
Cf. A059984, A059985.

A080071 Top-level length of each parenthesization/root degree of general trees encoded in A080070.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 27 2003

nonn

Cf. A080070, A080090.

a(n) = A057515(A080068(n))

A153240 Balance of general trees as ordered by A014486, variant A.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 21 2008

sign

This differs from variant A153241 only in that if the degree of the tree is odd (i.e. A057515(n) = 1 mod 2), then the balance of the center-subtree is always taken into account.

Note that for all n, Sum_{i=A014137(n)}^A014138(n) a(i) = 0.

			A014486(25) encodes the following general tree:
......o
......|
o.o...o.o
.\.\././
....*..
which consists of four subtrees, of which the second from right is one larger than the others, so we have a(25) = (0+1)-(0+0) = 1.

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

Differs from variant A153241 for the first time at n=268, where A153241(268) = 1, while a(268)=2. Note that (A014486->parenthesization (A014486 268)) = (() (() (())) (())). a(A061856(n)) = 0 for all n. Cf. also A153239.

A123695 Signature permutation of a nonrecursive Catalan automorphism: row 1653002 of table A089840.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

It is possible to recursively construct more of these kinds of nonrecursive automorphisms, which by default (if A057515(n) > 1) work as *A074679 and otherwise apply the previous automorphism of this construction process (here *A074679 itself) to the left subtree of a binary tree, before the whole tree is swapped with *A069770. Do the associated cycle-count sequences converge to anything interesting?
This automorphism is illustrated below, where letters A, B and C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.
...........................B...C........A...B..............................
............................\./..........\./...............................
..B...C.....A...B........A...x............x...C...A..()...............()..A
...\./.......\./..........\./..............\./.....\./.................\./.
A...x....-->..x...C........x..()...-->..()..x.......x..()....-->....()..x..
.\./...........\./..........\./..........\./.........\./.............\./...
..x.............x............x............x...........x...............x....

Inverse: A123696. Row 1653002 of A089840. Variant of A074679.

A153241 Balance of general trees as ordered by A014486, variant B.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 21 2008

sign

This differs from variant A153240 only in that if the degree of the tree is odd (i.e. A057515(n) = 1 mod 2), then the balance of the center-subtree is taken into account ONLY if the total weight of other subtrees at the left and the right hand side from the center were balanced against each other.

Note that for all n, Sum_{i=A014137(n)}^A014138(n) a(i) = 0.

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

Differs from variant A153240 for the first time at n=268, where A153240(268) = 2, while a(268)=1. Note that (A014486->parenthesization (A014486 268)) = (() (() (())) (())). a(A061856(n)) = 0 for all n. Cf. also A153239.

A083923 Characteristic function for A057548.

Original entry on oeis.org

0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Antti Karttunen, May 13 2003

nonn

Index entries for characteristic functions

a(n) = A083924(A069770(n)). Used to compute A083925.

a(n) = 1 if A057515(n)=1 (equivalently: if A072772(n)=0), otherwise 0.

A123714 Signature permutation of a nonrecursive Catalan automorphism: row 1786785 of table A089840.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

This automorphism is illustrated below, where letters A, B, C, D, E and F refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.
.............................B...C............F...B......
..............................\./..............\./.......
...............................x...D............x...C....
................................\./..............\./.....
.................................x...E............x...D..
..................................\./.....-->......\./...
..A...B.........C...A..............x...F............x...E
...\./...........\./................\./..............\./.
....x...C...-->...x...B..........()..x............()..x..
.....\./...........\./............\./..............\./...
......x.............x..............x................x....
This is the last multiclause automorphism of total seven opened conses in the table A089840. The next nonrecursive automorphism, A089840[1786786], which consists of a single seven-node clause, swaps the first two toplevel elements (of a general plane tree, like *A072796 does), but only if A057515(n) > 6 and in other cases keeps the tree intact.

Inverse: A123713. Row 1786785 of A089840. Differs from A089857 for the first time at n=102, where a(n)=106, while A089857(n)=102.

A358550 Depth of the ordered rooted tree with binary encoding A014486(n).

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 22 2022

nonn

The binary encoding of an ordered tree (A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

			The first few rooted trees in binary encoding are:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))

Positions of first appearances are A014137.
Leaves of the ordered tree are counted by A057514, standard A358371.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
Positions of 2's are A155587, indices of A020988.
The standard ranking of the ordered tree is A358523.
Nodes of the ordered tree are counted by A358551, standard A358372.
For standard instead of binary encoding we have A358379.
A000108 counts ordered rooted trees, unordered A000081.
A014486 lists all binary encodings.
Cf. A001263, A057122, A358373, A358505, A358524.

binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]];
Table[Depth[bint[k]]-1,{k,Select[Range[0,1000],binbalQ]}]

A358551 Number of nodes in the ordered rooted tree with binary encoding A014486(n).

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 22 2022

nonn

The binary encoding of an ordered tree (A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

			The first few rooted trees in binary encoding are:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))

Run-lengths are A000108.
Binary encodings are listed by A014486.
Leaves of the ordered tree are counted by A057514, standard A358371.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
For standard instead of binary encoding we have A358372.
The standard ranking of the ordered tree is A358523.
Depth of the ordered tree is A358550, standard A358379.
Cf. A000081, A001263, A057122, A358373, A358505, A358524.

binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]];
Table[Count[bint[k],_,{0,Infinity}],{k,Select[Range[0,10000],binbalQ]}]

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

cp's OEIS Frontend

A126307 a(n) is the length of the leftmost ascent (i.e., height of the first peak) in the n-th Dyck path encoded by A014486(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A079436 Full Łukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by A014486 (or A063171).

Views

Author

Keywords

Comments

Links

Crossrefs

A080071 Top-level length of each parenthesization/root degree of general trees encoded in A080070.

Views

Author

Keywords

Crossrefs

Formula

A153240 Balance of general trees as ordered by A014486, variant A.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A123695 Signature permutation of a nonrecursive Catalan automorphism: row 1653002 of table A089840.

Views

Author

Keywords

Comments

Links

Crossrefs

A153241 Balance of general trees as ordered by A014486, variant B.

Views

Author

Keywords

Comments

Links

Crossrefs

A083923 Characteristic function for A057548.

Views

Author

Keywords

Links

Crossrefs

Formula

A123714 Signature permutation of a nonrecursive Catalan automorphism: row 1786785 of table A089840.

Views

Author

Keywords

Comments

Links

Crossrefs

A358550 Depth of the ordered rooted tree with binary encoding A014486(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358551 Number of nodes in the ordered rooted tree with binary encoding A014486(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula