Changed layout for more manageable volumes

1 files changed, 0 insertions, 1630 deletions

diff --git a/1.3.3.lyx b/1.3.3.lyx
deleted file mode 100644
index db7c653..0000000
--- a/1.3.3.lyx
+++ /dev/null
@@ -1,1630 +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
-exerc1[02]
-\end_layout
-
-\end_inset
-
-Consider the transformation of 
-\begin_inset Formula $\{0,1,2,3,4,5,6\}$
-\end_inset
-
- that replaces 
-\begin_inset Formula $x$
-\end_inset
-
- by 
-\begin_inset Formula $2x\bmod7$
-\end_inset
-
-.
- Show that this transformation is a permutation,
- and write it in cycle form.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-Being a permutation follows from the fact that 
-\begin_inset Formula $\mathbb{Z}_{7}$
-\end_inset
-
- is a field.
- In cycle form,
- this would be 
-\begin_inset Formula $(1\,2\,4)(3\,6\,5)$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc2[10]
-\end_layout
-
-\end_inset
-
-The text shows how we might set 
-\begin_inset Formula $(a,b,c,d,e,f)\to(c,d,f,b,e,a)$
-\end_inset
-
- by using a series of replacement operations (
-\begin_inset Formula $x\gets y$
-\end_inset
-
-) and one auxiliary variable 
-\begin_inset Formula $t$
-\end_inset
-
-.
- Show how to do the job by using a series of 
-\emph on
-exchange
-\emph default
- operations (
-\begin_inset Formula $x\leftrightarrow y$
-\end_inset
-
-) and no auxiliary variables.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-Since the permutation such that 
-\begin_inset Formula $(a,b,c,d,e,f)\to(c,d,f,b,e,a)$
-\end_inset
-
- such that 
-\begin_inset Formula $x_{i}\to\sigma(x_{i})$
-\end_inset
-
- is 
-\begin_inset Formula $(a\,c\,f)(b\,d)$
-\end_inset
-
-,
- we could use 
-\begin_inset Formula $a\leftrightarrow c,c\leftrightarrow f,b\leftrightarrow d$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc3[03]
-\end_layout
-
-\end_inset
-
-Compute the product 
-\begin_inset Formula ${\small \begin{pmatrix}a & b & c & d & e & f\\
-b & d & c & a & f & e
-\end{pmatrix}}\times{\small \begin{pmatrix}a & b & c & d & e & f\\
-c & d & f & b & e & a
-\end{pmatrix}}$
-\end_inset
-
-,
- and express the answer in two-line notation.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-
-\begin_inset Formula 
-\[
-\begin{pmatrix}a & b & c & d & e & f\\
-d & b & f & c & a & e
-\end{pmatrix}.
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc4[10]
-\end_layout
-
-\end_inset
-
-Express 
-\begin_inset Formula $(a\,b\,d)(e\,f)(a\,c\,f)(b\,d)$
-\end_inset
-
- as a product of disjoint cycles.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-
-\begin_inset Formula $(a\,d\,c\,f\,e)$
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc5[M10]
-\end_layout
-
-\end_inset
-
-Equation (3) shows several equivalent ways to express the same permutation in cycle form.
- How many different ways of writing that permutation are possible,
- if all singleton cycles are suppressed?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-There are 2 cycles which can be ordered in 
-\begin_inset Formula $2!=2$
-\end_inset
-
- different ways,
- and since an 
-\begin_inset Formula $m$
-\end_inset
-
--cycle can be written in 
-\begin_inset Formula $m$
-\end_inset
-
- different ways,
- there are 
-\begin_inset Formula $2!\cdot2\cdot3=12$
-\end_inset
-
- possible ways to write the permutation in cycle form.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc7[10]
-\end_layout
-
-\end_inset
-
-If Program A is presented with the input (6),
- what are the quantities 
-\begin_inset Formula $X$
-\end_inset
-
-,
- 
-\begin_inset Formula $Y$
-\end_inset
-
-,
- 
-\begin_inset Formula $M$
-\end_inset
-
-,
- 
-\begin_inset Formula $N$
-\end_inset
-
-,
- 
-\begin_inset Formula $U$
-\end_inset
-
-,
- and 
-\begin_inset Formula $V$
-\end_inset
-
- of (19)?
- What is the time required by Program A,
- excluding input-output?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-
-\begin_inset Formula $X$
-\end_inset
-
- is the number of cards of input,
- namely 
-\begin_inset Formula $\lceil30/24\rceil=2$
-\end_inset
-
- if no space is added;
- then 
-\begin_inset Formula $Y=29$
-\end_inset
-
-.
- 
-\begin_inset Formula $M=5$
-\end_inset
-
-,
- the number of cycles in input,
- and 
-\begin_inset Formula $N=7$
-\end_inset
-
-,
- the number of different elements.
- Then,
- since the output is 
-\begin_inset Formula $(a\,d\,g)(c\,e\,b)(f)$
-\end_inset
-
-,
- 
-\begin_inset Formula $U=3$
-\end_inset
-
-,
- the number of cycles in the output,
- and 
-\begin_inset Formula $V=1$
-\end_inset
-
-,
- the number of singleton cycles.
-\end_layout
-
-\begin_layout Standard
-Then the time required,
- excluding input-output,
- is
-\begin_inset Formula 
-\begin{multline*}
-112NX+304X-2M-Y+11U+2V-11=\\
-=112\cdot7\cdot2+304\cdot2-2\cdot5-29+11\cdot3+2\cdot1-11=2161u.
-\end{multline*}
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc8[23]
-\end_layout
-
-\end_inset
-
-Would it be feasible to modify Algorithm B to go from left to right instead of from right to left through the input?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-Yes,
- if we're allowed to use an extra step for inverting the result.
- For this algorithm,
- we use an auxiliary table 
-\begin_inset Formula $U[1],\dots,U[n]$
-\end_inset
-
- where we obtain the inverse of the permutation.
- We calculate it by noticing that 
-\begin_inset Formula $(a_{11}\,\dots\,a_{1m_{1}})\cdots(a_{k1}\,\cdots\,a_{km_{k}})=((a_{km_{k}}\,\dots\,a_{k1})\cdots(a_{1m_{1}}\,\dots\,a_{11}))^{-1}$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-\begin_inset Argument item:1
-status open
-
-\begin_layout Plain Layout
-
-\series bold
-B1.
-\end_layout
-
-\end_inset
-
-[Initialize.] Set 
-\begin_inset Formula $U[k]\to k$
-\end_inset
-
- for 
-\begin_inset Formula $1\leq k\leq n$
-\end_inset
-
-.
- Also,
- prepare to scan the input from left to right.
-\end_layout
-
-\begin_layout Enumerate
-\begin_inset Argument item:1
-status open
-
-\begin_layout Plain Layout
-
-\series bold
-B2.
-\end_layout
-
-\end_inset
-
-[Next element.] Examine the next element of the input.
- If the input has been exhausted,
- go to step B5.
- If the element is a `(',
- set 
-\begin_inset Formula $Z\gets0$
-\end_inset
-
- and repeat step B2;
- if it is a `)',
- go to B4.
- Otherwise the element is 
-\begin_inset Formula $x_{i}$
-\end_inset
-
- for some 
-\begin_inset Formula $i$
-\end_inset
-
-,
- go on to B'3.
-\end_layout
-
-\begin_layout Enumerate
-\begin_inset Argument item:1
-status open
-
-\begin_layout Plain Layout
-
-\series bold
-B3.
-\end_layout
-
-\end_inset
-
-[Change 
-\begin_inset Formula $U[i]$
-\end_inset
-
-.] Exchange 
-\begin_inset Formula $Z\leftrightarrow U[i]$
-\end_inset
-
-.
- If this makes 
-\begin_inset Formula $U[i]=0$
-\end_inset
-
-,
- set 
-\begin_inset Formula $j\gets i$
-\end_inset
-
-.
- Return to step B2.
-\end_layout
-
-\begin_layout Enumerate
-\begin_inset Argument item:1
-status open
-
-\begin_layout Plain Layout
-
-\series bold
-B4.
-\end_layout
-
-\end_inset
-
-[Change 
-\begin_inset Formula $U[j]$
-\end_inset
-
-.] Set 
-\begin_inset Formula $U[j]\gets Z$
-\end_inset
-
-.
- Return to step B2.
-\end_layout
-
-\begin_layout Enumerate
-\begin_inset Argument item:1
-status open
-
-\begin_layout Plain Layout
-
-\series bold
-B5.
-\end_layout
-
-\end_inset
-
-[Invert permutation.] For 
-\begin_inset Formula $1\leq k\leq n$
-\end_inset
-
-,
- set 
-\begin_inset Formula $T[U[i]]\gets i$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc9[10]
-\end_layout
-
-\end_inset
-
-Both Programs A and B accept the same input and give the answer in essentially the same form.
- Is the output 
-\emph on
-exactly
-\emph default
- the same under both programs?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-No.
- For example,
- for input (6),
- Program A produces 
-\begin_inset Formula $(a\,d\,g)(c\,e\,b)(f)$
-\end_inset
-
- while Program B produces 
-\begin_inset Formula $(a\,d\,g)(b\,c\,e)(f)$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc13[M24]
-\end_layout
-
-\end_inset
-
-Prove that Algorithm J is valid.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-We prove it by induction.
- Let 
-\begin_inset Formula $\sigma$
-\end_inset
-
- be the original permutation,
- it's enough to show that,
- when entering step J2,
- or when exiting step J5,
- for each 
-\begin_inset Formula $j\in\{1,\dots,n\}$
-\end_inset
-
-,
- if 
-\begin_inset Formula $\sigma^{-1}(j)>m$
-\end_inset
-
-,
- 
-\begin_inset Formula $X[j]=\sigma^{-1}(j)$
-\end_inset
-
-,
- and otherwise 
-\begin_inset Formula $X[j]=-\sigma^{k+1}(j)$
-\end_inset
-
- where 
-\begin_inset Formula $k$
-\end_inset
-
- is the least nonnegative integer with 
-\begin_inset Formula $\sigma^{k}(j)\leq m$
-\end_inset
-
- (if there were no such number,
- since 
-\begin_inset Formula $\sigma^{-1}(j)=\sigma^{p}(j)$
-\end_inset
-
- for some 
-\begin_inset Formula $p\geq0$
-\end_inset
-
-,
- then it would be 
-\begin_inset Formula $\sigma^{-1}(j)>m$
-\end_inset
-
-).
- 
-\end_layout
-
-\begin_layout Standard
-If we enter J2 from J1,
- every 
-\begin_inset Formula $X[j]<0$
-\end_inset
-
-,
- every 
-\begin_inset Formula $j\leq m=n$
-\end_inset
-
-,
- so 
-\begin_inset Formula $k=1$
-\end_inset
-
- and what we have to prove is that 
-\begin_inset Formula $X[j]=-\sigma(j)$
-\end_inset
-
-,
- which obviously holds.
- Now,
- provided that this holds when we enter J2,
- we have to show that it holds when we reach J5 and the proof is complete.
-\end_layout
-
-\begin_layout Standard
-After steps J2 and J3,
- obviously the condition still holds.
- After these steps,
- 
-\begin_inset Formula $i=-\sigma(m)$
-\end_inset
-
- and 
-\begin_inset Formula $j$
-\end_inset
-
- is such that 
-\begin_inset Formula $i=X[j]$
-\end_inset
-
-.
- We prove this by induction,
- showing that,
- after 
-\begin_inset Formula $k\geq1$
-\end_inset
-
- steps,
- 
-\begin_inset Formula $i$
-\end_inset
-
- is either 
-\begin_inset Formula $-\sigma(m)<0$
-\end_inset
-
- or 
-\begin_inset Formula $\sigma^{-k}(m)>0$
-\end_inset
-
-,
- and in the latter case,
- 
-\begin_inset Formula $\sigma^{-k}(m),\sigma^{-k+1}(m),\dots,\sigma^{-1}(m)>m$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-After one iteration,
- 
-\begin_inset Formula $i=X[m]$
-\end_inset
-
-;
- if 
-\begin_inset Formula $i>0$
-\end_inset
-
-,
- 
-\begin_inset Formula $i=\sigma^{-1}(m)>m$
-\end_inset
-
-;
- otherwise 
-\begin_inset Formula $i=-\sigma^{p+1}(m)$
-\end_inset
-
-,
- where 
-\begin_inset Formula $p$
-\end_inset
-
- is the least nonnegative integer with 
-\begin_inset Formula $\sigma^{p}(m)\leq m$
-\end_inset
-
-,
- but since 
-\begin_inset Formula $p=0$
-\end_inset
-
-,
- 
-\begin_inset Formula $i=-\sigma(m)$
-\end_inset
-
-.
- Now assume that this still holds after 
-\begin_inset Formula $k$
-\end_inset
-
- iterations,
- and that 
-\begin_inset Formula $i>0$
-\end_inset
-
- so there's a 
-\begin_inset Formula $(k+1)$
-\end_inset
-
--th iteration.
- Then 
-\begin_inset Formula $j=\sigma^{-k}(m)>0$
-\end_inset
-
- and we assign 
-\begin_inset Formula $X[j]$
-\end_inset
-
- to 
-\begin_inset Formula $i$
-\end_inset
-
-.
- If 
-\begin_inset Formula $i>0$
-\end_inset
-
-,
- 
-\begin_inset Formula $i=\sigma^{-1}(\sigma^{-k}(m))=\sigma^{-k-1}(m)>m$
-\end_inset
-
-;
- otherwise 
-\begin_inset Formula $i=-\sigma^{p+1}(\sigma^{-k}(m))$
-\end_inset
-
-,
- where 
-\begin_inset Formula $p$
-\end_inset
-
- is the least nonnegative integer with 
-\begin_inset Formula $\sigma^{p-k}(m)\leq m$
-\end_inset
-
-,
- but 
-\begin_inset Formula $\sigma^{-k}(m),\dots,\sigma^{-1}(m)>m$
-\end_inset
-
- and 
-\begin_inset Formula $\sigma^{0}(m)=m$
-\end_inset
-
-,
- so 
-\begin_inset Formula $p=k$
-\end_inset
-
- and 
-\begin_inset Formula $i=-\sigma^{k+1}(\sigma^{-k}(m))=-\sigma(m)$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-Now,
- at the beginning of step J4,
- 
-\begin_inset Formula $i=-\sigma(m)$
-\end_inset
-
- and 
-\begin_inset Formula $j$
-\end_inset
-
- is such that,
- if 
-\begin_inset Formula $k$
-\end_inset
-
- is the least nonnegative integer with 
-\begin_inset Formula $\sigma^{k}(j)\leq m$
-\end_inset
-
-,
- then 
-\begin_inset Formula $\sigma^{k+1}(j)=\sigma(m)$
-\end_inset
-
-.
- Then the new value of 
-\begin_inset Formula $X[j]$
-\end_inset
-
- is 
-\begin_inset Formula $X[-i]=X[\sigma(m)]=-\sigma^{p+1}(m)$
-\end_inset
-
-,
- where 
-\begin_inset Formula $p$
-\end_inset
-
- is the least positive integer with 
-\begin_inset Formula $\sigma^{p}(m)\leq m$
-\end_inset
-
-,
- the new value of 
-\begin_inset Formula $X[-i]=X[\sigma(m)]$
-\end_inset
-
- is 
-\begin_inset Formula $m=\sigma^{-1}(\sigma(m))$
-\end_inset
-
- and the new value of 
-\begin_inset Formula $m$
-\end_inset
-
- is 
-\begin_inset Formula $m-1$
-\end_inset
-
-.
- Since 
-\begin_inset Formula $\sigma^{-1}(\sigma(m))>m-1$
-\end_inset
-
-,
- the condition holds for 
-\begin_inset Formula $X[\sigma(m)]=X[-i]$
-\end_inset
-
-:.
- Also,
- 
-\begin_inset Formula $X[j]=-\sigma^{p+1}(m)=-\sigma^{p+k+1}(j)$
-\end_inset
-
-,
- 
-\begin_inset Formula $j,\sigma(j),\dots,\sigma^{k-1}(j),\sigma^{k}(j)=m,\sigma^{k+1}(j)=\sigma(m),\dots,\sigma^{p+k}(j)=\sigma^{p-1}(m)>m-1$
-\end_inset
-
-,
- and because 
-\begin_inset Formula $\sigma^{p+k+1}(j)=\sigma^{p}(m)\leq m$
-\end_inset
-
-,
- and 
-\begin_inset Formula $\sigma^{p}(m)\neq m$
-\end_inset
-
- because otherwise it would be either 
-\begin_inset Formula $p\leq k$
-\end_inset
-
- and 
-\begin_inset Formula $\sigma^{k-p}(j)=m\#$
-\end_inset
-
-,
- or 
-\begin_inset Formula $p>k$
-\end_inset
-
- and 
-\begin_inset Formula $\sigma^{p}(j)=\sigma^{p-k}(m)=j\leq m\#$
-\end_inset
-
-,
- then we have 
-\begin_inset Formula $\sigma^{p+k+1}(j)=\sigma^{p}(m)\leq m-1$
-\end_inset
-
-,
- and the condition holds for 
-\begin_inset Formula $X[j]$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-Now the only thing left to prove is that step J3 always ends,
- for which it suffices to prove that the cycle that 
-\begin_inset Formula $m$
-\end_inset
-
- is in contains an element 
-\begin_inset Formula $t$
-\end_inset
-
- with 
-\begin_inset Formula $X[t]<0$
-\end_inset
-
-,
- which happens if and only if it contains a 
-\begin_inset Formula $t$
-\end_inset
-
- with 
-\begin_inset Formula $\sigma^{-1}(t)\leq m$
-\end_inset
-
-,
- if and only if there's an element not greater than 
-\begin_inset Formula $m$
-\end_inset
-
-,
- but 
-\begin_inset Formula $m$
-\end_inset
-
- is such an element.
-\end_layout
-
-\begin_layout Standard
-\begin_inset Note Note
-status open
-
-\begin_layout Plain Layout
-TODO 26,
- 34
-\end_layout
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc26[M24]
-\end_layout
-
-\end_inset
-
-Extend the principle of inclusion and exclusion to obtain a formula for the number of elements that are in exactly 
-\begin_inset Formula $r$
-\end_inset
-
- of the subsets 
-\begin_inset Formula $S_{1},S_{2},\dots,S_{M}$
-\end_inset
-
-.
- (The text considers only the case 
-\begin_inset Formula $r=0$
-\end_inset
-
-.)
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-For the sake of abbreviation,
- let 
-\begin_inset Formula $E_{r}$
-\end_inset
-
- be the number of elements that are exactly in 
-\begin_inset Formula $r$
-\end_inset
-
- of the subsets and let
-\begin_inset Formula 
-\[
-T_{r}\coloneqq\sum_{1\leq j_{1}<\dots<j_{r}\leq M}|S_{j_{1}}\cap\dots\cap S_{j_{r}}|,
-\]
-
-\end_inset
-
-so that 
-\begin_inset Formula $T_{0}=N$
-\end_inset
-
- (we use the convention that the intersection of no subsets is the intended 
-\begin_inset Quotes eld
-\end_inset
-
-domain
-\begin_inset Quotes erd
-\end_inset
-
- set),
- 
-\begin_inset Formula $T_{M}=|S_{1}\cap\dots\cap S_{M}|$
-\end_inset
-
-,
- and for 
-\begin_inset Formula $r>M$
-\end_inset
-
-,
- 
-\begin_inset Formula $T_{r}=0$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-Obviously 
-\begin_inset Formula $E_{r}=0$
-\end_inset
-
- for 
-\begin_inset Formula $r>M$
-\end_inset
-
-,
- and 
-\begin_inset Formula $E_{M}=T_{M}$
-\end_inset
-
-.
- After calculating 
-\begin_inset Formula $E_{M-1}$
-\end_inset
-
- and 
-\begin_inset Formula $E_{M-2}$
-\end_inset
-
-,
- we formulate the hypothesis that
-\begin_inset Formula 
-\[
-E_{r}=\sum_{k=r}^{M}(-1)^{k-r}\binom{k}{r}T_{k}
-\]
-
-\end_inset
-
-for 
-\begin_inset Formula $0\leq r\leq M$
-\end_inset
-
-,
- which matches what we know about 
-\begin_inset Formula $E_{M}$
-\end_inset
-
- and 
-\begin_inset Formula $E_{0}$
-\end_inset
-
-.
- We prove this by induction from 
-\begin_inset Formula $r=M$
-\end_inset
-
- to 0.
- We have already established the base case.
- For 
-\begin_inset Formula $r<M$
-\end_inset
-
-,
- we start by pointing out that,
- for 
-\begin_inset Formula $r\leq k\leq M$
-\end_inset
-
-,
- 
-\begin_inset Formula $T_{r}$
-\end_inset
-
- counts the elements that appear exactly 
-\begin_inset Formula $k$
-\end_inset
-
- times a total of 
-\begin_inset Formula $\binom{k}{r}$
-\end_inset
-
- times,
- corresponding to choosing the 
-\begin_inset Formula $r$
-\end_inset
-
- indexes from those 
-\begin_inset Formula $k$
-\end_inset
-
- indexes that contain the element.
- Thus 
-\begin_inset Formula $T_{r}=\sum_{k=r}^{M}\binom{k}{r}E_{k}$
-\end_inset
-
-,
- so
-\begin_inset Formula 
-\begin{align*}
-E_{r} & =T_{r}-\sum_{k=r+1}^{M}\binom{k}{r}E_{k}=T_{r}-\sum_{k=r+1}^{M}\binom{k}{r}\sum_{j=k}^{M}(-1)^{j-k}\binom{j}{k}T_{j}\\
- & =T_{r}-\sum_{j=r+1}^{M}\left(\sum_{k=r+1}^{j}(-1)^{j-k}\binom{j}{k}\binom{k}{r}\right)T_{j},
-\end{align*}
-
-\end_inset
-
-but by Eq.
- 1.2.6–(23),
-\begin_inset Formula 
-\[
-\sum_{k=r+1}^{j}(-1)^{j-k}\binom{j}{k}\binom{k}{r}=\sum_{k=r}^{j}(-1)^{j-k}\binom{j}{k}\binom{k}{r}-(-1)^{j-r}\binom{j}{r}=\cancel{\binom{0}{r-j}}^{=0}-(-1)^{j-r}\binom{j}{r},
-\]
-
-\end_inset
-
-and so
-\begin_inset Formula 
-\[
-E_{r}=T_{r}+\sum_{j=r+1}^{M}(-1)^{j-r}\binom{j}{r}T_{j}=\sum_{j=r}^{M}(-1)^{j-r}\binom{j}{r}T_{j}.
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc34[M25]
-\end_layout
-
-\end_inset
-
-(
-\emph on
-Transposing blocks of data.
-\emph default
-) One of the most common permutations needed in practice is the change from 
-\begin_inset Formula $\alpha\beta$
-\end_inset
-
- to 
-\begin_inset Formula $\beta\alpha$
-\end_inset
-
-,
- where 
-\begin_inset Formula $\alpha$
-\end_inset
-
- and 
-\begin_inset Formula $\beta$
-\end_inset
-
- are substrings of an array.
- In other words,
- if 
-\begin_inset Formula $x_{0}x_{1}\dots x_{m-1}=\alpha$
-\end_inset
-
- and 
-\begin_inset Formula $x_{m}x_{m+1}\dots x_{m+n-1}=\beta$
-\end_inset
-
-,
- we want to change the array 
-\begin_inset Formula $x_{0}x_{1}\dots x_{m+n-1}=\alpha\beta$
-\end_inset
-
- to the array 
-\begin_inset Formula $x_{m}x_{m+1}\dots x_{m+n-1}x_{0}x_{1}\dots x_{m-1}=\beta\alpha$
-\end_inset
-
-;
- each element 
-\begin_inset Formula $x_{k}$
-\end_inset
-
- should be replaced by 
-\begin_inset Formula $x_{p(k)}$
-\end_inset
-
- for 
-\begin_inset Formula $0\leq k<m+n$
-\end_inset
-
-,
- where 
-\begin_inset Formula $p(k)=(k+m)\bmod(m+n)$
-\end_inset
-
-.
- Show that every such 
-\begin_inset Quotes eld
-\end_inset
-
-cyclic-shift
-\begin_inset Quotes erd
-\end_inset
-
- permutation has a simple cycle structure,
- and exploit that structure to device a simple algorithm for the desired rearrangement.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-Let 
-\begin_inset Formula $d\coloneqq\gcd\{m,n\}$
-\end_inset
-
-,
- then 
-\begin_inset Formula $p=C_{0}C_{1}\cdots C_{d-1}$
-\end_inset
-
- where
-\begin_inset Formula 
-\[
-C_{j}\coloneqq(j\,(m+j)\,(2m+j)\,\dots\,((\tfrac{n}{d}-1)m+j))\pmod n.
-\]
-
-\end_inset
-
-Effectively,
- each of the cycles above contains only elements with the same value modulo 
-\begin_inset Formula $d$
-\end_inset
-
-,
- so the cycles are disjoint,
- and for any 
-\begin_inset Formula $k\in\{0,\dots,n-1\}$
-\end_inset
-
-,
- let 
-\begin_inset Formula $p$
-\end_inset
-
- and 
-\begin_inset Formula $q$
-\end_inset
-
- be the quotient and remainder of 
-\begin_inset Formula $k/d$
-\end_inset
-
- and 
-\begin_inset Formula $am+bn=d$
-\end_inset
-
- be a Bézout identity,
- then
-\begin_inset Formula 
-\[
-k=pd+q=pam+pbn+q\equiv pam+q\equiv(pa\bmod n/d)m\pmod n.
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-We can use this in the following algorithm.
-\end_layout
-
-\begin_layout Standard
-
-\series bold
-Algorithm T.
-
-\series default
- (
-\emph on
-Transpose blocks of data.
-\emph default
-)
-\end_layout
-
-\begin_layout Enumerate
-[Initialize.] Set 
-\begin_inset Formula $d\gets m$
-\end_inset
-
-,
- 
-\begin_inset Formula $N\gets m+n$
-\end_inset
-
-,
- and 
-\begin_inset Formula $j\gets-1$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-[Calculate 
-\begin_inset Formula $d$
-\end_inset
-
-.] Set 
-\begin_inset Formula $n\gets n\bmod d$
-\end_inset
-
-.
- If 
-\begin_inset Formula $n\neq0$
-\end_inset
-
-,
- set 
-\begin_inset Formula $d\leftrightarrow n$
-\end_inset
-
- and repeat this step.
-\end_layout
-
-\begin_layout Enumerate
-[Set up cycle.] Increment 
-\begin_inset Formula $j$
-\end_inset
-
- by 1.
- If 
-\begin_inset Formula $j=d$
-\end_inset
-
-,
- terminate the algorithm.
- Otherwise set 
-\begin_inset Formula $k\gets j$
-\end_inset
-
- and 
-\begin_inset Formula $s\gets x_{j}$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-[Iterate.] Set 
-\begin_inset Formula $l\gets(k+m)\bmod(m+n)$
-\end_inset
-
-.
- If 
-\begin_inset Formula $l=j$
-\end_inset
-
-,
- set 
-\begin_inset Formula $x_{k}\gets s$
-\end_inset
-
- and go to the previous step.
- Otherwise set 
-\begin_inset Formula $x_{k}\gets x_{l}$
-\end_inset
-
-,
- 
-\begin_inset Formula $k\gets l$
-\end_inset
-
-,
- and repeat this step.
-\end_layout
-
-\end_body
-\end_document