Changed layout for more manageable volumes

1 files changed, 1630 insertions, 0 deletions

diff --git a/vol1/1.3.3.lyx b/vol1/1.3.3.lyx
new file mode 100644
index 0000000..db7c653
--- /dev/null
+++ b/vol1/1.3.3.lyx
@@ -0,0 +1,1630 @@
+#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