%I
%S 1,5,30,196,1348,9603,70210,523732,3969948,30490434
%N 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}.
%C 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.
%C Parse words are counted only up to permutation of the three letters.
%C The statement that all pairs of binary trees have at least one common parse word under G is equivalent to the fourcolor theorem.
%H B. Cooper and E. Rowland and D. Zeilberger, <a href="http://arxiv.org/abs/1006.1324">Toward a language theoretic proof of the four color theorem</a>, arXiv:1006.1324 [math.CO], 20112012.
%H B. Cooper and E. Rowland and D. Zeilberger, <a href="http://dx.doi.org/10.1016/j.aam.2011.11.002">Toward a language theoretic proof of the four color theorem</a>, Advances in Applied Mathematics 48 (2012), 414431.
%H E. Rowland, <a href="https://ericrowland.github.io/packages/ParseWords.m"> Mathematica program ParseWords.m</a>.
%H D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/LOU">Maple program LOU.txt</a>.
%e 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.
%p read `LOU.txt`; # see link above
%p seq(nops(MinLou(n)[2]), n=3..7);
%t BinaryTrees[1] = {{}};
%t BinaryTrees[n_Integer /; n > 1] := BinaryTrees[n] =
%t Join @@ Table[Tuples[{BinaryTrees[i], BinaryTrees[n  i]}], {i, n  1}];
%t ParseWords[{}, root_] := {{root}};
%t ParseWords[tree_List, root_: 0] := ParseWords[tree, root] =
%t With[{col = DeleteCases[{0, 1, 2}, root]}, Join[
%t Flatten /@ Tuples[{ParseWords[tree[[1]], col[[1]]], ParseWords[tree[[2]], col[[2]]]}],
%t Flatten /@ Tuples[{ParseWords[tree[[1]], col[[2]]], ParseWords[tree[[2]], col[[1]]]}]
%t ]];
%t MinTreePairs[n_Integer /; n > 0] :=
%t Count[Length[Intersection[ParseWords[#1], ParseWords[#2]]]& @@@ Subsets[BinaryTrees[n], {2}], 2];
%K nonn,hard,more
%O 3,2
%A _Christoph Koutschan_, Apr 06 2016
