Changed layout for more manageable volumes

1 files changed, 224 insertions, 0 deletions

diff --git a/vol1/2.3.4.6.lyx b/vol1/2.3.4.6.lyx
new file mode 100644
index 0000000..1373c23
--- /dev/null
+++ b/vol1/2.3.4.6.lyx
@@ -0,0 +1,224 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 620
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input defs
+\end_preamble
+\use_default_options true
+\maintain_unincluded_children no
+\language english
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_formatted_ref 0
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\docbook_mathml_prefix 1
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc1[21]
+\end_layout
+
+\end_inset
+
+Find a simple one-to-one correspondence between binary trees with 
+\begin_inset Formula $n$
+\end_inset
+
+ nodes and dissections of an 
+\begin_inset Formula $(n+2)$
+\end_inset
+
+-sided convex polygon into 
+\begin_inset Formula $n$
+\end_inset
+
+ triangles,
+ assuming that the sides of the polygon are distinct.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $v_{0},\dots,v_{n+1}$
+\end_inset
+
+ be the vertices of the polygon.
+ We start at the root and,
+ if the left subtree has 
+\begin_inset Formula $k$
+\end_inset
+
+ nodes (
+\begin_inset Formula $0\leq k<n$
+\end_inset
+
+) and the right subtree has 
+\begin_inset Formula $n-k-1$
+\end_inset
+
+ nodes,
+ we take out the triangle 
+\begin_inset Formula $\text{conv}\{v_{0},v_{1},v_{k+2}\}$
+\end_inset
+
+.
+ This leaves us with a polygon of 
+\begin_inset Formula $k+2$
+\end_inset
+
+ nodes 
+\begin_inset Formula $v_{1},\dots,v_{k+2}$
+\end_inset
+
+ when the left subtree is not empty,
+ and one of 
+\begin_inset Formula $n-k+1$
+\end_inset
+
+ nodes 
+\begin_inset Formula $v_{k+2},\dots,v_{n+1},v_{0}$
+\end_inset
+
+ when the right subtree is not empty,
+ and we just have to dissect these two smaller polygons recursively,
+ for example,
+ by renaming 
+\begin_inset Formula $v_{k+2}$
+\end_inset
+
+ to 
+\begin_inset Formula $v_{0}$
+\end_inset
+
+ in the polygon for the left subtree and 
+\begin_inset Formula $v_{k+2},\dots,v_{n+1}$
+\end_inset
+
+ to 
+\begin_inset Formula $v_{1},\dots,v_{n-k}$
+\end_inset
+
+ in the polygon for the right subtree.
+\end_layout
+
+\begin_layout Standard
+To get back the original binary tree,
+ we just have to see which other vertex is in the triangle that contains the edge between 
+\begin_inset Formula $v_{0}$
+\end_inset
+
+ and 
+\begin_inset Formula $v_{1}$
+\end_inset
+
+,
+ take it out,
+ and then 
+\begin_inset Quotes eld
+\end_inset
+
+decode
+\begin_inset Quotes erd
+\end_inset
+
+ the two remaining polygons if they exist,
+ something we can do for arbitrary dissections of the polygon.
+\end_layout
+
+\end_body
+\end_document