login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A265279 Number of pairs of binary trees with n leaves which have only a single common parse word under the grammar G = {0 -> 12, 0 -> 21, 1 -> 02, 1 -> 20, 2 -> 01, 2 -> 10}. 0
1, 5, 30, 196, 1348, 9603, 70210, 523732, 3969948, 30490434 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,2

COMMENTS

We say that a word w in {0,1,2}^* is a parse word of a binary tree T if T is the derivation tree of w under the given grammar G.

Parse words are counted only up to permutation of the three letters.

The statement that all pairs of binary trees have at least one common parse word under G is equivalent to the four-color theorem.

LINKS

Table of n, a(n) for n=3..12.

B. Cooper and E. Rowland and D. Zeilberger, Toward a language theoretic proof of the four color theorem, arXiv:1006.1324 [math.CO], 2011-2012.

B. Cooper and E. Rowland and D. Zeilberger, Toward a language theoretic proof of the four color theorem, Advances in Applied Mathematics 48 (2012), 414-431.

E. Rowland, Mathematica program ParseWords.m.

D. Zeilberger, Maple program LOU.txt.

EXAMPLE

There are exactly two binary trees with n = 3 leaves, the first one parses the words 101 and 110, the second one parses the words 011 and 101 (and all words obtained by permuting the letters 0, 1, 2). Thus this single pair of trees has precisely one common parse word.

MAPLE

read `LOU.txt`;  # see link above

seq(nops(MinLou(n)[2]), n=3..7);

MATHEMATICA

BinaryTrees[1] = {{}};

BinaryTrees[n_Integer /; n > 1] := BinaryTrees[n] =

  Join @@ Table[Tuples[{BinaryTrees[i], BinaryTrees[n - i]}], {i, n - 1}];

ParseWords[{}, root_] := {{root}};

ParseWords[tree_List, root_: 0] := ParseWords[tree, root] =

  With[{col = DeleteCases[{0, 1, 2}, root]}, Join[

    Flatten /@ Tuples[{ParseWords[tree[[1]], col[[1]]], ParseWords[tree[[2]], col[[2]]]}],

    Flatten /@ Tuples[{ParseWords[tree[[1]], col[[2]]], ParseWords[tree[[2]], col[[1]]]}]

  ]];

MinTreePairs[n_Integer /; n > 0] :=

  Count[Length[Intersection[ParseWords[#1], ParseWords[#2]]]& @@@ Subsets[BinaryTrees[n], {2}], 2];

CROSSREFS

Sequence in context: A158828 A264910 A196471 * A034164 A322257 A103433

Adjacent sequences:  A265276 A265277 A265278 * A265280 A265281 A265282

KEYWORD

nonn,hard,more

AUTHOR

Christoph Koutschan, Apr 06 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 4 18:38 EDT 2020. Contains 335448 sequences. (Running on oeis4.)