A071152 Łukasiewicz words for the rooted plane binary trees (interpretation d in Stanley's exercise 19) with the last leaf implicit, i.e., these words are given without the last trailing zero, except for the null tree which is encoded as 0.

0, 20, 2020, 2200, 202020, 202200, 220020, 220200, 222000, 20202020, 20202200, 20220020, 20220200, 20222000, 22002020, 22002200, 22020020, 22020200, 22022000, 22200020, 22200200, 22202000, 22220000, 2020202020, 2020202200

Offset: 0

Author

Antti Karttunen, May 14 2002

Keywords

• nonn

Links

• Paolo Xausa, Table of n, a(n) for n = 0..23713
• Indranil Ghosh, Python program for computing this sequence
• Antti Karttunen, Collection of source-code for this and similar sequences in Internet Archive (Look especially in the first three modules, gatomain.scm, gatorank.scm and gatoaltr.scm. To be replaced later with a stand-alone code.)
• R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
• R. P. Stanley, Exercises on Catalan and Related Numbers
• OEIS Wiki, Łukasiewicz words
• Index entries for sequences related to Łukasiewicz

Crossrefs

a(n) = 2*A063171(n) = A071153(A057123(n)).

Cf. A014486, A059984, A059985, A071153, A071154, A079436.

Programs

Mathematica

balancedQ[0] = True; balancedQ[n_] := (s = 0; Do[s += If[b == 1, 1, -1]; If[s < 0, Return[False]], {b, IntegerDigits[n, 2]}]; Return[s == 0]); 2*FromDigits /@ IntegerDigits[ Select[Range[0, 684], balancedQ], 2] (* Jean-François Alcover, Jul 24 2013 *)
Array[Map[FromDigits[# /. -1->0]*20 &, Select[Permutations[Join[Table[-1, #-1], Table[1,#]]], Min[Accumulate[#]] >=0 &]]&, 6, 0] (* Paolo Xausa, Mar 12 2024 *)

Python

from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A071152_gen(): # generator of terms
    yield 0
    for l in count(1):
        for s in multiset_permutations('0'*l+'1'*(l-1)):
            c, m = 0, (l<<1)-1
            for i in range(m):
                if s[i] == '1':
                    c += 2
                if cA071152_list = list(islice(A071152_gen(),30)) # Chai Wah Wu, Nov 28 2023

Formula

a(n) = 2*A063171(n).