\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{cancel}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, April 10, 2026 16:26:24}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
\usetikzlibrary{shapes.geometric, arrows.meta, fit, positioning, decorations.pathreplacing}
\tikzset{|/.tip={Bar[width=1ex,round]}}
\newcounter{exer}
\newcounter{rmk}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[rmk]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{udefinition}{\par\medskip\noindent\begin{leftbar}\noindent\textbf{Definition.}\quad}{\end{leftbar}\par\medskip}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand{\iverson}[1]{\left[#1\right]}
\newcommand{\sur}{\operatorname{sur}}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): handwritten notes 2017-11-14}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg):}

\textbf{handwritten notes from the lecture of 14 November 2017}

(digitized using Claude in 2026)

\textbf{Note:} This is \textbf{not} a polished text!
\end{center}

\subsection*{4.2. The Concept of a FPS (continued)}

\begin{definition}
If an FPS $a\in K[\![x]\!]$ has a multiplicative inverse $a^{-1}$, then we can
define $a^{-n}$ for each $n\in\mathbb{N}$ by setting $a^{-n}=(a^{-1})^{n}$. So
the powers $a^{k}$ are defined for all $k\in\mathbb{Z}$.
\end{definition}

\setcounter{theo}{6}

\begin{theorem}
\label{thm.4990-2017nov14.7}The FPS $1-x$ has a multiplicative inverse, which
is%
\[
\dfrac{1}{1-x}=1+x+x^{2}+x^{3}+\cdots\,.
\]

\end{theorem}

\begin{proof}
We have%
\begin{align*}
(1-x)(1+x+x^{2}+x^{3}+\cdots)  &  =(1+x+x^{2}+x^{3}+\cdots)\\
&  \qquad-(x+x^{2}+x^{3}+\cdots)\\
&  =1.
\end{align*}


\textbf{Alternatively:}%
\begin{align*}
(1-x)(1+x+x^{2}+x^{3}+\cdots)  &  =(1-x)+(x-x^{2})+(x^{2}-x^{3})+(x^{3}%
-x^{4})+\cdots\\
&  =1\ \ \ \ \ \ \ \ \ \ \left(  \text{since all the terms other than }1\text{
cancel}\right)  .
\end{align*}

\end{proof}

\setcounter{theo}{7}

\begin{theorem}
\label{thm.4990-2017nov14.8}\textquotedblleft\emph{Newton's binomial
theorem}\textquotedblright: For each $n\in\mathbb{Z}$, we have
\[
(1+x)^{n}=\underbrace{\sum_{k}\dbinom{n}{k}x^{k}}_{\text{This sum is actually
infinite if }n<0}\ .
\]

\end{theorem}

\begin{proof}
[Proof idea]For $n\geq0$, this follows from the regular binomial theorem.

For $n=-1$, this boils down to Theorem~\ref{thm.4990-2017nov14.7} (with $x$
replaced by $-x$).

For $n<-1$, we need the following lemma:
\end{proof}

\setcounter{theo}{8}

\begin{lemma}
\label{lem.4990-2017nov14.9}For any $n\in\mathbb{N}$, we have
\[
(1-x)^{-n}=\sum_{k}\dbinom{n+k-1}{k}x^{k}\ .
\]

\end{lemma}

\begin{proof}
[Proof idea for Lemma~\ref{lem.4990-2017nov14.9}.]Induction over $n$. Need to
check:%
\[
\left(  \sum_{k}\dbinom{n+k-1}{k}x^{k}\right)  \cdot\underbrace{\dfrac{1}%
{1-x}}_{\substack{=\sum\limits_{\ell}x^{\ell}\\\text{(by
Theorem~\ref{thm.4990-2017nov14.7})}}}=\sum_{k}\dbinom{n+k}{k}x^{k}\,.
\]
This easily follows from Pascal's recurrence.
\end{proof}

\medskip\noindent Now, we want to prove Theorem~\ref{thm.4990-2017nov14.8}
using Lemma \ref{lem.4990-2017nov14.9} by substituting $-x$ for $x$. What does
\textquotedblleft substituting\textquotedblright\ mean? We need to define substitution.

\begin{definition}
\label{def.fps.subst}Let $f$ and $g$ be two FPS with $[x^{0}]g=0$. (That is,
$g=g_{1}x+g_{2}x^{2}+\cdots$.) Then, the FPS $f[g]$ is defined as follows:%
\[
\text{Write }f\text{ as }f=\sum_{n\geq0}f_{n}x^{n}\text{, and set }%
f[g]=\sum_{n\geq0}f_{n}g^{n}.
\]


This is well-defined, i.e., the family $(f_{n}g^{n})_{n\in\mathbb{N}}$ is
summable. Instead of giving a formal proof of this fact, we shall show this on
an example:
\end{definition}

\begin{example}
We can substitute $x+x^{2}$ for $x$ into the FPS $\sum_{i\in\mathbb{N}}%
x^{i}=1+x+x^{2}+\cdots$. What we get is%
\begin{align*}
&  \sum_{i\in\mathbb{N}}\left(  x+x^{2}\right)  ^{i}\\
&  =1+(x+x^{2})+\underbrace{(x+x^{2})^{2}}_{=x^{2}+2x^{3}+x^{4}}%
+\underbrace{(x+x^{2})^{3}}_{=x^{3}+3x^{4}+3x^{5}+x^{6}}+\underbrace{(x+x^{2}%
)^{4}}_{=x^{4}+4x^{5}+\cdots}+\cdots.
\end{align*}
As you can see, this infinite sum makes sense: Each addend $\left(
x+x^{2}\right)  ^{i}$ has the form \textquotedblleft$x^{i}$ plus some higher
powers of $x$\textquotedblright, and thus has its first $i$ coefficients equal
to $0$. Thus, for each $n\in\mathbb{N}$, only finitely many $i\in\mathbb{N}$
satisfy $\left[  x^{n}\right]  \left(  \left(  x+x^{2}\right)  ^{i}\right)
\neq0$ (namely, only those $i$ that satisfy $i\leq n$, and not even all of
these). Hence, the family $\left(  \left(  x+x^{2}\right)  ^{i}\right)
_{i\in\mathbb{N}}$ of FPSs is summable, so its sum $\sum_{i\in\mathbb{N}%
}\left(  x+x^{2}\right)  ^{i}$ makes sense.

This is true more generally for the infinite sum $\sum_{n\geq0}f_{n}g^{n}$ in
Definition \ref{def.fps.subst}: The condition $[x^{0}]g=0$ shows that each
addend $f_{n}g^{n}$ has its first $n$ coefficients equal to $0$, and thus the
family $(f_{n}g^{n})_{n\in\mathbb{N}}$ is summable. This shows that $f\left[
g\right]  $ in Definition \ref{def.fps.subst} is well-defined.

Let us actually compute the result of substituting $x+x^{2}$ for $x$ into
$\sum_{i\in\mathbb{N}}x^{i}=1+x+x^{2}+\cdots$ explicitly:
\begin{align*}
&  1+(x+x^{2})+(x+x^{2})^{2}+(x+x^{2})^{3}+(x+x^{2})^{4}+\cdots\\
&  =1+x+2x^{2}+3x^{3}+5x^{4}+8x^{5}+\cdots\\
&  =\sum_{n\geq0}f_{n+1}x^{n}\qquad\text{where }f_{i}\text{ are the Fibonacci
numbers}.
\end{align*}
This is because substituting $x+x^{2}$ for $x$ in the equality $1+x+x^{2}%
+\cdots=\dfrac{1}{1-x}$ yields%
\[
1+(x+x^{2})+(x+x^{2})^{2}+\cdots=\dfrac{1}{1-(x+x^{2})}=\dfrac{1}{1-x-x^{2}%
}=\sum_{n}f_{n+1}x^{n}%
\]
(by Example 1 in \S 4.1).
\end{example}

\setcounter{theo}{9}

\begin{proposition}
\label{prop.4990-2017nov14.10}Substitution satisfies the rules you would
expect: e.g., for any three FPSs $f,g,h$ with $\left[  x^{0}\right]  g=0$ and
$\left[  x^{0}\right]  h=0$, we have%
\[
f[g[h]]=(f[g])[h]\,.
\]
We can restate this as $f\circ(g\circ h)=(f\circ g)\circ h$, where we use the
notation $f\circ g$ for $f[g]$.

(See \cite[\S 7.10]{Loehr-BC} for details.)
\end{proposition}

After a bit of work, this leads to a proof of
Theorem~\ref{thm.4990-2017nov14.8} for $n<-1$, thus concluding the above
proof. This justifies Example~1 in \S 4.1.

\begin{remark}
A \emph{polynomial} is a FPS $(a_{0},a_{1},\ldots)$ such that all but finitely
many $i\in\mathbb{N}$ satisfy $a_{i}=0$.
\end{remark}

To justify Example~2 in \S 4.1, we need to make sense of $(1+x)^{n}$ for
$n\notin\mathbb{Z}$. Here are two ways to do this:

\begin{itemize}
\item \textbf{Option~1:}\quad Define $(1+x)^{n}$ as $\sum_{k}\dbinom{n}%
{k}x^{k}$. (This is what Loehr does in \cite[\S 7.11]{Loehr-BC}.)

But then, we would have to prove all the rules of exponents for these newly
defined powers:%
\begin{align*}
(1+x)^{n}(1+x)^{m}  &  =(1+x)^{n+m},\\
((1+x)^{n})^{m}  &  =(1+x)^{nm},\\
&  \ldots
\end{align*}


\item \textbf{Option~2:}\quad Define $(1+x)^{n}$ as $\exp[n\log(1+x)]$. Here,
$\exp$ and $\log$ are defined by%
\[
\exp=\sum_{n\geq0}\dfrac{1}{n!}x^{n},\qquad\log(1+x)=\sum_{n\geq1}%
\dfrac{(-1)^{n-1}}{n}x^{n}.
\]
Just like Option 1, this option requires lots of things to be proved, but this
is easier; see \cite{logexp} for details.
\end{itemize}

Both options give the same value of $\left(  1+x\right)  ^{n}$. After some
work, Example~2 in \S 4.1 thus becomes justified.

\subsection*{4.3. One more example for the use of generating functions}

Here is another example for how FPSs (actually, polynomials are all we need
here) can be used to prove binomial identities.

Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Start with the obvious identity
$(1-x)(1+x)=1-x^{2}$. Take it to the $n$-th power to get%
\[
\underbrace{(1-x)^{n}}_{=\sum_{k}(-1)^{k}\dbinom{n}{k}x^{k}}%
\ \ \underbrace{(1+x)^{n}}_{=\sum_{k}\dbinom{n}{k}x^{k}}=\underbrace{(1-x^{2}%
)^{n}}_{=\sum_{k}(-1)^{k}\dbinom{n}{k}x^{2k}}\,.
\]
That is,%
\[
\left(  \sum_{k}(-1)^{k}\dbinom{n}{k}x^{k}\right)  \left(  \sum_{k}\dbinom
{n}{k}x^{k}\right)  =\sum_{k}(-1)^{k}\dbinom{n}{k}x^{2k}\,.
\]
Now, take the $x^{m}$-coefficient on both sides to obtain%
\[
\boxed{\sum_{a=0}^{m}(-1)^{a}\dbinom{n}{a}\dbinom{n}{m-a}=\begin{cases}
(-1)^{m/2}\dbinom{n}{m/2}, & \text{if }m\text{ is even;}\\
0, & \text{if }m\text{ is odd.}\end{cases}
}
\]
For example, if $m=n$, then this simplifies to%
\[
\sum_{a=0}^{n}(-1)^{a}\dbinom{n}{a}^{2}=%
\begin{cases}
(-1)^{n/2}\dbinom{n}{n/2}, & \text{if }n\text{ is even;}\\
0, & \text{if }n\text{ is odd.}%
\end{cases}
\]


For more about FPSs and generating functions, see \cite{Loehr-BC},
\cite{Galvin}, \cite{Wilf04}, etc.

\section*{5. Permutations}

We will now give a very short and superficial introduction to the
combinatorics of permutations. See \cite[Chapter 5]{detnotes} for more,
\cite[Chapter 5]{21s} for much more, and \cite{Bona22} for a lot more.

\textbf{Recall:} A permutation of a set $X$ is a bijection $X\rightarrow X$.

\begin{definition}
Given $n\in\mathbb{N}$. Let $S_{n}$ denote the set of all permutations of
$[n]$.
\end{definition}

This set $S_{n}$ is closed under composition and inverses.

\begin{definition}
Let $n\in\mathbb{N}$ and $\sigma\in S_{n}$. The $n$-tuple $[\sigma
(1),\sigma(2),\ldots,\sigma(n)]$ is called the \emph{one-line notation} of
$\sigma$.

(The use of square brackets to demarcate this $n$-tuple is traditional; it
doesn't mean anything. Often, the commas and the brackets are omitted.)
\end{definition}

\begin{statement}
\textbf{Example:} The permutation
\[
\left(  \quad\vcenter{\hbox{\begin{tikzpicture}[scale=2.5]
\node[circle, draw, inner sep=2pt, minimum size=7mm] (1a) at (1, 0) {$1$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (2a) at (2, 0) {$2$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (3a) at (3, 0) {$3$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (4a) at (4, 0) {$4$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (5a) at (5, 0) {$5$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (1b) at (1, -1) {$1$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (2b) at (2, -1) {$2$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (3b) at (3, -1) {$3$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (4b) at (4, -1) {$4$};
\node[circle, draw, inner sep=2pt, minimum size=7mm] (5b) at (5, -1) {$5$};
\draw[->, very thick] (1a) -- node[above, draw=none, inner sep=0pt, font=\footnotesize] {} (4b);
\draw[->, very thick] (2a) -- node[above, draw=none, inner sep=0pt, font=\footnotesize] {} (2b);
\draw[->, very thick] (3a) -- node[above, draw=none, inner sep=0pt, font=\footnotesize] {} (1b);
\draw[->, very thick] (4a) -- node[above, draw=none, inner sep=0pt, font=\footnotesize] {} (3b);
\draw[->, very thick] (5a) -- node[above, draw=none, inner sep=0pt, font=\footnotesize] {} (5b);
\end{tikzpicture}
}} \quad\right)  \in S_{5}%
\]
is written in one-line notation as $[4,2,1,3,5]$, or, for short, as $42135$.
\end{statement}

\setcounter{theo}{0}

\begin{proposition}
\label{prop.4990-2017nov14.5.1}Let $n\in\mathbb{N}$. Then, the map%
\begin{align*}
S_{n}  &  \rightarrow\lbrack n]_{\operatorname*{dist}}^{n}=\{n\text{-tuples of
distinct elements of }[n]\},\\
\sigma &  \mapsto\lbrack\sigma(1),\sigma(2),\ldots,\sigma(n)]=\left(
\text{one-line notation of }\sigma\right)
\end{align*}
is a bijection.
\end{proposition}

\begin{proof}
Pigeonhole principle / box principle / \textquotedblleft doocot
principle\textquotedblright.
\end{proof}

\begin{definition}
\ \ 

\begin{enumerate}
\item[\textbf{(a)}] Let $i,j$ be distinct elements of $[n]$. Then, the
\emph{transposition} $t_{i,j}\in S_{n}$ is the permutation that sends $i$ to
$j$, sends $j$ to $i$, and leaves everything else in its place. In one-line
notation,%
\[
t_{i,j} = [1,2,\ldots,i-1,\,j,\,i+1,\ldots,j-1,\,i,\,j+1,\ldots,n]\qquad
\text{for }i<j.
\]


\item[\textbf{(b)}] For each $i\in[n-1]$, set $s_{i}=t_{i,i+1}$.
\end{enumerate}
\end{definition}

\begin{statement}
\textbf{Example.} The cycle digraph of $t_{i,j}$ is%
\[
\begin{tikzpicture}[>=Stealth, thick, every node/.style={circle, draw,
inner sep=2pt, minimum size=6mm}]
\node (i) at (-2,0) {$i$};
\node (j) at (0,0) {$j$};
\draw[->] (i) to[bend left=30] (j);
\draw[->] (j) to[bend left=30] (i);
\node (k1) at (2,0) {};
\node (k2) at (4,0) {};
\node (k3) at (6,0) {};
\node[draw=white, fill=white] (k4) at (8,0) {$\cdots$};
\node (k5) at (10,0) {};
\draw[->] (k1) to[loop, looseness=10] (k1);
\draw[->] (k2) to[loop, looseness=10] (k2);
\draw[->] (k3) to[loop, looseness=10] (k3);
\draw[->] (k5) to[loop, looseness=10] (k5);
\end{tikzpicture}
\]
(with self-loops on all the elements other than $i$ and $j$).
\end{statement}

\setcounter{theo}{1}

\begin{proposition}
\label{prop.4990-2017nov14.5.2}We have the following:

\begin{enumerate}
\item[\textbf{(a)}] We have $s_{i}^{2}=\operatorname{id}$ for all $i\in\left[
n-1\right]  $.

\item[\textbf{(b)}] We have $s_{i}\circ s_{j}=s_{j}\circ s_{i}$ for all
$i,j\in\left[  n-1\right]  $ satisfying $|i-j|>1$.

\item[\textbf{(c)}] We have $s_{i}\circ s_{i+1}\circ s_{i}=s_{i+1}\circ
s_{i}\circ s_{i+1}=t_{i,i+2}$ for all $i\in\left[  n-2\right]  $.
\end{enumerate}
\end{proposition}

\begin{proof}
Just compare how both sides act on a given $k\in\left[  n\right]  $.
\end{proof}

\begin{definition}
Let $w_{0}$ be the permutation in $S_{n}$ sending each $i$ to $n+1-i$. In
other words, it \textquotedblleft reflects\textquotedblright\ numbers across
the midpoint of $[n]$. It is the unique strictly decreasing permutation of
$[n]$.
\end{definition}

\begin{statement}
\textbf{Example.} If $n=5$, then $w_{0}=[5,4,3,2,1]$, with cycle digraph%
\[
\begin{tikzpicture}[>=Stealth, thick, every node/.style={circle, draw,
inner sep=2pt, minimum size=6mm}]
\node (i) at (-2,0) {$1$};
\node (j) at (0,0) {$5$};
\draw[->] (i) to[bend left=30] (j);
\draw[->] (j) to[bend left=30] (i);
\node (2) at (2,0) {$2$};
\node (4) at (4,0) {$4$};
\draw[->] (2) to[bend left=30] (4);
\draw[->] (4) to[bend left=30] (2);
\node (3) at (6,0) {$3$};
\draw[->] (3) to[loop, looseness=10] (3);
\end{tikzpicture}\ \ .
\]


If $n=6$, then $w_{0}=[6,5,4,3,2,1]$, with cycle digraph%
\[
\begin{tikzpicture}[>=Stealth, thick, every node/.style={circle, draw,
inner sep=2pt, minimum size=6mm}]
\node (i) at (-2,0) {$1$};
\node (j) at (0,0) {$6$};
\draw[->] (i) to[bend left=30] (j);
\draw[->] (j) to[bend left=30] (i);
\node (2) at (2,0) {$2$};
\node (5) at (4,0) {$5$};
\draw[->] (2) to[bend left=30] (5);
\draw[->] (5) to[bend left=30] (2);
\node (3) at (6,0) {$3$};
\node (4) at (8,0) {$4$};
\draw[->] (3) to[bend left=30] (4);
\draw[->] (4) to[bend left=30] (3);
\end{tikzpicture}\ \ .
\]

\end{statement}

\begin{definition}
For any $k$ distinct elements $i_{1},i_{2},\ldots,i_{k}$ of $[n]$, let
$\operatorname*{cyc}\nolimits_{i_{1},\ldots,i_{k}}$ be the permutation in
$S_{n}$ sending%
\[
i_{1}\mapsto i_{2},\qquad i_{2}\mapsto i_{3},\qquad\ldots,\qquad
i_{k-1}\mapsto i_{k},\qquad i_{k}\mapsto i_{1},
\]
and leaving all other numbers in place.
\end{definition}

\begin{statement}
\textbf{Eaxmple.} The cycle digraph of $\operatorname*{cyc}{}_{3,5,6}\in
S_{7}$ is%
\[
\begin{tikzpicture}[>=Stealth, thick, every node/.style={circle, draw,
inner sep=2pt, minimum size=6mm}]
\node (3) at (120:1.5) {$3$};
\node (6) at (240:1.5) {$6$};
\node (5) at (0:1.5) {$5$};
\draw[->] (3) to[bend left=30] (5);
\draw[->] (5) to[bend left=30] (6);
\draw[->] (6) to[bend left=30] (3);
\node (1) at (4,0) {$1$};
\draw[->] (1) to[loop, looseness=10] (1);
\node (2) at (6,0) {$2$};
\draw[->] (2) to[loop, looseness=10] (2);
\node (4) at (8,0) {$4$};
\draw[->] (4) to[loop, looseness=10] (4);
\node (7) at (10,0) {$7$};
\draw[->] (7) to[loop, looseness=10] (7);
\end{tikzpicture}\ \ .
\]

\end{statement}

Here are some formulas for the permutations we have defined:

\setcounter{theo}{2}

\begin{proposition}
\label{prop.4990-2017nov14.5.3}\ \ 

\begin{enumerate}
\item[\textbf{(a)}] We have
\[
\operatorname*{cyc}{}_{i_{1},i_{2},\ldots,i_{k}}=t_{i_{1},i_{2}}\circ
t_{i_{2},i_{3}}\circ\cdots\circ t_{i_{k-1},i_{k}}%
\]
for any distinct $i_{1},i_{2},\ldots.,i_{k}$.

\item[\textbf{(b)}] We have
\[
\operatorname*{cyc}{}_{i,i+1,\ldots,i+k-1}=s_{i}\circ s_{i+1}\circ\cdots\circ
s_{i+k-2}%
\]
for all $i\in\left[  n\right]  $ and $k\in\left[  n-i+1\right]  $.

\item[\textbf{(c)}] We have%
\begin{align*}
w_{0}  & =s_{1}\circ(s_{2}s_{1})\circ(s_{3}s_{2}s_{1})\circ\cdots\circ
(s_{n-1}s_{n-2}\cdots s_{1})\\
& =\left(  s_{1}s_{2}\cdots s_{n-1}\right)  \circ\left(  s_{1}s_{2}\cdots
s_{n-2}\right)  \circ\cdots\circ\left(  s_{1}s_{2}\right)  \circ s_{1}.
\end{align*}


[Here and in the following, $\alpha\beta$ or $\alpha\cdot\beta$ means
$\alpha\circ\beta$ when $\alpha,\beta\in S_{n}$.]

\item[\textbf{(d)}] If $1\leq i<j\leq n$, then
\begin{align*}
t_{i,j}  & =s_{i}s_{i+1}\cdots s_{j-2}s_{j-1}s_{j-2}\cdots s_{i+1}s_{i}\\
& \ \ \ \ \ \ \ \ \ \ \left(  \text{where the subscripts first rise, then
fall: }\begin{tikzpicture}
\draw (0,0) -- (1,1) -- (2,0);
\end{tikzpicture}\right)  \\
& =s_{j-1}s_{j-2}\cdots s_{i+1}s_{i}s_{i+1}\cdots s_{j-2}s_{j-1}\\
& \ \ \ \ \ \ \ \ \ \ \left(  \text{where the subscripts first fall, then
rise: }\begin{tikzpicture}
\draw (0,0) -- (1,-1) -- (2,0);
\end{tikzpicture}\right)  .
\end{align*}


\item[\textbf{(e)}] For any $\sigma\in S_{n}$ and any distinct $i_{1}%
,i_{2},\ldots.,i_{k}$, we have
\[
\sigma\circ\operatorname*{cyc}{}_{i_{1},\ldots,i_{k}}\circ\sigma
^{-1}=\operatorname*{cyc}{}_{\sigma(i_{1}),\ldots,\sigma(i_{k})}.
\]


\item[\textbf{(f)}] For any $i\neq j$ in $\left[  n\right]  $, we have
$t_{i,j}=t_{j,i}$.

\item[\textbf{(g)}] For any $i\in\left[  n-1\right]  $, we have $s_{i}%
=t_{i,i+1}$.
\end{enumerate}
\end{proposition}

\begin{proof}
Parts \textbf{(f)} and \textbf{(g)} are trivial.

Parts \textbf{(a)} and \textbf{(e)} fall prey to the standard strategy of
\textquotedblleft show that the left and the right hand sides send any
$k\in\left[  n\right]  $ to the same image\textquotedblright\ (see
\cite[Exercise 5.16 and Exercise 5.17]{detnotes}). Part \textbf{(b)} is a
particular case of \textbf{(a)}, since $s_{i}=t_{i,i+1}$.

\textbf{(c)} To prove the equality%
\[
w_{0}=s_{1}\circ(s_{2}s_{1})\circ(s_{3}s_{2}s_{1})\circ\cdots\circ
(s_{n-1}s_{n-2}\cdots s_{1}),
\]
show (by induction on $m$) that each $m\in\left[  n\right]  $ satisfies%
\begin{align*}
& s_{1}\circ(s_{2}s_{1})\circ(s_{3}s_{2}s_{1})\circ\cdots\circ(s_{m-1}%
s_{m-2}\cdots s_{1})\\
& =(\text{the permutation in }S_{n}\text{ that sends }1,2,\ldots,m\\
& \qquad\text{to }m,m-1,\ldots,1\text{ and leaves }m+1,m+2,\ldots,n\text{
unchanged})
\end{align*}
(this uses part \textbf{(b)}; see \cite[solution to Exercise 5.1 \textbf{(c)}%
]{detnotes} for details). To prove the equality%
\[
w_{0}=\left(  s_{1}s_{2}\cdots s_{n-1}\right)  \circ\left(  s_{1}s_{2}\cdots
s_{n-2}\right)  \circ\cdots\circ\left(  s_{1}s_{2}\right)  \circ s_{1},
\]
similarly argue that each $m\in\left[  n\right]  $ satisfies%
\begin{align*}
& \left(  s_{1}s_{2}\cdots s_{m-1}\right)  \circ\left(  s_{1}s_{2}\cdots
s_{m-2}\right)  \circ\cdots\circ\left(  s_{1}s_{2}\right)  \circ s_{1}\\
& =(\text{the permutation in }S_{n}\text{ that sends }1,2,\ldots,m\\
& \qquad\text{to }m,m-1,\ldots,1\text{ and leaves }m+1,m+2,\ldots,n\text{
unchanged}).
\end{align*}


\textbf{(d)} This can be proved by induction on $j-i$. In the induction step,
use $t_{i,j}=s_{i}t_{i+1,j}s_{i}$ for the first equality and $t_{i,j}%
=s_{j-1}t_{i,j-1}s_{j-1}$ for the second equality.
\end{proof}

\begin{definition}
An \emph{inversion} of a permutation $\sigma\in S_{n}$ means a pair $(i,j)$ of
elements of $[n]$ with $i<j$ and $\sigma(i)>\sigma(j)$.
\end{definition}

\begin{statement}
\textbf{Example.} Let $\pi=[3,1,4,2]\in S_{4}$ (as usual, written in one-line
notation; also called $\pi$ for reasons...). The inversions of $\pi$ are
$(1,2)$, $(1,4)$ and $(3,4)$. For example, $\left(  1,2\right)  $ is an
inversion of $\pi$ because $1<2$ but $\pi(1)=3>1=\pi(2)$.
\end{statement}

\begin{definition}
The \emph{length} of a permutation $\sigma\in S_{n}$ is its number of
inversions. It is called $\ell(\sigma)$.

(This is also called the \emph{(Coxeter) length} of $\sigma$.)
\end{definition}

\begin{statement}
\textbf{Example.} The permutation $\pi\in S_{4}$ from the previous example has
length $\ell(\pi)=3$.
\end{statement}

\begin{remark}
If $\sigma\in S_{n}$, then $0\leq\ell(\sigma)\leq\dbinom{n}{2}$.

The only $\sigma\in S_{n}$ with $\ell(\sigma)=0$ is $\operatorname{id}$.

The only $\sigma\in S_{n}$ with $\ell(\sigma)=\dbinom{n}{2}$ is $w_{0}$.

Inbetween, there are many $\sigma$'s with a given length.
\end{remark}

Here is a picture of $S_{3}$ showing all permutations $\sigma\in S_{3}$ in
one-line notation (showing their lengths $\ell\left(  \sigma\right)  $ on the
right):%
\[
\xymatrix{
& 321 \are[ld]_{s_1} \are[rd]^{s_2} & & & \ell = 3 \\
231 \are[d]_{s_2} & & 312 \are[d]^{s_1} & & \ell = 2 \\
213 \are[rd]_{s_1} & & 132 \are[ld]^{s_2} & & \ell = 1 \\
& 123 & & & \ell = 0
}
\]
(This is a graph whose vertices are the $6$ permutations in $S_{3}$, written
in one-line notation. Note that the top vertex is $321=w_{0}$, while the
bottom vertex is $123=\operatorname*{id}$. An edge $\xymatrix{
\alpha \are[r]^{s_i} & \beta
}$ is drawn whenever $\alpha=\beta\circ s_{i}$ (or, equivalently,
$\beta=\alpha\circ s_{i}$).)

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[Bona22]{Bona22}Mikl\'{o}s B\'{o}na, \textit{Combinatorics of
Permutations}, 3rd edition, Taylor\&Francis 2022.\newline\url{https://doi.org/10.1201/9780429274107}

\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics},
13 December 2017.\newline%
\url{https://www3.nd.edu/~dgalvin1/60610/60610_S21/index.html} \newline(Follow
the Overleaf link and compile main.tex and Course-notes.tex. See also
\url{https://web.archive.org/web/20180205122609/http://www-users.math.umn.edu/~dgrinber/comb/60610lectures2017-Galvin.pdf}
for an archived old version.)

\bibitem[Grinbe15]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 15 September 2022.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2022-09-15c} or
\href{https://arxiv.org/abs/2008.09862v3}{arXiv:2008.09862v3}.

\bibitem[Grinbe17]{logexp}Darij Grinberg, \textit{Why the log and exp series
are mutually inverse}, 11 May 2018.\newline\url{https://www.cip.ifi.lmu.de/~grinberg/t/17f/logexp.pdf}

\bibitem[Grinbe21]{21s}Darij Grinberg, \textit{An Introduction to Algebraic
Combinatorics (Math 531, Winter 2024 lecture notes)}, 8 February 2025.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/21s/lecs.pdf}

\bibitem[Loehr11]{Loehr-BC}%
\href{http://www.math.vt.edu/people/nloehr/bijbook.html}{Nicholas A. Loehr,
\textit{Bijective Combinatorics}, Chapman \& Hall/CRC 2011.}

\bibitem[Wilf04]{Wilf04}Herbert S. Wilf, \textit{generatingfunctionology}, 2nd
edition 2004.\newline\url{https://www2.math.upenn.edu/~wilf/DownldGF.html}
\end{thebibliography}


\end{document}