\documentclass[10pt  ]{article}

\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{verbatim}
\hypersetup{breaklinks=true,
pagecolor=white,
colorlinks=true,
linkcolor= blue,
hyperfootnotes= true,
urlcolor=blue
}
\urlstyle{rm}

 

\newcommand{\margincomment}[1]
  {\mbox{}\marginpar{\tiny\hspace{0pt}#1}}

\newcommand{\comments}[1]{}
\renewcommand{\baselinestretch}{1.2}
 \parindent 24pt
 \parskip 10pt
\reversemarginpar
%\topmargin -1in \oddsidemargin -.5in \evensidemargin -.5in
 \textheight 10.5in
 %\textwidth 7.3in


\begin{document}
 

\vspace*{12pt}

\begin{center}
{\large {\bf   Permutations }}
\end{center}
 
 


\noindent
{\bf Definition 1.} A permutation is an ordered arrangement of K objects. For example, ABC and ACB are permutations of the  objects A, C, and B. 

 

\noindent
{\bf Definition 2.} For number $N$, we define $N$ Factorial, also called ``the factorial of $N$''   as $N\cdot (N-1)\cdot (N-2)\cdot \ldots 3\cdot 2\cdot 1$. For example 
$4! = 4\cdot 3 \cdot 3\cdot 2\cdot 1= 24$.  We define 0! as 1, because in advanced math that turns out to make things simpler sometimes


 (see
 \href{https://en.wikipedia.org/wiki/Empty_product}{https://en.wikipedia.org/wiki/Empty\_product}), and it is hard to know whether to define  an empty set, $\{ \}$,  as having 1  permutation or 0  permutations.  Is there one way to arrange nothing, or no way? 

\noindent
{\bf Symbols.}  The Greek letter for the ``A''  sound, is Alpha: $\alpha$  as a small letter and A as a capital. See ``I am Alpha and Omega, the beginning and the end, the first and the last,'' in  Revelation 22:18.  The Greek letter for the ``O''  sounds is Omega: $\omega$ as a small letter and $\Omega$ as a capital. Omega is the last letter of the Greek alphabet, the way they arrange it. They also had a letter Omicron:  $o,  O$ for ``O'' that is the same as our ``O''. 

 

\noindent
{\bf Proposition 1.}  There are 6 permutations of the letters $\{A, B, C\}$. \\
\noindent
{\bf Proof.} There are three ways to start the permutation: A, B, and C. For each of these, there are two ways to choose the second letter (e.g., for A first, B or C can be second). Then there is one letter left that can be used for the third letter. Thus there are $3\cdot 2 = 6 $ ways to arrange the the three letters, which is what it means to permute them. Q.E.D.

A diagram is helpful for this. 
\vspace{72pt}

\noindent
{\bf Proposition 2.}  There are $N!$ permutations of $N$ objects.\\
\noindent
{\bf Proof.} There are $N$ ways to choose the first object in the permutation.  For each of those, that leaves $N-1$ ways to choose the second object. That leaves $N-2$ ways to choose the third object. This pattern continues until there are 3 ways to choose the 3rd-from-last object, 2 ways to choose the second-from-last, and just 1 way to choose the last one. Thus, there are $N\cdot N-1 \cdot N-2\cdot \ldots 3 \cdot 2 \cdot 1$ permutations, which can be written at $N!$. Q.E.D.

 \newpage

\noindent
{\bf Proposition 3.}  There are $N(N-1) \ldots  (N-K)+1$ permutations of  $K$ objects taken from a set of $N$ objects with no duplicates. \\
\noindent
{\bf Proof.} There are $N$ ways to choose the first object in the permutation.  For each of those, that leaves $N-1$ ways to choose the second object. That leaves $N-2$ ways to choose the third object.  This continues until we have reached the $K$th object.  Thus, there are $N\cdot N-1 \cdot N-2\cdot \ldots N-K+1$ permutations. Q.E.D.


\noindent
{\bf Proposition 4.}  There are $N^K$ permutations of  $K$ objects taken from a set of $N$ objects if duplicates are allowed.  \\
\noindent
{\bf Proof.} There are $N$ ways to choose the first object in the permutation.  For each of those,  there are still $N$ ways to choose the second object, since duplicates are allowed. Then there are $N $ ways to choose the third object.  This continues until we have reached the $K$th object.  Thus, there are $N\cdot N \cdot N \ldots N $ with $N$ repeated $K$ times  permutations, which is $N^K$. Q.E.D.
     

 \end{document}
