login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A123050 Conjectured number of ordered trees on n edges for which the conjugate and transpose commute. 6
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, 30, 30, 32, 38, 38, 40, 40, 46, 48, 48, 48, 58, 58, 58, 60, 68, 68, 70, 70, 80, 82, 82, 82, 94, 94, 94, 96, 108, 108, 110, 110, 122, 124, 124, 124, 140, 140, 140, 142, 156, 156, 158 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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.

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.

REFERENCES

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).

LINKS

Table of n, a(n) for n=0..68.

D. E. Knuth, Pre-Fascicle 4a: Generating All Trees, Exercise 17, 7.2.1.6.

FORMULA

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))

MATHEMATICA

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}]

CROSSREFS

This sequence updates the lower bound conjectured in A079438.

Sequence in context: A086227 A302402 A079438 * A113694 A086159 A029048

Adjacent sequences:  A123047 A123048 A123049 * A123051 A123052 A123053

KEYWORD

nonn

AUTHOR

David Callan, Sep 25 2006

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 May 19 06:57 EDT 2019. Contains 323386 sequences. (Running on oeis4.)