#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