% % http://www.iki.fi/~kartturi/matikka/Nekomorphisms/nrgatoms.txt % % % by Antti Karttunen, May 2003, http://www.iki.fi/~kartturi/ % % Some of the definitions & conditions are elaborated here % with the Prolog-code. % % This works with GNU prolog http://www.gnu.org/software/prolog % % Load as: % consult('c:\\matikka\\Nekomorphisms\\nrgatoms.txt'). % cons(CAR,CDR,[CAR|CDR]). %% Few examples of simple non-recursive gatomorphisms: %% 0 non-default clauses and 0 opening (closing) conses: a001477(X,X). %% Identity. % % A B --> B A % \ / \ / % X Y %% 1 non-default clause and 1 opening (closing) cons: a069770(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. a069770(X,X). %% The default clause, fix S-exprs (here just []) the above clause could not handle. %% One non-default clause and two opening (closing) conses: % % B C A C % \ / \ / % A M --> B N % \ / \ / % X Y a072796(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(A,C,N), cons(B,N,Y), !. a072796(X,X). %% Fix [] and S-exprs of length 1. % % C B C A % \ / \ / % M A --> N B % \ / \ / % X Y a072797(X,Y) :- cons(M,A,X), cons(C,B,M), % -- cons(C,A,N), cons(N,B,Y), !. a072797(X,X). %% Fix the rest. % % B C A B % \ / \ / % A M --> N C A [] --> [] A % \ / \ / \ / \ / % X Y X Y %% Two non-default clauses with 2 & 1 opening (closing) conses: a074679(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(A,B,N), cons(N,C,Y), !. a074679(X,Y) :- cons(A,B,X), % B = [] by above clause. % -- cons(B,A,Y), !. a074679(X,X). %% Fix the rest. % % C B B A % \ / \ / % M A --> C N [] B --> B [] % \ / \ / \ / \ / % X Y X Y a074680(X,Y) :- cons(M,A,X), cons(C,B,M), % -- cons(B,A,N), cons(C,N,Y), !. % Above clause implies that A = []. a074680(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. a074680(X,X). %% Fix the rest. %% %% (define (gmA082351! s) %% (cond ((not (pair? s)) s) %% ((not (pair? (car s))) s) %% ((not (pair? (cdr s))) (robl! (swap! s))) %% (else (robl! s)) %% ) %% ) %% %% (define (gmA082352! s) %% (cond ((not (pair? s)) s) %% ((not (pair? (car s))) s) %% ((not (pair? (caar s))) (swap! (robr! s))) %% (else (robr! s)) %% ) %% ) %% % A D % \ / % A D B C Q B A B [] A % \ / \ / \ / \ / \ / and by default: % P M --> N C M [] --> N B [] A [] A % \ / \ / \ / \ / \ / --> \ / % X Y X Y X Y %% Two non-default clauses with 3 & 2 = 5 opening (closing) conses: a082351(X,Y) :- cons(P,M,X), cons(A,D,P), cons(B,C,M), % -- cons(A,D,Q), %% Note: Q is equal to P. cons(Q,B,N), cons(N,C,Y), !. % Above clause implies that C=[]. a082351(X,Y) :- cons(M,C,X), cons(A,B,M), % -- cons(C,A,N), cons(N,B,Y), !. a082351(X,X). %% Fix the rest. % D C % \ / % P B D C B A [] B B A % \ / \ / \ / \ / \ / and by default: % M A --> Q N M A --> N [] [] A [] A % \ / \ / \ / \ / \ / --> \ / % X Y X Y X Y a082352(X,Y) :- cons(M,A,X), cons(P,B,M), cons(D,C,P), % -- cons(D,C,Q), % Note that Q is equal to P. cons(B,A,N), cons(Q,N,Y), !. a082352(X,Y) :- cons(M,A,X), cons(C,B,M), % -- cons(B,A,N), cons(N,C,Y), !. a082352(X,X). %% Fix the rest. %% %% We see that there are Cat(n)*(n+1)! (= A001813[n]) ways to form %% such gatomorphism of one non-default clause of n opening (closing) %% conses, of which only (Cat(n)*((n+1)!-1)) = A001813[n]-A000108[n] %% 0,1,10,115,1666,30198,665148,17296851,518916970,... (not in OEIS) %% result a non-identity permutation. %% %% Then for multiclause gatomorphisms, one clause can be constructed %% in Cat(n)*Cat(n)*(n+1)! (= A001246[n]*A000142[n+1] = A001813[n]*A000108[n]) %% ways: 1,2,24,600,23520,1270080,87816960,7420533120,742053312000 (not in EIS) %% and taking Cameron's inverse of this sequence (from a(n>=1) = 2 onward): %% INVERT([seq(Cat(n)*Cat(n)*(n+1)!,n=1..9)]); %% --> [2,28,704,26800,1404416,94890112,7887853568,779773444864,89407927009280,...] %% we get an absolute upper bound for number of (distinct) simple nonrecursive %% gatomorphisms of total n opening (closing) conses. %% %% This is because we can say that a sequence of triplets (X_i,Y_i,P_{i+1}) like: %% ((X_i1,Y_i1,P_{i1+1}),(X_i2,Y_i2,P_{i2+1}),...,(X_ik,Y_ik,P_{ik+1})) %% where i1+i2+...+ik = n %% contains sufficient information to define a simple nonrecursive %% gatomorphism of total n opening (closing) conses in k clauses. %% X_i ("source") and Y_i ("destination") refer to arbitrary binary trees %% of i+1 leaves (enumerated by Cat(i)), and P_{i+1} (enumerated by (i+1)!) %% refers to an arbitrary reordering of those i+1 leaves. Possibilities %% for one clause is a cartesian product of these three components. %% However, we can considerably improve the above upper bound by subtracting from it %% [seq((Cat(n)-1)*Cat(n)*(n+1)!,n=1..9)]; to get: %% [2,16,224,4960,164576,7738432,484617728,38239051264,3644207367680,...] %% because no clause with "source" and "destination"-subtrees of different %% shape can occur alone as a "stand-alone" clause: %% there is a binary tree A for which any such clause will succeed, %% but the resulting tree B will not, and because there are no %% other non-default clauses the B will be fixed, thus we have %% two binary trees A & B which map to the same tree B, and thus %% the clause does not result an injection, and cannot thus be %% a bijection either. %% %% There are also other ways to prune the search space. %% For example, it doesn't make sense to examine sequences %% (if we are looking only for distinct, new gatomorphisms that %% have not appeared for any smaller value of n) %% where a later triplet has a (source) binary tree X_j %% which is a super-tree of an earlier (source) binary tree X_i %% (in other words X_i is a subtree of X_j, i.e. X_i = A082858(X_i,X_j)), %% because then the latter clause is no-op, as the first clause %% will always succeed for any tree which would succeed for the latter clause. %% %% Questions: %% %% Is there some a priori way of determining which such triplet-combinations %% result a gatomorphism (i.e. a bijection on the set of binary trees)? %% %% If not, then what is the sure(st) technique for determining whether %% a collection of such clauses indeed result a gatomorphism, i.e. a true bijection? %% Is it enough to check that the candidate gatomorphism looks like %% a bijection up to a certain size s of the binary trees? %% (where s depends only on the sequence of clauses in the candidate gatomorphism) %% %% % Two non-default clauses with 3 + 1 = 4 opening (closing) conses: % % % A B C D B A D C % \ / \ / \ / \ / % M N --> P Q A B --> B A % \ / \ / \ / \ / % X Y X Y %% Alternatively, for the first clause we could have any other permutation of the %% four leaves A,B,C & D, as long as we keep the shape of src- & dst-tree same. %% Here we notice that the first clause implies that if we ever %% come to the second clause, then either A or B (the left or right-hand-side subtree) %% is empty, []. %% Both clauses would work as stand-alone clauses, but they also work %% together because the trees for which they succeed are never in the same %% orbit. (The orbit counts of the combination should be easy to compute %% from the orbit counts of the separate clauses? Here the combination %% has the same orbit profile as the latter clause alone (a069770), %% both are involutions.) %% Is this a general condition for the set of stand-alone clauses to work %% together as a bijection? example1(X,Y) :- cons(M,N,X), cons(A,B,M), cons(C,D,N), % -- cons(B,A,P), cons(D,C,Q), cons(P,Q,Y), !. example1(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. example1(X,X). %% Fix the rest. % Two non-default clauses with 2 + 1 = 3 opening (closing) conses: % % % B C C A % \ / \ / % A M --> B P A B --> B A % \ / \ / \ / \ / % X Y X Y % example2(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(C,A,P), cons(B,P,Y), !. example2(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. example2(X,X). %% Fix the rest. %% Here we notice that the first clause implies that if we ever %% come to the second clause, then its B (the right-hand-side subtree) %% is empty, []. %% Both clauses would work as stand-alone clauses, as they are just %% permutations of certain branches of otherwise fixed-shape subtree. %% However, as together they don't form a bijection, because %% the first clause maps %% %% [] s s r %% \ / \ / %% r . --> [] . %% \ / \ / %% . . %% %% to which the second clause also maps this tree: %% %% s r %% \ / %% . [] %% \ / %% . %% %% (which will be left alone by the first clause, because its right subtree is []). %% So again, the injectivity is broken, thus we have no bijection either. %% %% %% Neither this will work, I think: %% %% B C C B %% \ / \ / %% A M --> A P A B --> B A %% \ / \ / \ / \ / %% X Y X Y %% %% %% %% By Antti Karttunen, 18. - 19. May 2003. %%