From 4f670b750af5c11e1eac16d9cd8556455f89f46a Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan@mnpi.eu>
Date: Fri, 16 May 2025 22:18:44 +0200
Subject: Changed layout for more manageable volumes

---
 2.3.4.4.lyx | 750 ------------------------------------------------------------
 1 file changed, 750 deletions(-)
 delete mode 100644 2.3.4.4.lyx

(limited to '2.3.4.4.lyx')

diff --git a/2.3.4.4.lyx b/2.3.4.4.lyx
deleted file mode 100644
index 0172abf..0000000
--- a/2.3.4.4.lyx
+++ /dev/null
@@ -1,750 +0,0 @@
-#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
-rexerc5[M25]
-\end_layout
-
-\end_inset
-
-(A.
- Cayley.) Let 
-\begin_inset Formula $c_{n}$
-\end_inset
-
- be the number of (unlabeled) oriented trees having 
-\begin_inset Formula $n$
-\end_inset
-
- leaves (namely,
- vertices with in-degree zero) and having at least two subtrees at every other vertex.
- Thus 
-\begin_inset Formula $c_{3}=2$
-\end_inset
-
-,
- by virtue of the two trees
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-begin{center}
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-def
-\backslash
-dot#1{node(#1){
-\backslash
-textbullet}}
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-begin{tikzpicture}
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw (0,1) 
-\backslash
-dot R (-.5,0) 
-\backslash
-dot A (0,0) 
-\backslash
-dot B (.5,0) 
-\backslash
-dot C
-\end_layout
-
-\begin_layout Plain Layout
-
-      (0,-1) node{};
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw[->] (A) -> (R);
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw[->] (B) -> (R);
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw[->] (C) -> (R);
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-end{tikzpicture}
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-hfil
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-begin{tikzpicture}
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw (0,1) 
-\backslash
-dot R (-.5,0) 
-\backslash
-dot A (.5,0) 
-\backslash
-dot B
-\end_layout
-
-\begin_layout Plain Layout
-
-                   (-1,-1) 
-\backslash
-dot C (0,-1) 
-\backslash
-dot D;
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw[->] (C) -> (A);
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw[->] (D) -> (A);
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw[->] (B) -> (R);
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-draw[->] (A) -> (R);
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-end{tikzpicture}
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-end{center}
-\end_layout
-
-\end_inset
-
-Find a formula analogous to (3) for the generating function
-\begin_inset Formula 
-\[
-C(z)=\sum_{n}c_{n}z^{n}.
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-Every tree has at least one leaf,
- so 
-\begin_inset Formula $c_{0}=0$
-\end_inset
-
-.
- This includes subtrees,
- so 
-\begin_inset Formula $c_{1}=1$
-\end_inset
-
- as,
- if the root weren't also a leaf,
- it would have at least two children and therefore two trees.
- For 
-\begin_inset Formula $n>1$
-\end_inset
-
-,
- the root has a tree and various subtrees.
- Let 
-\begin_inset Formula $j_{k}$
-\end_inset
-
- be the number of subtrees with 
-\begin_inset Formula $k$
-\end_inset
-
- leaves,
- 
-\begin_inset Formula $1\leq k<n$
-\end_inset
-
-,
- for those subtrees we may choose up to
-\begin_inset Formula 
-\[
-\binom{c_{k}+j_{k}-1}{j_{k}}
-\]
-
-\end_inset
-
-possibilities,
- since these are combinations with repetition (see exercise 1.2.6–60),
- so
-\begin_inset Formula 
-\[
-c_{n}=\sum_{\begin{subarray}{c}
-j_{1},\dots,j_{n-1}\geq0\\
-j_{1}+2j_{2}+\dots+(n-1)j_{n-1}=n
-\end{subarray}}\binom{c_{1}+j_{1}-1}{j_{1}}\cdots\binom{c_{n-1}+j_{n-1}-1}{j_{n-1}}.
-\]
-
-\end_inset
-
-Note that this is like (2) except that we have 
-\begin_inset Formula $n$
-\end_inset
-
- under the sum instead of 
-\begin_inset Formula $n-1$
-\end_inset
-
-.
- Thus,
- using the same identity as in the derivation of (3),
-\begin_inset Formula 
-\begin{align*}
-C(z) & =c_{0}+c_{1}z+\sum_{n\geq2}\sum_{\begin{subarray}{c}
-j_{1},\dots,j_{n-1}\geq0\\
-j_{1}+2j_{2}+\dots+(n-1)j_{n-1}=n
-\end{subarray}}\prod_{k=1}^{n-1}\binom{c_{k}+j_{k}-1}{j_{k}}z^{kj_{k}}\\
- & =z+\sum_{(j_{n})_{n}\in\mathbb{N}^{(\mathbb{N}^{*})}}\prod_{n\geq1}\binom{c_{n}+j_{n}-1}{j_{n}}z^{nj_{n}}-\sum_{n\geq1}c_{n}z^{n}-1\\
- & =\prod_{n\geq1}\sum_{j\geq1}\binom{c_{n}+j-1}{j}z^{nj_{n}}-C(z)+z-1\\
- & =\frac{1}{(1-z)^{c_{1}}(1-z^{2})^{c_{2}}\cdots(1-z^{n})^{c_{n}}\cdots}-C(z)+z-1,
-\end{align*}
-
-\end_inset
-
-where 
-\begin_inset Formula $\mathbb{N}^{(\mathbb{N}^{*})}$
-\end_inset
-
- is the set of sequences of natural numbers starting at 
-\begin_inset Formula $j_{1}$
-\end_inset
-
- and with a finite amount of nonzero coefficients;
- the subtracted term 
-\begin_inset Formula $\sum_{n\geq1}c_{n}z^{n}$
-\end_inset
-
- is there to cancel the terms which correspond to nodes having just one child,
- and likewise for 
-\begin_inset Formula $-1$
-\end_inset
-
- for the term with all zeroes.
-\end_layout
-
-\begin_layout Standard
-Thus,
-\begin_inset Formula 
-\[
-C(z)=\frac{1}{2}\left(\prod_{n\geq1}\frac{1}{(1-z^{n})^{c_{n}}}+z-1\right).
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc10[M22]
-\end_layout
-
-\end_inset
-
-Prove that a free tree with 
-\begin_inset Formula $n$
-\end_inset
-
- vertices and two centroids consists of two free trees with 
-\begin_inset Formula $n/2$
-\end_inset
-
- vertices,
- joined by an edge.
- Conversely,
- if two free trees with 
-\begin_inset Formula $m$
-\end_inset
-
- vertices are joined by an edge,
- we obtain a free tree with 
-\begin_inset Formula $2m$
-\end_inset
-
- vertices and two centroids.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer
-\end_layout
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Itemize
-\begin_inset Argument item:1
-status open
-
-\begin_layout Plain Layout
-\begin_inset Formula $\implies]$
-\end_inset
-
-
-\end_layout
-
-\end_inset
-
-Let 
-\begin_inset Formula $u$
-\end_inset
-
- and 
-\begin_inset Formula $v$
-\end_inset
-
- be the two centroids,
- with weight 
-\begin_inset Formula $m$
-\end_inset
-
-.
- If 
-\begin_inset Formula $u$
-\end_inset
-
- had weight 
-\begin_inset Formula $m$
-\end_inset
-
- from an edge that wasn't the one that leads to 
-\begin_inset Formula $v$
-\end_inset
-
-,
- then 
-\begin_inset Formula $v$
-\end_inset
-
- would have weight at least 
-\begin_inset Formula $m+1$
-\end_inset
-
-,
- owing to the 
-\begin_inset Formula $m$
-\end_inset
-
- nodes that stem from that edge in 
-\begin_inset Formula $u$
-\end_inset
-
- and 
-\begin_inset Formula $u$
-\end_inset
-
- itself.
-\begin_inset Formula $\#$
-\end_inset
-
- By a similar argument,
- if there were an intermediate node 
-\begin_inset Formula $w\neq u,v$
-\end_inset
-
- in the path connecting 
-\begin_inset Formula $u$
-\end_inset
-
- with 
-\begin_inset Formula $v$
-\end_inset
-
-,
- its weight must necessarily be at most 
-\begin_inset Formula $m-1\#$
-\end_inset
-
-.
- Therefore 
-\begin_inset Formula $u$
-\end_inset
-
- and 
-\begin_inset Formula $v$
-\end_inset
-
- are the only centroids,
- they are connected with an edge and the subtrees that result from removing that edge have 
-\begin_inset Formula $m$
-\end_inset
-
- nodes each.
-\end_layout
-
-\begin_layout Itemize
-\begin_inset Argument item:1
-status open
-
-\begin_layout Plain Layout
-\begin_inset Formula $\impliedby]$
-\end_inset
-
-
-\end_layout
-
-\end_inset
-
-Let 
-\begin_inset Formula $u$
-\end_inset
-
- and 
-\begin_inset Formula $v$
-\end_inset
-
- be the two nodes that are newly connected,
- then 
-\begin_inset Formula $u$
-\end_inset
-
- has weight 
-\begin_inset Formula $m$
-\end_inset
-
- because of its connection with 
-\begin_inset Formula $v$
-\end_inset
-
-,
- 
-\begin_inset Formula $v$
-\end_inset
-
- has weight 
-\begin_inset Formula $m$
-\end_inset
-
- because of its connection with 
-\begin_inset Formula $u$
-\end_inset
-
-,
- and any other node has weight at least 
-\begin_inset Formula $m+1$
-\end_inset
-
- because of their connection to 
-\begin_inset Formula $u$
-\end_inset
-
- and 
-\begin_inset Formula $v$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc14[10]
-\end_layout
-
-\end_inset
-
-True or false:
- The last entry,
- 
-\begin_inset Formula $f(V_{n-1})$
-\end_inset
-
-,
- in the canonical representation of an oriented tree is always the root of that tree.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-True.
- After each removal step,
- we still have a tree with the same root,
- and by the end the tree has no edges and therefore it only has one node,
- which is the root.
- Just before that,
- it only has one edge,
- which must connect a direct child of the root to the root.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc21[M20]
-\end_layout
-
-\end_inset
-
-Enumerate the number of labeled oriented trees in which each vertex has in-degree zero or two.
- (See exercise 20 and exercise 2.3–20.)
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-These are precisely the 0-2-trees in exercise 2.3–20.
- We know 0-2-trees always have an odd number of nodes,
- say 
-\begin_inset Formula $2m+1$
-\end_inset
-
- nodes.
- By the construction in the text,
- these trees correspond to sequences of 
-\begin_inset Formula $2m$
-\end_inset
-
- nodes where each node that appears does so exactly twice.
- There are 
-\begin_inset Formula $\binom{2m+1}{m}$
-\end_inset
-
- ways to choose which nodes 
-\emph on
-do
-\emph default
- appear in the sequence,
- and 
-\begin_inset Formula $\frac{(2m)!}{2^{m}}$
-\end_inset
-
- ways to arranging them (we can think of arranging 
-\begin_inset Formula $2m$
-\end_inset
-
- elements and then discarding the relative order of equal pairs of elements).
- This gives us
-\begin_inset Formula 
-\[
-\binom{2m+1}{m}(2m)!\Bigg/2^{m}
-\]
-
-\end_inset
-
-labeled oriented 0-2-trees.
-\end_layout
-
-\end_body
-\end_document
-- 
cgit v1.2.3