login
Ł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.
3

%I #58 Mar 12 2024 19:01:36

%S 0,20,2020,2200,202020,202200,220020,220200,222000,20202020,20202200,

%T 20220020,20220200,20222000,22002020,22002200,22020020,22020200,

%U 22022000,22200020,22200200,22202000,22220000,2020202020,2020202200

%N Ł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.

%H Paolo Xausa, <a href="/A071152/b071152.txt">Table of n, a(n) for n = 0..23713</a>

%H Indranil Ghosh, <a href="/A071152/a071152.txt">Python program for computing this sequence</a>

%H Antti Karttunen, <a href="https://web.archive.org/web/20070114104000/http://ndirty.cute.fi/~karttu/matikka/Nekomorphisms/gatomorf.htm">Collection of source-code for this and similar sequences in Internet Archive</a> (Look especially in the first three modules, gatomain.scm, gatorank.scm and gatoaltr.scm. To be replaced later with a stand-alone code.)

%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/hip.pdf">Hipparchus, Plutarch, Schröder and Hough</a>, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.

%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/ec/catalan.pdf">Exercises on Catalan and Related Numbers</a>

%H OEIS Wiki, <a href="/wiki/Łukasiewicz_words">Łukasiewicz words</a>

%H <a href="/index/Lu#Lukasiewicz">Index entries for sequences related to Łukasiewicz</a>

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

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

%t Array[Map[FromDigits[# /. -1->0]*20 &, Select[Permutations[Join[Table[-1, #-1], Table[1,#]]], Min[Accumulate[#]] >=0 &]]&, 6, 0] (* _Paolo Xausa_, Mar 12 2024 *)

%o (Python)

%o from itertools import count, islice

%o from sympy.utilities.iterables import multiset_permutations

%o def A071152_gen(): # generator of terms

%o yield 0

%o for l in count(1):

%o for s in multiset_permutations('0'*l+'1'*(l-1)):

%o c, m = 0, (l<<1)-1

%o for i in range(m):

%o if s[i] == '1':

%o c += 2

%o if c<i:

%o break

%o else:

%o yield 10**m+int(''.join(s))<<1

%o A071152_list = list(islice(A071152_gen(),30)) # _Chai Wah Wu_, Nov 28 2023

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

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

%K nonn

%O 0,2

%A _Antti Karttunen_, May 14 2002