formelblad-mse.tex

\documentclass[a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage{mathtools,graphicx,amssymb}
\usepackage{array}   % nicer tables

% instead of \usepackage{fullpage} <<<
\advance \topmargin by -4.5\headheight
\advance \textheight by 125pt
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.6in
\parindent=0pt
\advance\parskip by 1pt
% >>>

\pagestyle{headings}
\everymath{\textstyle}

%-------------
%- LaTeX def's
%-------------

\everymath{\displaystyle}

% Header matter %<<<
\makeatletter
\renewcommand{\@oddhead}{}
\renewcommand{\@evenhead}{}
\renewcommand{\@oddfoot}
{\ifnum\thepage=1
  \today\hfill file:~\small\texttt{\jobname.pdf}
\else
  Math for Soft Eng Formula Sheet
  \hfill
  \Tr{p}{s}.~\thepage{} \Tr{of}{av} \pageref{LastPageNo}
\fi}

  \renewcommand{\@evenfoot}{\small
        \texttt{\jobname.pdf},\hfill}
\makeatother%>>>

\input ../bz/StdLaTeXdef.h

\begin{document}


\section*{MSE Formula Sheet}

All parameters, if nothing else specified, assumed in $\Zone$;
notation used: $[a]_n \iff a\; (\mbox{mod } n)$.

\vspace{-10pt}

\subsubsection*{Generating functions:} \vspace{-1.2em}%<<<
\[
  \begin{array}[t]{|ll|ll|}
    \hline
    &&& \\[-9pt]
    \mbox{Geometirc sum:} & 1+t+\cdots+t^n = \frac{1-t^{n+1}}{1-t} &
    \mbox{Geometirc series:} & 1+t+t^2+\cdots = \frac{1}{1-t}
    \\[7pt]\hline
    &&& \\[-9pt]
    \multicolumn{2}{|l|}{(1+t)^n = \sum_{r=0}^{n} \binom nr t^r, \; \binom nr = \frac{n!}{r!(n-r)!}} &
    \multicolumn{2}{l|}{(1-t)^{-n} = \sum_{r=0}^{\infty} \binom {-n}r (-t)^r = \sum_{r=0}^{\infty}\binom {n-1+r}r t^r}
    \\[11pt]\hline
    &&& \\[-9pt]
    \multicolumn{2}{|l|}{e^t = \sum_{k=0}^{\infty} \frac{t^k}{k!} =  1 + \frac{t}{1!} + \frac{t^2}{2!} + \cdots}&
    \multicolumn{2}{l|}{\ln(1+t) = \sum_{k=1}^{\infty}(-1)^{k+1}\frac{t^k}{k} =  t - \frac{t^2}{2} + \frac{t^3}{3} - \cdots}
    \\[11pt]\hline

  \end{array}
\]%>>>

\subsubsection*{Greatest common divisor, least common multiple:} \vspace{-1.2em}%<<<
\[
  \begin{array}[t]{|*{3}{l|}}
    \hline
    && \\[-8pt]
    m\perp n \iff \gcd(m,n)=1 & \gcd(m,n) = d \iff \frac md\perp\frac nd & \gcd(m,n)\,\mbox{lcm}(m,n) = mn
 \\[6pt] \hline
  \end{array}
\]%>>>

\subsubsection*{Sets:} \vspace{-2.5em} %<<<
\[
  \begin{array}[t]{|*{3}{l|}}
 \hline
    && \\[-8pt]
   n\Zone = \{0,\pm n,\pm 2n,\ldots \}
 & Z_n,\Zone/n\Zone = \{[0]_n,[1]_n,\ldots,[n-1]_n\}
 & Z_n^* = \{[1]_n,\ldots,[n-1]_n\} \\[6pt]
   \Rone - \mbox{the reals}
 & \Zone^* = \Zone\setminus\{0\},\;
   \Rone^* = \Rone\setminus\{0\},\;
   \Cone^* = \Cone\setminus\{0\}
 & U_n = \{k\in\Zone_n: k\perp n\}
 \\[3pt] \hline
  \end{array}
\]%>>>

\textbf{Groups:}%<<<
\vspace{-15pt}
\[
  \begin{array}[t]{|l|l|}
    \hline
    \rule{0pt}{10pt}
     \Zone_n := (\Zone_n,+_n) \text{  -- $\Zone_n$ under summation mod $n$}
    &  U_n := (U_n,\cdot_n) \text{  -- $U_n$ under multiplication mod $n$}
    \\\hline
    \rule{0pt}{10pt}
    C_n = \langle a\rangle = \{e,a,a^2,\ldots,a^{n-1}\} \text{ -- the cyclic group}
    & GL_n = \{A_{n\times n} \,|\, \det(A)\neq 0 \text{ -- the general linear group}
    \\ \hline
    \multicolumn{2}{|l|}{%
    \text{Product groups: } G\times H = \{(g,h)\,|\, g\in G, h\in H\}, \;
    \text{ multiplication: }
    (g,h)\circ(g',h')\defeq (g\circ_Gg', h\circ_H h')
  } % multicolumn
    \cr\hline
  \end{array}
\]%>>>

\subsubsection*{Arithmetic mod $n$:} \vspace{-1.2em} %<<<
\[
  \begin{array}[t]{|*{4}{l|}}
    \hline
    &&& \\[-8pt]
    [a+b]_n = [[a]_n + [b]_n]_n &
    [ab]_n = [[a]_n[b]_n]_n &
    [ka]_{kn} = k [a]_n &
    \mbox{Euler: }a\perp n \ergo [a^{\varphi(n)}]_n = 1
    \\[3pt] \hline
  \end{array}
\]%>>>

\textbf{Euler totient}: %<<<
\begin{tabular}[m]{|l|l|l|}
  \hline
  \rule{0pt}{16pt}
  $\varphi(n)=|U_n|=n\prod_{p\,|\,n}\Bigl(1-\frac1p\Bigr)$ &
  $\phi(p^k)=(p-1)p^{k-1}$, $p$--prime &
  $\varphi(st)=\varphi(s)\varphi(t)$, $s\perp t$ \cr
  \hline
\end{tabular}%>>>

\subsubsection*{Solve Bézout \fbox{$mx\pm ny=1$, $m\perp n$} (find inverse in $U_n$) %<<<
by row red.~in Euklides extended:}
\[
  \boxed{
  m\perp n \ergo
  \begin{pmatrix}
    m \BAR 1 & 0 \cr
    n \BAR 0 & 1 \cr
  \end{pmatrix}
  \sim \{\mbox{row op.}\} \sim
  \begin{pmatrix}
    1 \BAR m & -n \cr
    0 \BAR -y & x \cr
  \end{pmatrix}
  \iff
  mx-ny=1
  \iff
  \begin{cases}
  \hfill  x = m^{-1}   & \text{in }\, U_n \cr
   -y = n^{-1} & \text{in }\, U_m \cr
%    [mx]_n    &=1 \cr
%    [(-n)y]_m &= 1.
  \end{cases}
}
\]%>>>

\subsubsection*{Concurrent congruences/The Chinese Remainder Theorem}%<<<
\[
  \boxed{
  \left\{
  \begin{array}{ll}
    [x]_{n_j} = [r_j],& j=1,\cdots,k \\[2pt]
  \hfil n_i\perp n_j ,& 1\le i\neq j\le k
  \end{array}\right.
\;\iff\;
x = \Bigl[ \sum_{j=1}^{k} r_jN_j[N_j^{-1}]_{n_j} \Bigr]_n, \; N_j= \frac{n}{n_j}, \,
    n=n_1\cdots n_k.
  }
\]%>>>

\subsubsection*{Automorphisms $S_X$ of a set $X$; $S_n$ %<<<
  -- the groups of permutations of $\{0,1,\ldots,n-1\}$}


Any finite set $X=\{x_1,\ldots,x_n\}$ gives rise to the group of its
permutations \, $\text{Sym}(X)=S_X\cong S_n$ under composition.
Fixed elements in DCF are most often ommitted, e.g., the unit element in $S_n$, $e=()$, $\forall n$.

\medskip
  \textbf{Notation} for permutations in $S_n$:
  \begin{tabular}[m]{|l|l|}
    \hline
     & \\[-10pt]
    Two-line notation: & Disjoint cycle form (DCF): \cr \hline
     & \\[-9pt]
    $
    \alpha =
    \begin{pmatrix}
      0 & 1 & 2 & 3 & 4 & 5 \cr
      5 & 4 & 0 & 3 & 1 & 2 \cr
    \end{pmatrix} \in S_6
    $
    &
    $
    \begin{array}[m]{ll}
    \alpha
    &= (0,5,2)(1,4)(3)\cr
    &= (0,5,2)(1,4)
    \end{array}
    $
    \\[9pt]\hline
  \end{tabular}
\begin{center}
  \begin{tabular}[m]{|l|l|}
    \hline
     & \\[-10pt]
    Left group  action on a set (list): & Multiplication (right-to-left) : \cr \hline
     & \\[-9pt]
    $
     (0,5,2)(1,4)[a,b,c,d,e,f]
             =   [f,e,a,d,b,c]
    $
    &
    $
    \begin{array}[m]{l}
     \alpha\circ\beta = (0,5,2)(1,4)\circ(0,4) = (0,1,4,5,2) \cr
     \beta\circ\alpha = (0,4)\circ(0,5,2)(1,4) = (0,5,2,4,1)
    \end{array}
    $
    \\[1pt]\hline
  \end{tabular}
\end{center}%>>>

\label{LastPageNo}
\end{document}

% vim: foldmethod=marker spelllang=en