A071152 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

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

FORMULA

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

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 *)

PROG

(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