login
Binary encoding of balanced ordered rooted trees (counted by A007059).
3

%I #6 Nov 21 2022 22:01:53

%S 0,2,10,12,42,52,56,170,204,212,232,240,682,820,844,852,920,936,976,

%T 992,2730,3276,3284,3380,3404,3412,3640,3688,3736,3752,3888,3920,4000,

%U 4032,10922,13108,13132,13140,13516,13524,13620,13644,13652,14568,14744,14760

%N Binary encoding of balanced ordered rooted trees (counted by A007059).

%C An ordered tree is balanced if all leaves are the same distance from the root.

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

%e The terms together with their corresponding trees begin:

%e 0: o

%e 2: (o)

%e 10: (oo)

%e 12: ((o))

%e 42: (ooo)

%e 52: ((oo))

%e 56: (((o)))

%e 170: (oooo)

%e 204: ((o)(o))

%e 212: ((ooo))

%e 232: (((oo)))

%e 240: ((((o))))

%e 682: (ooooo)

%e 820: ((o)(oo))

%e 844: ((oo)(o))

%e 852: ((oooo))

%e 920: (((o)(o)))

%e 936: (((ooo)))

%e 976: ((((oo))))

%e 992: (((((o)))))

%t 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]}];

%t bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]]

%t Select[Range[0,1000],binbalQ[#]&&SameQ@@Length/@Position[bint[#],{}]&]

%Y These trees are counted by A007059.

%Y This is a subset of A014486.

%Y The version for binary trees is A057122.

%Y The unordered version is A184155, counted by A048816.

%Y Another ranking of balanced ordered trees is A358459.

%Y A000108 counts ordered rooted trees, unordered A000081.

%Y A358453 counts transitive ordered trees, unordered A290689.

%Y Cf. A001263, A003238, A244925, A358377, A358379, A358523.

%K nonn

%O 1,2

%A _Gus Wiseman_, Nov 21 2022