cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A123050 Conjectured number of ordered trees on n edges for which the conjugate and transpose commute.

This page as a plain text file.
%I A123050 #6 Mar 31 2012 10:22:44
%S A123050 1,1,2,2,2,4,4,4,6,6,6,8,8,8,12,12,12,14,16,16,18,18,22,24,24,24,30,
%T A123050 30,30,32,38,38,40,40,46,48,48,48,58,58,58,60,68,68,70,70,80,82,82,82,
%U A123050 94,94,94,96,108,108,110,110,122,124,124,124,140,140,140,142,156,156,158
%N A123050 Conjectured number of ordered trees on n edges for which the conjugate and transpose commute.
%C A123050 The conjugate of an ordered tree is given by flipping it over, while its transpose is given by flipping over the corresponding binary tree. A list of ordered trees for which the conjugate and transpose commute, counted by this sequence, is given in Exercise 17, Sec. 7.2.1.6 of the Knuth reference. (Knuth deletes the root from an ordered tree and works with the resulting forest instead.) This list is complete provided a certain set of ordered trees contains no self-conjugate members other than the "obvious" ones.
%C A123050 The set in question consists of all trees generated by repeatedly applying the following two productions to the one-edge tree: (i) T -> plant(T) (i.e. add an edge to the root to obtain a new root) and (ii) T -> add left root edge to the transpose of the conjugate of T. Computational evidence suggests that this proviso does indeed hold.
%D A123050 D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation, vi+120pp. ISBN 0-321-33570-8 Addison-Wesley Professional; 1ST edition (Feb 06, 2006).
%H A123050 D. E. Knuth, <a href="http://www-cs-staff.Stanford.EDU/~knuth/fasc4a.ps.gz">Pre-Fascicle 4a: Generating All Trees</a>, Exercise 17, 7.2.1.6.
%F A123050 a(0)=a(1)=1, a(n) = 2(Floor[(n+1)/3] + Sum[Max[0,Floor[(n-(8k+2))/4]],{k,1,(n-2)/8}]) for n>=2. GF: 1 + x + 2x^2/((1-x)(1-x^3)) + 2x^14/((1-x)*(1-x^4)*(1-x^8))
%t A123050 a[0]=a[1]=1; a[n_]/;n>=2 := 2(Floor[(n+1)/3] + Sum[Max[0,Floor[(n-(8k+2))/4]],{k,1,(n-2)/8}]); Table[a[n],{n,0,90}]
%Y A123050 This sequence updates the lower bound conjectured in A079438.
%K A123050 nonn
%O A123050 0,3
%A A123050 _David Callan_, Sep 25 2006