\documentclass[12pt]{amsart}
\usepackage{amsmath,amsfonts,epsfig}
\marginparwidth 0pt \marginparsep 0pt
\oddsidemargin -0.1in \evensidemargin 0pt
\topmargin -.3in
\textwidth 6.5in
\textheight 9in
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newcommand{\choice}[2]{{{#1}\choose{#2}}}
\newcommand{\REF}[1]{[\ref{#1}]}
\newcommand{\Ref}[1]{(\ref{#1})}
\newcommand{\ts}{\textstyle}
\newcommand{\sst}{\scriptstyle}
\newcommand{\setn}{{\bf [n]}}
\newcommand{\setm}{{\bf [m]}}
\newcommand{\setL}{{\bf [L]}}
\newcommand{\integers}{\mbox{\bb Z}}
\newcommand{\positives}{\mbox{\bb P}}
%\newcommand{\example}{\noindent{\sc Example.\ }}
\newcommand{\examp}[1]{\noindent{\sc Example {#1}.\ }}
\newcommand{\examples}{\noindent{\sc Examples.\ }}
%\newcommand{\proof}{\noindent {\sc Proof.\ }}
\newcommand{\remark}{\noindent {\sc Remark.\ }}
\newcommand{\remarks}{\noindent {\sc Remarks.\ }}
\newcommand{\defin}{\noindent {\sc Definition.\ } }
\newcommand{\notation}{\noindent {\sc Notation.\ } }
%\newcommand{\qed}{{\hfill $\triangle$}}
%-------------
\newcommand{\dcup}{{\stackrel{\cdot}{\cup}}}
%-------------
\newcommand{\al}{{\alpha}}
\newcommand{\ta}{{\theta}}
\newcommand{\be}{{\beta}}
\newcommand{\ga}{{\gamma}}
\newcommand{\de}{{\delta}}
\newcommand{\la}{{\lambda}}
\newcommand{\La}{{\Lambda}}
\newcommand{\om}{{\omega}}
\newcommand{\ka}{{\kappa}}
\newcommand{\vep}{{\varepsilon}}
\newcommand{\vth}{{\vartheta}}
\newcommand{\si}{{\sigma}}
\newcommand{\De}{{\Delta}}
\newcommand{\ze}{{\zeta}}
%--------------
\newcommand{\ld}{{\ldots}}
\newcommand{\cd}{{\cdots}}
\newcommand{\ti}{{\times}}
%--------------
\newcommand{\sA}{{\cal A}}
\newcommand{\sN}{{\cal N}}
\newcommand{\sO}{{\cal O}}
\newcommand{\sR}{{\cal R}}
\newcommand{\sT}{{\cal T}}
\newcommand{\sB}{{\cal B}}
\newcommand{\sD}{{\cal D}}
\newcommand{\sL}{{\cal L}}
\newcommand{\sC}{{\mathcal C}}
\newcommand{\sF}{{\cal F}}
\newcommand{\sS}{{\mathcal S}}
\newcommand{\sP}{{\cal P}}
\newcommand{\sQ}{{\cal Q}}
\newcommand{\sK}{{\cal K}}
\newcommand{\sU}{{\cal U}}
\newcommand{\bx}{{\bf x}}
\newcommand{\bX}{{\bf X}}
%-------------
\newcommand{\sfC}{{\mathsf{C}}}
\newcommand{\sfE}{{\mathsf{E}}}
\newcommand{\sfF}{{\mathsf{F}}}
%--------------
\newcommand{\mF}{{\bf \mathrm{F}}}
\newcommand{\mZ}{{\bf \mathrm{Z}}}
\newcommand{\mt}{{\mathrm{t}}}
\newcommand{\rmN}{{\mathrm{N}}}
%--------------
\newcommand{\wt}{{\mathrm{wt}}\,}
\newcommand{\pf}{{\mathrm{pf}}\,}
\newcommand{\sgn}{{\mathrm{sgn}}\,}
\newcommand{\per}{{\mathrm{per}}\,}
\newcommand{\diag}{{\mathrm{diag }}\,}
\newcommand{\trace}{{\mathrm{trace}}\,}
\newcommand{\rank}{{\mathrm{rank}}\,}
\newcommand{\height}{{\mathrm{ht}}\,}
\newcommand{\suchthat}{\,|\,}
\newcommand{\equals}{\;=\;}
\newcommand{\sabar}{{\overline{\sA}}}
\newcommand{\srbar}{{\overline{\sR}}}
\title{C\&O 631 NOTES}
\date{\today}
\begin{document}
\maketitle
\section{Formal power series}
The series that we shall use in this course are {\it formal power series},
not the power series of real variables that have been studied in
calculus courses. A formal power series is given
by $A(x)=\sum_{i\geq 0} a_i x^i$, where $a_i=[x^i]A(x)$, the
{\it coefficient of} $x^i$, is a complex number,
for $i\geq 0$. The basic rule for $A(x)$ is that $a_i$ is determined finitely
for each finite $i$. Let $B(x)=\sum_{i\geq 0}b_ix^i$. Then $A(x)=B(x)$ if
and only if $a_i=b_i$ for all $i\geq 0$, and we define
sum and product by
$$A(x)+B(x)= \sum_{i\geq 0} (a_i+b_i)x^i,\;\;\;\;
A(x)B(x)=\sum_{i\geq 0}\left(\sum_{j=0}^ia_jb_{i-j}\right)x^i,$$
and a special case of product is the scalar
product $c\,A(x)=\sum_{i\geq 0}(c\,a_i)x^i$, for a complex number $c$.
We write $A(0)=a_0$, and unless $A$ is a polynomial, this is the only
evaluation we allow. If $b_0=0$, then we define the composition
$$A(B(x))=\sum_{i\geq 0}a_iB(x)^i=\sum_{n\geq 0}
\sum_{\stackrel{i\ge 0,j_1,\ld ,j_i\geq 1}{j_1+\ld +j_i=n}}
a_ib_{j_1}\ld b_{j_i} x^n,$$
and note that the summations above are finite. Note that we only allow substitutions of this type - where we substitute a constant-free $B(x)$ for $x$.
Now suppose $A(0)=1$. Then if $B(x)$ is a {\em multiplicative inverse}
of $A(x)$, we have (since multiplication of complex numbers is commutative,
so is multiplication of $A(x)$ with $B(x)$, so there is no difference
between a left-inverse and a right-inverse) $\sum_{i\geq 0}a_ix^i\sum_{j\geq 0}b_jx^j=1$,
and equating coefficients of $x^n$ on both sides, for $n\geq 0$, we obtain
\begin{eqnarray*}
b_0&=&1\\
a_1b_0+b_1&=&0\\
a_2b_0+a_1b_1+b_2&=&0,
\end{eqnarray*}
where the $n$th equation is $a_nb_0+a_{n-1}b_1+\ld +b_0=0$, $n\geq 1$. But this
gives $b_0=1$, and allows us to determine $b_n$ uniquely in terms of $b_0,\ld ,b_{n-1}$, for
each $n\geq 1$, so, by induction on $n$, $B(x)$ is unique. Applying this process to
obtain the multiplicative inverse of $A(x)=1-x$, we obtain $b_n=1$, $n\ge 0$,
by induction on $n$, or $(1-x)^{-1}=\sum_{i\geq 0}x^i$. But substitution into
this, for an arbitrary $A(x)$ with $A(0)=1$, gives
$$A(x)^{-1}=\left( 1-(1-A(x))\right) ^{-1}
=1+\sum_{i\geq 1}\left( 1-A(x)\right) ^i,$$
which is therefore the {\it unique} multiplicative inverse of $A(x)$.
\medskip
We define {\it differentiation} and {\it integration} operators by
$$\frac{d}{dx}A(x)=\sum_{i\geq 1}ia_ix^{i-1},\;\;\;\;\;\;
I_x\, A(x)=\sum_{i\geq 0}\frac{a_i}{i+1}x^{i+1}.$$
Now note that we have uniqueness for solution of differential
equations: if $\frac{d}{dx}A(x)=\frac{d}{dx}B(x)$ and $A(0)=B(0)$,
then $A(x)=B(x)$. Now
$$\frac{d}{dx}(A(x)+B(x))=\sum_{i\geq 1}i(a_i+b_i)x^{i-1}
=\sum_{i\geq 1}ia_ix^{i-1}+\sum_{i\geq 1}ib_ix^{i-1}
=\frac{d}{dx}A(x)+\frac{d}{dx}B(x),$$
so the differentiation satisfies the sum rule, and
\begin{eqnarray*}
\frac{d}{dx}(A(x)B(x))&=&\sum_{i\geq 1}\sum_{j=0}^iia_jb_{i-j}x^{i-1}\\
&=&\sum_{i\geq 1}\sum_{j=0}^i(j+i-j)a_jb_{i-j}x^{i-1}\\
&=&\left(\frac{d}{dx}A(x)\right)B(x)+A(x)
\left(\frac{d}{dx}B(x)\right),
\end{eqnarray*}
and differentiation satisfies the product rule. Induction on $n$ then
gives $\frac{d}{dx}B(x)^n=nB(x)^{n-1}\frac{d}{dx}B(x)$ for positive
integers $n$, which allows
us to prove the {\it chain rule}:
$$\frac{d}{dx}A(B(x))=A^{\prime}(B(x))\frac{d}{dx}B(x).$$
To differentiate $A(x)^{-1}$, where $A(0)=1$, we apply the product rule
to $A(x)\cdot A(x)^{-1}=1$, to obtain
\begin{equation}\label{diffinv}
A(x)^{-1}\frac{d}{dx}A(x)+A(x)\frac{d}{dx}A(x)^{-1}=0,
\end{equation}
and thus conclude that
$$\frac{d}{dx}A(x)^{-1}= -A(x)^{-2}\frac{d}{dx}A(x).$$
We now define three special series
\begin{equation}\label{three fps}
\vep (x)=\sum_{n\geq 0}\frac{1}{n!}x^n,\quad \la(x)=\sum_{n\geq 1}\frac{1}{n}x^n,\quad B_a(x)=\sum_{n\geq 0}\frac{a(a-1)\ld (a-n+1)}{n!}x^n,
\end{equation}
where $a$ is a complex number parameter in $B_a(x)$. Our
object is to show that $\vep(x),\la (x), B_a(x)$ have
the properties of the familiar
functions $e^x,\mathrm{ln}(1-x)^{-1},(1+x)^a$, respectively.
(Except that we will NOT be able to consider,
for example, $\vep (\vep (x))$, since it uses composition with
a series with constant term $1$.) First, note
that $\frac{d}{dx}\vep (x)=\vep (x)$. Then, for example, we can prove
that $\vep (x)\vep(-x)=1$, since $\vep (x)\vep(-x)$ has
constant term $\vep (0)\vep (-0)=1$, and
$$\frac{d}{dx}(\vep (x)\vep (-x))=\vep (x)\vep (-x)-\vep (x)\vep (-x)
=0,$$
where we have used the product rule and chain rule. The result follows
by the uniqueness of solution of differential equations ( since $1$ also
has constant term $1$ and derivative $0$). Also, we
have $\frac{d}{dx}\la (x)=\sum_{n\ge 0}x^n=(1-x)^{-1}$, so
$$\frac{d}{dx}\left(\la (1-\vep (-x))\right)
=\left(\vep (-x)\right) ^{-1}\vep (-x) =1,$$
by the chain rule, and $\la (1-\vep (-0))=0$, and we conclude
that $\la (1-\vep (-x))=x$, by uniqueness of solution of
differential equations. (The series $1-\vep (-x)$ has constant
term $0$, so the composition $\la (1-\vep (-x))$ is valid.)
Similarly, we prove that $\vep (\la (x))=(1-x)^{-1}$, using
$\vep (\la (0))=1$, and
$$\frac{d}{dx}\left( (1-x)\vep (\la (x))\right)
=-\vep (\la (x))+(1-x)\vep (\la (x))(1-x)^{-1} =0,$$
using the product rule and chain rule. Also, if $A(0)=1$, the chain rule together
with~\eqref{diffinv} gives
\begin{equation}\label{lnderiv}
\frac{d}{dx}\la(1-A(x)^{-1})=A(x)\frac{d}{dx}\left( 1-A(x)^{-1}\right) =A(x)^{-1}\frac{d}{dx}A(x).
\end{equation}
For the series $B_a(x)$, we have $\frac{d}{dx}B_a(x)=a\,B_{a-1}(x)$, and we omit further details of these computations. In summary, we have demonstrated above that the series $\vep(x),\la (x), B_a(x)$ defined in~(\ref{three fps}) have most of the properties of the familiar functions $e^x,\mathrm{ln}(1-x)^{-1},(1+x)^a$, respectively, and we shall write
\begin{equation}\label{threefunc}
e^x=\sum_{n\geq 0}\frac{1}{n!}x^n,\quad {\mathrm{ln}}(1-x)^{-1}=\sum_{n\geq 1}\frac{1}{n}x^n,\quad (1+x)^a =\sum_{n\geq 0}\frac{a(a-1)\ld (a-n+1)}{n!}x^n,
\end{equation}
where, as usual, the only substitutions that we allow for $x$ are constant-free formal power series.
For example, in terms of these familiar functions,~(\ref{lnderiv}) becomes the familiar logarithmic differentiation rule
$$\frac{d}{dx}\mathrm{ln}A(x) =A(x)^{-1}\frac{d}{dx}A(x),$$
where $A(0)=1$. As another example, consider the problem of finding the $n$th root of a formal power series: begin by noting that it is easy to verify that there are no zero divisors for formal power series,
and this fact allows us to establish
that $n$th roots are unique, at least with given constant term, as follows.
Suppose $A(0)=B(0)=1$, and $A(x)^n=B(x)^n$, for some positive integer $n$.
Then we have
$$0=A(x)^n-B(x)^n=(A(x)-B(x))(A(x)^{n-1}+A(x)^{n-2}B(x)+\ld +B(x)^{n-1}) .$$
Now the constant term in the second factor
is $A(0)^{n-1}+A(0)^{n-2}B(0)+\ld +B(0)^{n-1}=n\neq 0$, so we conclude
that $A(x)-B(x)=0$, since there are no zero divisors, which gives $A(x)=B(x)$,
as required. But we can determine the $n$th root of $A(x)$ with $A(0)=1$
by substitution in the binomial series $B_{\frac{1}{n}}(x)=(1+x)^{\frac{1}{n}}$, to obtain
$$A(x)^{\tfrac{1}{n}}=(1+(A(x)-1))^{\tfrac{1}{n}}
=1+\sum_{i\geq 1}\frac{\tfrac{1}{n}(\tfrac{1}{n}-1)\ld(\tfrac{1}{n}-i+1)}{i!}(A(x)-1)^i,$$
which is therefore the {\it unique} $n$th root with constant term $1$.
\medskip
We introduce trigonometric series by defining
$$\sin (x)=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\ld,\;\;\;\;\;\;
\cos (x)=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\ld,$$
and then proving the properties of these series from
properties of the series $\vep (x) =e^x$, by
$$\sin (x)=\frac{e^{ix}-e^{-ix}}{2i},\;\;\;\;\;\;
\cos (x)= \frac{e^{ix}+e^{-ix}}{2},$$
so, for example, we have
\begin{eqnarray*}
\sin (x) ^2 +\cos (x) ^2&=&
\left( \frac{e^{ix}-e^{-ix}}{2i}\right) ^2+
\left( \frac{e^{ix}+e^{-ix}}{2}\right) ^2\\
&=&\tfrac{1}{4}\left( -(e^{2ix} -2+e^{-2ix})+(e^{2ix} +2+e^{-2ix})\right) =1.
\end{eqnarray*}
Then, noting that $\cos (x)$ has constant term $1$, so it is invertible, we define
$$\tan (x)=\frac{\sin (x)}{\cos (x)} = x+\frac{x^3}{3}+\frac{2x^5}{15}+\ld
=x+\frac{2x^3}{3!}+\frac{16x^5}{5!}+\ld,$$
$$\sec (x) =\frac{1}{\cos (x)}=1+\frac{x^2}{2}+\frac{5x^4}{24}+\ld
=1+\frac{x^2}{2!}+\frac{5x^4}{4!}+\ld .$$
Various special functions are of interest combinatorially. For example,
the coefficients in these formal power series for \emph{sec} and \emph{tan}, scaled
by the factorial as in the above expressions, give the number of permutations of
a special kind, called \emph{alternating} permutations.
In a similar way, consider {\it formal Laurent series}, given by $A(x)=\sum_{i\ge -k} a_ix^i$, for
some finite negative integer $-k$. We proceed as for formal power series above, with little
modification required. To handle multiplicative inverses, suppose that $A(x)=a_{-k}x^{-k}B(x)$,
where $a_{-k}$ is invertible, and $B(x)$ is a formal power series with $B(0)=1$. Then define
$$A(x)^{-1}=a_{-k}^{-1}x^{k}B(x)^{-1}.$$
We define differentiation in the same way as for formal power
series, by $\frac{d}{dx}A(x)=\sum_{i\ge -k} ia_ix^{i-1}$. The
{\it formal residue} of a formal Laurent series is given by the coefficient of $x^{-1}$. This
has a nice invariance property, given in the following result.
\begin{theorem}\label{rescomp}
Suppose that $A(x)$ is a formal Laurent series, and that $B(x)=\sum_{i\ge m}b_ix^i$ is
a formal power series with $m$ a positive integer, and $b_m$ invertible. Then
$$[x^{-1}]A(x)=\frac{1}{m}[x^{-1}]A(B(x))\frac{d}{dx}B(x).$$
(Note, that for formal Laurent series $A(x)$, the composition $A(B(x))$ is well-formed
only when $B(x)$ is a formal power series with constant term $0$.)
\end{theorem}
\begin{proof}
Let $A(x)=\sum_{n\ge -k}a_nx^n$, so on the right hand side of the result we have
$$ \frac{1}{m}[x^{-1}]\sum_{n\ge -k} a_nB(x)^n\frac{d}{dx}B(x).$$
For $n\ge 0$, note that $B(x)^nB^{\prime}(x)$ is a formal power series in $x$, so we
have
$$\frac{1}{m}[x^{-1}]B(x)^nB^{\prime}(x)=0$$
in this case.
For $-k1$, this gives
$$g_n=-f_1^{-1}\sum_{i=2}^{n}f_i \sum_{j_1+\ld +j_i=n}g_{j_1}\cdots g_{j_i},$$
which allows us to recursively obtain each coefficient $g_n$ finitely in terms
of $f_1,\ld ,f_n$.
\vspace{.1in}
{\bf Lagrange's Implicit Function Theorem.} We have the functional
equation $w=t\phi(w)$, for
some formal power series $\phi$ with an invertible constant term. Rewrite this functional
equation as $\Phi(w)=t$, where $\Phi(w)=w/\phi(w)$, and
let $\Psi$ be the compositional inverse of $\Phi$, so
we have $w=\Psi(t)$.
Now consider any formal Laurent series $f$.
Then we have, for $n\neq 0$,
$$[t^n]f(w)=[t^{-1}]t^{-n-1}f(w)=[t^{-1}]t^{-n-1}f(\Psi(t)),$$
and we can apply Theorem~\ref{rescomp}, with $B=\Phi$ (for which we have $m=1$),
to obtain
$$[t^n]f(w)=[w^{-1}]\Phi(w)^{-n-1}f(w)\Phi^{\prime}(w)=-\frac{1}{n}[w^{-1}]f(w)\left(\Phi^{-n}(w)\right)^{\prime}.$$
But $[w^{-1}]f(w)g^{\prime}(w)=-[w^{-1}]f^{\prime}(w)g(w)$ for any formal Laurent series $f,g$,
since
$$[w^{-1}]\left(f(w)g(w)\right)^{\prime}=0,$$
so we have
\begin{equation}\label{lagnorm}
[t^n]f(w)=\frac{1}{n}[w^{-1}]f^{\prime}(w)\Phi^{-n}(w)=\frac{1}{n}[w^{-1}]f^{\prime}(w)\phi^{n}(w)w^{-n}
=\frac{1}{n}[w^{n-1}]f^{\prime}(w)\phi^{n}(w),
\end{equation}
for $n\ge 1$, where $w=t\phi(w)$, which is the usual statement of Lagrange's Implicit Function Theorem. For an analytic treatment of Lagrange's Theorem, see Section 5.1 of Wilf's book {\em Generatingfunctionology}.
\section{Lecture of May 1}
We now turn to {\it symmetric functions}.
For fixed positive integer $n$, we consider formal power series in $x_1,\ld ,x_n$.
A formal power series $A(x_1,\ld ,x_n)$ is
{\it symmetric} if $A(x_{\si(1)},\ld ,x_{\si(n)})=A(x_1,\ld ,x_n)$ for all
permutations $\si$ of $\{ 1,\ld ,n\}$ (so the word ``symmetric'' here refers
to the symmetric group $S(n)$, which consists of all permutations of $\{ 1,\ld ,n\}$).
We begin with the simplest example. Let $\la =(\la_1,\ld ,\la_n)$,
where $\la_1\ge\ld\ge\la_n\ge 0$, so $\la$ is a {\it partition} with
at most $n$ parts (the number of parts in $\la$ is given by the number
of positive $\la_i$'s). Then the {\em monomial} symmetric function $m_{\la}=m_{\la}(x_1,\ld ,x_n)$ is defined to be the
\begin{equation}\label{mosf}
m_{\la}= x_1^{\la_1}\cd x_n^{\la_n}+\ld,
\end{equation}
in which we add the minimal set of monomials that, together with the monomial $x_1^{\la_1}\cd x_n^{\la_n}$, creates a symmetric function. In general, $m_{\la}$ is a sum of $\frac{n!}{|{\mathrm{aut}}\la |}$ distinct monomials, where $| {\mathrm{aut}}\la | $ is the number of permutations that fix the $n$-tuple $(\la_1,\ld ,\la_n)$. For example, we have $m_{(2,2,2)}(x_1,x_2,x_3) = x_1^2x_2^2x_3^2$, and
\[ m_{(3,2,0)}(x_1,x_2,x_3) = x_1^3x_2^2+x_1^3x_3^2+x_1^2x_2^3+x_2^3x_3^2+x_1^2x_3^3+x_2^2x_3^3. \]
Second, the {\it elementary} symmetric functions $e_k=e_k(x_1,\ld ,x_n)$, $k\ge 0$,
are defined by $e_k= m_{(1,\ld ,1,0,\ld ,0)}$, where $(1,\ld ,1,0,\ld ,0)$ has $k$ $1$'s and $n-k$ $0$'s. Equivalently, using a generating function, we have
\begin{equation}\label{elsf}
\sum_{k\ge 0} e_kt^k=\prod_{j=1}^n (1+x_jt).
\end{equation}
Thus $e_k$ is the sum of $\binom{n}{k}$ monomials with exponents $0$ or $1$, each of which
corresponds to a $k$-subset of $\{ 1\ld ,n\}$, the $k$-subset specifying which
of the indeterminates have exponent $1$.
Third, the {\it homogeneous} (or {\it complete}) symmetric
functions $h_k=h_k(x_1,\ld ,x_n)$, $k\ge 0$,
are defined by
\[ h_k = \sum m_{\la}, \]
where the summation is over all $\la=(\la_1,\ld ,\la_n)$ with $\la_1+\cd+\la_n=k$. But this means that $h_k$ is the sum of all monomials in $x_1,\ld ,x_n$ of (total) degree $k$, so, equivalently, using a generating function, we have
\begin{equation}\label{hosf}
\sum_{k\ge 0} h_kt^k=\prod_{j=1}^n (1-x_jt)^{-1}=\prod_{j=1}^n (1+x_jt+x_j^2t^2+\ld ).
\end{equation}
Thus $h_k$ is the sum of all of the $\binom{n+k-1}{k}$ monomials with non-negative
exponents totalling $k$.
Fourth, the {\it power sum} symmetric
functions $p_k=p_k(x_1,\ld ,x_n)$, $k\ge 0$,
are defined by $p_k=m_{(k,0,\ld ,0)}$, so we have $p_0=1$ and
\begin{equation}\label{pssf}
p_k=\sum_{j=1}^n x_j^k,\quad k\ge 1.
\end{equation}
In terms of generating functions, we obtain
\[ \sum_{k\ge 1}p_k\frac{t^k}{k} = \sum_{k\ge 1} \sum_{j=1}^n x_j^k \frac{t^k}{k} = \sum_{j = 1}^n \sum_{k\ge 1} x_j^k \frac{t^k}{k} = \sum_{j = 1}^n \mathrm{ln} (1-x_j t)^{-1} = \mathrm{ln}\sum_{i\ge 0} h_i t^i. \]
As a fifth example, we now consider a less familiar example of symmetric functions, the Schur functions. We shall make extensive use of {\em determinants} in this presentation, for which it will be useful to recall the definition as a summation over the symmetric group:
\[ \det \left( a_{i,j} \right)_{i,j=1,\ld ,n} = \sum_{\rho\in S(n)} \sgn(\rho)\prod_{i=1}^n a_{i,\rho(i)} . \]
Then for $\la =(\la_1,\ld ,\la_n)$
with $\la_1\ge\ld\ge\la_n\ge 0$, the {\it Schur} symmetric
function $s_{\la}=s_{\la}(x_1,\ld ,x_n)$ is defined by
\begin{equation}\label{scsf}
s_{\la}=
\frac{\det\left(x_i^{\la_j +n-j}\right)_{i,j=1,\ld ,n}}{\det\left(x_i^{n-j}\right)_{i,j=1,\ld ,n}}.
\end{equation}
This is symmetric because
$$s_{\la}(x_{\si(1)},\ld ,x_{\si(n)})=\frac{\mathrm{sgn}(\si )}{\mathrm{sgn}(\si )}
s_{\la}(x_1,\ld ,x_n),$$
where $\mathrm{sgn}(\si )$ is the sign of the permutation $\si$ (since in both the numerator
and denominator determinants of $s_{\la}$, to evaluate at $x_{\si(1)},\ld ,x_{\si(n)}$,
we simply permute the rows by $\si$).
The denominator determinant in~\eqref{scsf} is well-known, as the {\it Vandermonde}
determinant. Call it $V(x_1,\ld ,x_n)$. Note that $V$ is a polynomial in $x_1,\ld ,x_n$,
and has value $0$ if $x_k=x_{\ell}$ for any $k\neq \ell$ (since
this makes rows $k$ and $\ell$ identical). Therefore $V$ is divisible by
\begin{equation}\label{vanprod}
\prod_{1\le k< \ell\le n}(x_k-x_{\ell}).
\end{equation}
But $V$ is homogeneous of total degree $(n-1)+\ld +1+0=\binom{n}{2}$,
and~\eqref{vanprod} is also homogeneous of total degree $\binom{n}{2}$, so
we conclude that
$$V(x_1,\ld ,x_n)=c\cdot\prod_{1\le k< \ell\le n}(x_k-x_{\ell}),$$
for some constant $c$. Now, the monomial $x_1^{n-1}\cdots x_{n-1}^1 x_n^0$ appears
in $V$ with coefficient $1$, since it is produced uniquely in the
expansion of the determinant as the product of
the entries on the main diagonal (for which $\rho$ is the identity permutation, with $\sgn$ $+1$); this monomial also appears in
the expansion of~\eqref{vanprod} with coefficient $1$, since it is produced uniquely
in the expansion of the product by selecting the $x_k$ from each $x_k-x_{\ell}$.
This implies that $c=1$, giving
\begin{equation}\label{vanfinal}
V(x_1,\ld ,x_n)=\prod_{1\le k< \ell\le n}(x_k-x_{\ell}).
\end{equation}
Now the same argument as we used for the denominator proves that the numerator determinant in~\eqref{scsf}
is a polynomial divisible by~\eqref{vanprod}, which implies that $s_{\la}$ is
a symmetric {\it polynomial} in $x_1,\ld ,x_n$ (not just a symmetric rational
function), since the denominator in~\eqref{scsf} perfectly divides the numerator. Moreover, since the numerator of~\eqref{scsf} is a homogeneous polynomial of total degree $\la_1+\ld +\la_n +\binom{n}{2}$, we conclude that the polynomial $s_{\la}$ itself is homogeneous, of total degree $\la_1+\ld +\la_n$.
We now give a second, combinatorial definition of the polynomial $s_{\la}$ (and
will then prove that these definitions are consistent). The {\it Ferrers graph}
of the partition $\la$ is an array of boxes (called {\it cells}), with $\la_i$ cells
in row $i$ (indexed from the top), for each positive $\la_i$, aligned at the left.
For example, the Ferrers graph of $(5,3,2)$ is given on the
left hand side of Figure~\ref{Fertab}.
\begin{figure}[ht]
\begin{center}
\scalebox{.80}{\includegraphics{ferrtab.eps}}
\end{center}
\caption{A Ferrers graph and tableau.}\label{Fertab}
\end{figure}
A {\it tableau} of {\it shape} $\la$ is obtained by placing positive
integers (here the positive integers are between $1$ and $n$) into the cells of the Ferrers graph of $\la$ (one in each cell),
subject to the condition that the integers weakly increase from left
to right across each row, and strictly increase from top to bottom
down each column. An example of a tableau of shape $(5,3,2)$ is given on the
right hand side of Figure~\ref{Fertab}.
Our combinatorial definition of $s_{\la}(x_1,\ld ,x_n)$ is now given by
\begin{equation}\label{combscsf}
s_{\la}=\sum_T \wt (T), \qquad \wt (T) = \prod_{j=1}^n x_j^{n_j(T)},
\end{equation}
where the summation is over all tableaux $T$ of shape $\la$, and $n_j(T)$ is the number
of times $j$ appears in a cell of $T$. For example, the tableau given in Figure~\ref{Fertab} contributes the
monomial $x_1^2 x_2 x_3^3 x_4^2 x_5^2$ to $s_{(5,3,2)}(x_1,\ld ,x_n)$ (for any $n\ge 5$).
\section{Lecture of May 3}
Note that the combinatorial object defined in~\eqref{combscsf} is a homogeneous
polynomial of total degree $\la_1+\ld \la_n$ (where $\la=(\la_1,\ld .\la_n)$),
since each monomial has exponents totalling the number of cells in the Ferrers
graph of $\la$.
It is also straightforward to prove directly that~\eqref{combscsf} is a symmetric
polynomial, as follows. For fixed $i$, $1\le i\le n-1$, and any tableau $T$ of
shape $\la$, consider the cells that contain $i$ or $i+1$. These cells must
appear in $T$ as disjoint collections, each of the form that appears
\begin{figure}[ht]
\begin{center}
\scalebox{.80}{\includegraphics{tansym.eps}}
\end{center}
\caption{Cells containing $i$ or $i+1$ in a tableau.}\label{exiphi}
\end{figure}
in Figure~\ref{exiphi} -- horizontal segments containing a weakly increasing
sequence of $i$'s and $i+1$'s, with vertical pairs containing one $i$ and
one $i+1$ in between. Define a mapping $\phi_i$ on the set of such tableaux,
whose action on $T$ is to replace each horizontal segment with $j$ $i$'s
followed by $k$ $i+1$'s, by a horizontal segment with $k$ $i$'s
followed by $j$ $i+1$'s. (For example, there are three horizontal segments
in Figure~\ref{exiphi} -- the first from the left would be replaced with
two $i+1$'s, the middle by two $i$'s and one $i+1$, and the third
by a single $i$.) Clearly $\phi_i$ is an involution (which means
that $\phi_i(\phi_i(T))=T$), whose fixed points have equal numbers of $i$'s and $i+1$'s in
all horizontal segments.
Thus $\phi_i$ is a bijection on the set
of tableaux that interchanges the number of $i$'s and $i+1$'s, and hence~\eqref{combscsf}
is invariant under the adjacent transposition $(i,i+1)$ (note that the
fixed points of $\phi_i$ are themselves symmetric under the action of $(i,i+1)$).
But every permutation can be written as a product of adjacent transpositions,
and we conclude that~\eqref{combscsf} is a symmetric function.
Now we turn to proving that these two definitions of the Schur function really
are identical. The first step is to consider tableaux from a geometric point of
view, as a collection of {\it lattice paths}, whose unit steps that are either
horizontal (from left to right) or vertical (from bottom to top). In particular,
for $m\le n$ and $\la=(\la_1,\ld ,\la_m)$, with $\la_1\ge \ld\ge\la_m\ge 1$, for $j=1,\ld ,m$,
we construct path $\pi_j$, from starting point $P_j=(m-j,1)$ to ending
point $Q_j=(m-j+\la_j,n)$, to correspond to tableau $T$ of
shape $\la$, in the following way. There is a horizontal step
in $\pi_j$ at height $k$ for each cell
containing a $k$ in row $j$ of $T$. The vertical steps are filled in uniquely.
For example, the three paths corresponding to the tableau given in Figure~\ref{Fertab}
are illustrated in Figure~\ref{paths3}.
\begin{figure}[ht]
\begin{center}
\scalebox{.80}{\includegraphics{tabpaths.eps}}
\end{center}
\caption{Three paths corresponding to a tableau.}\label{paths3}
\end{figure}
Now, for each fixed $\la$, let
$$\sS=\{ (\si,\pi_1\ld ,\pi_m):\si\in S(m), \pi_i\;
\mathrm{a}\;\mathrm{lattice}\;\mathrm{path}\;\mathrm{from}\; P_i
\;\mathrm{to}\; Q_{\si(i)}, i=1,\ld,m\},$$
$$\Phi_{\sS}=\sum_{(\si,\pi_1\ld ,\pi_m)\in\sS}\mathrm{W}(\si,\pi_1\ld ,\pi_m),$$
where $S(m)$ is the symmetric group on $\{ 1,\ld ,m\}$, and we further define
$$\mathrm{W}(\si,\pi_1\ld ,\pi_m)=\mathrm{sgn}(\si)\prod_{i=1}^m
\prod_{j=1}^n x_j^{N_{i,j}},$$
and $N_{i,j}$ is the number of horizontal steps at height $j$ in $\pi_i$. But
$$\sum_{\pi_i}\prod_{j=1}^n x_j^{N_{i,j}}=
\sum_{a_1+\ld +a_n=\la_{\si(i)}-\si_i+i}x_1^{a_1}\cdots x_n^{a_n}=
h_{\la_{\si(i)}-\si(i)+i}(x_1,\ld ,x_n),$$
where the sum is over all paths $\pi_i$ from $P_i$ to $Q_{\si(i)}$,
since each such path has $m-\si(i)+\la_{\si(i)}-(m-i)=\la_{\si(i)}-\si(i)+i$
horizontal steps, and exactly one of these paths has $a_j$ at height $j$ for
each $a_1,\ld ,a_n\ge 0$ with $a_1+\ld +a_n=\la_{\si(i)}-\si(i)+i$. Thus we have
\begin{equation}\label{detPhi}
\Phi_{\sS}=\sum_{\si\in S_m} \mathrm{sgn}(\si )\prod_{i=1}^m h_{\la_{\si(i)}-\si(i)+i}(x_1,\ld ,x_n)
=\det \left( h_{\la_{j}-j+i}(x_1,\ld ,x_n)\right) _{i,j=1,\ld ,m}.
\end{equation}
Now partition the set $\sS$ into two subsets -- $\sS_{\mathrm{int}}$, in which
some pair of the paths $\pi_1,\ld ,\pi_m$ intersects, and $\sS_{\mathrm{nonint}}$, in which
no pair of the paths $\pi_1,\ld ,\pi_m$ intersects. We immediately have
\begin{equation}\label{disjint}
\Phi_{\sS}=\Phi_{\sS_{\mathrm{nonint}}}+\Phi_{\sS_{\mathrm{int}}},
\end{equation}
since this partitions the set $\sS$.
Now, if $(\si,\pi_1,\ld ,\pi_m)\in\sS_{\mathrm{nonint}}$, then $\si$ must be
the identity permutation, since otherwise, we must have $\si(i)>\si(j)$ for
some $ii$, replacing $j$ by $i$, and row-merging $j$ in row $2$;
if there is no such $j$, add $i$ (in a new cell) at the end of row $1$ and STOP. Repeat
until STOP (this will STOP at a previously empty row, if not sooner).
\vspace{.1in}
\noindent
{\bf Robinson-Schensted Algorithm} Consider a permutation $\si$ of $\{ 1,\ld ,n\}$ and
a pair $(P_0,Q_0)$ of empty tableaux (with no cells, corresponding to the empty
partition). For $i$ from $1$ to $n$, row-insert $\si(i)$ in $P_{i-1}$, and place $i$ in
a new cell added to $Q_{i-1}$, in the same cell in which $P_i$ differs from $P_{i-1}$.
CLAIM: $(P_n,Q_n)$ is an ordered pair of Young tableaux on elements $\{ 1,\ld ,n\}$, of the same shape,
and this is a bijection.
\vspace{.1in}
As an example of the Robinson-Schensted Algorithm with $n=7$,
consider $\si$ specified by $\si(1)\ld \si(7)=4\, 2\, 3\, 6\, 5\, 1\, 7$.
Then, by following the algorithm, we obtain:
$$
P_1=
\begin{tabular}{c}
4\\
\end{tabular}
\qquad\qquad
Q_1=
\begin{tabular}{c}
1\\
\end{tabular}
,\qquad\qquad\qquad
P_2=
\begin{tabular}{c}
2\\
4\\
\end{tabular}
\qquad\qquad
Q_2=
\begin{tabular}{c}
1\\
2\\
\end{tabular}
$$
$$
P_3=
\begin{tabular}{cc}
2&3\\
4&\\
\end{tabular}
\qquad\qquad
Q_3=
\begin{tabular}{cc}
1&3\\
2&\\
\end{tabular}
$$
$$
P_4=
\begin{tabular}{ccc}
2&3&6\\
4&&\\
\end{tabular}
\qquad\qquad
Q_4=
\begin{tabular}{ccc}
1&3&4\\
2&&\\
\end{tabular}
$$
$$
P_5=
\begin{tabular}{ccc}
2&3&5\\
4&6&\\
\end{tabular}
\qquad\qquad
Q_5=
\begin{tabular}{ccc}
1&3&4\\
2&5&\\
\end{tabular}
$$
$$
P_6=
\begin{tabular}{ccc}
1&3&5\\
2&6&\\
4&&\\
\end{tabular}
\qquad\qquad
Q_6=
\begin{tabular}{ccc}
1&3&4\\
2&5&\\
6&&\\
\end{tabular}
$$
$$
P_7=
\begin{tabular}{cccc}
1&3&5&7\\
2&6&&\\
4&&&\\
\end{tabular}
\qquad\qquad
Q_7=
\begin{tabular}{cccc}
1&3&4&7\\
2&5&&\\
6&&&\\
\end{tabular}
$$
In this case, we have mapped $\si$ to the pair $(P_7,Q_7)$ of Young tableaux, both
of the same shape $(4,2,1)$. As another example, if we apply the Robinson-Schensted Algorithm to the permutation $\pi = 6\, 2\, 3\, 1\, 5\, 4\, 7$, then we obtain the
pair $(Q_7,P_7)$ of Young tableaux (i.e., the roles of $P$ and $Q$ Are interchanged). Note that this permutation $\pi$ is the inverse of the permutation $\si$ above; in general we claim that if a permutation is mapped to the pair $(P,Q)$ of Young tableaux of the same shape, then $\si^{-1}$ is mapped to the pair $(Q,P)$. As two other examples of the Robinson-Schensted Algorithm, consider applying it to the identity permutation $1\, 2\, 3\, 4\, 5\, 6\, 7$, in which case we obtain both $P$ and $Q$ equal to the Young tableau with a single row of $7$ cells, with the elements $1,\ldots ,7$ in increasing order along that row, or consider applying it to the reverse permutation $7\, 6\, 5\, 4\, 3\, 2\, 1$, in which case we obtain both $P$ and $Q$ equal to the Young tableau with a single column of $7$ cells, with the elements $1,\ldots ,7$ in increasing order down that column.
Now we prove that the Robinson-Schensted Algorithm works, although we will not prove the statement about the inverse and interchanging $P$ and $Q$. We use the term ``bumping''
to describe what happens to element $j$ in some row when $ib_{\ell-1}=
t'_{\ell,c_{\ell}},$$
which gives $t'_{\ell+1,c_{\ell}}> t'_{\ell,c_{\ell}}$, when there is an element
in position ${\ell+1,c_{\ell}}$ of $T'$,
for $\ell=1,\ld ,r$. But, by construction, there is no element in position ${r+2,c_{r+1}}$ of $T'$,
so we have checked completely that $T'$ satisfies column-strictness. Also,
since $c_{r+1}\le c_{r}$, then the new cell in $T'$, in position ${r+1,c_{r+1}}$,
occurs below a existing cell in $T$, since $c_{r+1}\le c_r$ (and the cell in
position $r,c_r$ is occupied in $T$, and therefore in $T'$). Thus $T'$ is a tableau.
\end{proof}
\medskip
\begin{theorem}\label{RobSchenOK}
The Robinson-Schensted Algorithm is a bijection between permutations on $\{ 1,\ld ,n\}$ and
ordered pairs of Young tableaux of the same shape, where the shape varies over all
partitions of $n$.
\end{theorem}
\begin{proof}
In Corollary~\ref{rowmetab}, we have established at every
stage that $P_i$ is a tableau, for $i=1,\ld ,n$. As part of that proof,
we established that the cell in which $P_{i}$ differs from $P_{i-1}$ occurs
at the end of a row, and directly below another cell, so $Q_i$ is also a
tableau at every stage. It is easy to invert this Algorithm, since $P_{i-1}$ can
be recovered from $P_i$ by noting that the cell containing $i$ in $Q_i$ is
the cell in which $P_i$ differs from $P_{i-1}$, and then the row-insertion
process is easy to invert. This is a bijection because reversing as described
above always yields a tableau $P_{i-1}$ (check inequalities), at every stage, and
so we obtain a unique permutation $\si$ corresponding to each pair of tableaux $(P_n,Q_n)$.
\end{proof}
We have established that the Robinson-Schensted Algorithm works, but haven't proved
more refined properties, which we will prove now (at least sketch how).
First, if $\si\mapsto (P,Q)$ then $\si^{-1}\mapsto (Q,P)$. Second, the length of the
longest increasing subsequence in $\si$ is equal to the length of the
first row in $P$ (and $Q$); the length of the
longest decreasing subsequence in $\si$ is equal to the length of the
first column in $P$ (and $Q$).
To prove these facts, it is convenient to give a more geometrical (but equivalent)
version of the Algorithm. Given a permutation $\si$ of $\{ 1,\ld ,n\}$, place
vertices at positions $(i,\si (i))$ in ${\mathbb{R}}^2$. Let the quarter
plane given by the intersection of $x\ge a$ and $y\ge b$ be the \textit{shadow}
of vertex $(a,b)$. Find the union of the shadows of
the $n$ vertices $(1,\si (1)),\ld ,(n,\si (n))$, and let the piecewise linear
boundary of this union be the first ``shadow-line''. Remove the vertices on
this shadow-line, and repeat until no vertices remain, to obtain a set of
shadow-lines, with each vertex on a unique shadow-line, called the ``shadow diagram''.
For example, the shadow-lines corresponding to $\si (1)\ld \si (7) = 4\, 2\, 3\, 6\, 5\, 1\, 7$,
are pictured in Figure~\ref{shaddiag} (this
is the permutation for which we illustrated the Robinson-Schensted Algorithm
on pages 12, 13).
\begin{figure}[ht]
\begin{center}
\scalebox{.80}{\includegraphics{shadow.eps}}
\end{center}
\caption{A shadow diagram.}\label{shaddiag}
\end{figure}
Note that the shadow diagram of $\si^{-1}$ is obtained from the shadow diagram of $\si$ by
reflecting about the line $y=x$. Note also that the entries in the first row
of $P$ are precisely the $y$-coordinates of the rightmost vertices in the
shadow-lines (in the example, $1\, 3\, 5\, 7$), and the entries in the first row
of $Q$ are precisely the $x$-coordinates of the leftmost vertices in the
shadow-lines (in the example, $1\, 3\, 4\, 7$). These latter properties are
very easy to prove by induction on the stage in the Robinson-Schensted Algorithm:
consider the shadow diagram for points $(1,\si (1),\ld ,(k,\si (k))$ (obtained
visually in the above example by removing the half plane $x\ge k+0.5$ from the figure).
Then it is immediate that the Algorithm's rule for how to bump from the
first row of $P_k$ is matched precisely by the $y$-coordinates in the rightmost
vertices in the corresponding shadow diagrams (and, trivially, by the $x$-coordinates
of the leftmost vertices in the corresponding shadow diagrams). To understand
the remaining rows in $P$ and $Q$, repeat with the northeast corners of the shadow-lines
as a new set of vertices (in Figure~\ref{shaddiag}, these vertices are $(2,4), (6,2), (5,6)$).
These give the second rows of $P$ and $Q$ in the same way, and every row can be obtained
by iterating this ``northeast corner'' construction (in Figure~\ref{shaddiag}, another,
final iteration yields the point $(6,4)$, to correspond to the third rows).
An intricate, but straightforward
induction gives a proof of these facts. The reflection about $y=x$ clearly replaces the permutation $\si$ by the permutation $\si^{-1}$, but also interchanges the
roles of $P$ and $Q$.
\section{Lecture of May 10}
If permutation $\si$ maps to a pair of Young tableaux of shape $\la$, then we have described above
how the length of the longest increasing subsequence is equal to $\la_1$, the length of the
first row of the tableaux. How about the length of the other rows ? If $s$ is a subsequence, the
let its length be denoted by $|s|$. Then we have the following result of Greene: for each $j\ge 1$,
$$\la_1+\ldots +\la_j=\max\{ |s_1|+\ldots +|s_j|\},$$
where $s_1,\ldots ,s_j$ are disjoint increasing substrings in $\si$.
For example, if $\si=2\, 4\, 7\, 9\, 5\, 1\, 3\, 6\, 8$, then applying the Robinson-Schensted Algorithm,
we obtain
$$P=
\begin{tabular}{ccccc}
1&3&5&6&8\\
2&4&9&&\\
7&&&&\\
\end{tabular},
$$
so here we have $\la=(5,3,1)$. Now the length of the longest increasing subsequence
in $\si$ is indeed $\la_1 =5$ (the unique such subsequence is $2\, 4\, 5\, 6\, 8$), but when this
subsequence is omitted, the resulting sequence, $7\, 9\, 1\, 3$, has no increasing
subsequence of length $3$ (the longest has length $2$). But the two disjoint increasing
subsequences $s_1=2\, 4\, 7\, 9$ and $s_2=1\, 3\, 6\, 8$, both of length $4$, do achieve the
value $\la_1+\la_2=5+3=8=4+4$ in Greene's result above.
The enumeration of permutations with given longest increasing subsequence length is carried
out by the above bijection with pairs of Young tableaux. For example, the famous result that
the average length of longest increasing subsequence in permutations on $\{ 1,\ldots ,n\}$ is
asymptotically equal to $2\sqrt{n}$ was obtained by evaluating this average as
$$\frac{1}{n!}\sum_{\la\vdash n} \la_1\left( f^{\la}\right)^2, $$
where $f^{\la}$ denotes the number of Young tableaux of shape $\la$, and ``$\la\vdash n$'' means ``$\la$ is a partition of $n$''. In the summation, the term $\left( f^{\la} \right)^2$ accounts for the number of pairs $(P,Q)$ of Young tableaux of shape $\la$, which correspond to a permutation in which the longest increasing subsequence has length $\la_1$ (the length of the first row of $\la$). For more information about this problem see the paper: R. P. Stanley, {\em Increasing and decreasing subsequences and their variants}, Proc. ICM, 2006.
Indeed, even more simply, if our claim that Robinson-Schensted Algorithm is a bijection is true, then we must have
\begin{equation}\label{desq}
\sum_{\la\vdash n} \left(f^{\la}\right)^2 =n!
\end{equation}
Also, if the effect of the Robinson-Schensted Algorithm on the inverse of the permutation
is to interchange the tableaux, then a permutation which is its own inverse (this is
an involution) must be mapped to two copies of the same Young tableau (try the algorithm on
such a permutation,, for example, $3\, 5\, 1\, 4\, 2$), so we must have
\begin{equation}\label{deginv}
\sum_{\la\vdash n}f^{\la}=a_n,
\end{equation}
where $a_n$ is the number of involutions on $\{ 1,\ld ,n\}$. But an involution must
have only fixed points and two-cycles in its disjoint cycle representation, so from the exponential generating function methods of previous enumeration courses, we have
\begin{align*}
a_n& = \left[ \frac{x^n}{n!} \right] \exp \left( x+\frac{x^2}{2} \right) = \left[ \frac{x^n}{n!} \right] \sum_{i\ge 0} \frac{ \left( x+\frac{x^2}{2} \right)^i }{i!} \\
& = \left[ \frac{x^n}{n!} \right] \sum_{i\ge 0} \frac{x^i}{i!} \sum_{j\ge 0} {i \choose j} \left(\frac{x}{2}\right)^j \\
&= \left[ \frac{x^n}{n!} \right] \sum_{i \ge 0} \sum_{j\ge 0} \frac{1}{j! (i-j)! 2^j} x^{i+j} \\
&= n! \sum_{\substack{i , j \ge 0 \\ i+j=n}} \frac{1}{j! (i-j)! 2^j} \\
&= \sum_{j\ge 0} \frac{n!}{j! (n-2j)! 2^j},
\end{align*}
where we have set $i=n-j$ to give the final summation formula, which gives, for example, $a_0=1$, $a_1=1$, $a_2=2$, $a_3=4$, $a_4=10$.
If we consider the partitions of $4$, then it is easy to check that the numbers of Young tableaux are given by $f^{(4)}=f^{(1,1,1,1)}=1$,
$f^{(3,1)}=f^{(2,1,1)}=3$, and $f^{(2,2)}=2$. Then we get
$$\sum_{\la\vdash 4} \left( f^{\la}\right)^2 = 1^2+1^2+3^2+3^2+2^2=24 =4!, $$
which confirms~(\ref{desq}) for $n=4$. We also have
$$\sum_{\la\vdash n}f^{\la}=1+1+3+3+2=10=a_4,$$
which confirms~(\ref{deginv}) for $n=4$.
Now we will find a formula for $f^{\la}$, the number of Young tableaux of shape $\la$ for an arbitrary partition $\la$.
We begin by noting that, from~\eqref{combscsf} and~\eqref{JacTru}, we have
\begin{equation}\label{degJT}
f^{\la}=[x_1\cdots x_n] \det\left( h_{\la_j-j+i}\right)_{i,j=1,\ld ,m},
\end{equation}
where $\la=(\la_1,\ld ,\la_m)$ is a partition of $n$ with $m \le n$ parts.
We now introduce some notation that will be useful in determining $f^{\la}$ from~(\ref{degJT}).
For polynomials $F_1,F_2$ in $x_1,\ld ,x_n$, we say that $F_1 \equiv F_2$ if every monomial in $F_1 - F_2$ has
an exponent on at least one of $x_1,\ld ,x_n$ that is equal to $2$ or more. Then we immediately have
$$h_k\equiv e_k\equiv\frac{p_1^k}{k!},\qquad k\ge 0,$$
where we have used the multinomial theorem for the last $\equiv$. But if $F_1 \equiv F_2$ and $G_1 \equiv G_2$, we have $F_1\cdot G_1 \equiv F_2 \cdot G_2$, and $[x_1\cdots x_n] F_1 = [x_1\cdots x_n]F_2$, so from~(\ref{degJT}), we obtain
\begin{eqnarray*}
f^{\la}&=&[x_1\cdots x_n]\det\left(\frac{p_1^{\la_j-j+i}}{(\la_j-j+i)!}\right)_{i,j=1,\ld ,m}\\
&=& [x_1\cdots x_n]p_1^n \det\left(\frac{1}{(\la_j-j+i)!}\right)_{i,j=1,\ld ,m} \\
&=&n!\det\left(\frac{1}{(\la_j-j+i)!}\right)_{i,j=1,\ld ,m}\\
&=&\frac{n!}{\prod_{\ell=1}^m(\la_{\ell}-\ell+m)!} \det\left((\la_j-j+m)_{m-i}\right)_{i,j=1,\ld ,m}
\end{eqnarray*}
where, for the second equality, we have factored $p_1^{\la_j-j}$ out of column $j$, $j=1,\ld ,m$,
and factored $p_1^i$ out of row $i$, $i=1,\ld ,m$, and then used the fact that $\la_1+\ld +\la_m = n$. For the third equality we have used the multinomial theorem, and for the fourth equality
we have factored $((\la_j-j+m)!)^{-1}$ out of column $j$, $j=1,\ld ,m$. In the last determinant,
we are using the falling factorial notation $(x)_k = x(x-1)\cdots (x-k+1)$ for $k\ge 1$, and $(x)_0=1$. To evaluate this last determinant, we use the
following lemma. (Note that $(x)_k$ is a {\em monic} polynomial of degree $k$ in $x$ -- which means that the coefficient of the monomial of highest degree is equal to $1$.)
\begin{lemma}\label{monicpoly}
If $P_k(x)$ is a monic polynomial of degree $k$, $k\ge 0$ (and $P_k(x)=0$ for $k<0$), then
$$\det\left( P_{m-j}(x_i)\right)_{i,j=1,\ld ,m}=\prod_{1\le ik$ or $k<0$. Then we have
\begin{eqnarray*}
\left( P_{m-j}(x_i)\right)_{i,j=1,\ld ,m}
&=&\left( \sum_{\ell=1}^mP_{m-j, m-\ell}x_i^{m-\ell}\right)_{i,j=1,\ld ,m}\\
&=&\left(x_i^{m-j}\right)_{i,j=1,\ld ,m} \left( P_{m-j, m-i}\right)_{i,j=1,\ld ,m}.
\end{eqnarray*}
But $\left( P_{m-j, m-i}\right)_{i,j=1,\ld ,m}$ has $0$'s above the diagonal, and $1$'s
on the diagonal, so it has determinant equal to $1$. The result follows from the
Vandermonde determinant evaluation~\eqref{vanfinal}.
\end{proof}
\medskip
Applying Lemma~\ref{monicpoly} with $x_j =\la_j-j+m$, we have
\begin{align*}
f^{\la} &= \frac{n!}{\prod_{\ell=1}^m(\la_{\ell}-\ell+m)!} \det\left(( x_j )_{m-i}\right)_{i,j=1,\ld ,m} \\
&= \frac{n!}{\prod_{\ell=1}^m(\la_{\ell}-\ell+m)!} \det\left(( x_i )_{m-j}\right)_{i,j=1,\ld ,m} \\
&= \frac{n!}{\prod_{\ell=1}^m(\la_{\ell}-\ell+m)!} \prod_{1\le i\la_{n}$, and that
the monomial that is chosen from $e_{{\widetilde{\la}}_{\ell}}$ must
have $x_1\cdots x_{n-1}$ as a factor for $\ell\le\la_{n}$. But this
means that there are at most $\la_{n}$ factors that can contain $x_n$,
and so we conclude that $\mu_n\le\la_n$. Iterate this for $n\ge 1$ to obtain the result.
But, if we consider equation~(\ref{elemmon}) over all partitions $\la$ of $k$, then we
obtain a linear system of equations that is unitriangular (i.e., $1$'s on the diagonal), and
therefore invertible, with a unitriangular inverse that also has integer entries (once again use Cramer's rule).
Thus we can express each $m_{\mu}$ as a unique integer linear
combination of $e_{\la}$'s, and we have proved that $\{ e_{\la}:\la\vdash k\}$ is a basis for $\La^k$ over the integers.
Now define $\La=\bigoplus_{k\ge 0}\La^k$ (a vector space direct sum). Note that $\La$ is naturally also
an algebra, since we can multiply symmetric functions in the obvious way. This is
a graded algebra (graded by degree) since if $f\in\La^k$ and $g\in\La^{\ell}$,
then $f\cdot g\in\La^{k+\ell}$.
Note that, from this point of view, the fact that $\{ e_{\la}:\la\vdash k\}$ is a basis for $\La^k$ over the integers implies that the elements
of $\La$ can be written uniquely as a polynomial
in $e_1,e_2,\ld$ (written $\La={\mathbb{Z}}[e_1,e_2,\ld ]$),
which also implies that the $e_i$'s are algebraicly independent over the integers.
We define the complete symmetric functions indexed by a partition in the same multiplicative way: Let $h_{\la}=h_{\la_1}h_{\la_2}\cdots$, where $\la$ is a partition with parts $\la_1,\la_2,\ld$. As for the finite variable case, here we have $h_k=\sum_{\la\vdash k}m_{\la}$, $k\ge 1$, and $h_0=1$. In order to consider symmetric functions indexed by a partition, it will he helpful to conserve the mapping $\om$ defined by
$$\om : \La\rightarrow\La: e_i\mapsto h_i,\qquad i\ge 1,$$
which is well-defined since the $e_i$'s are algebraicly independent. Now let
$$H(t)=\sum_{k\ge 0}h_kt^k=\prod_{j\ge 1}(1-x_jt)^{-1},$$
$$E(t)=\sum_{k\ge 0}e_kt^k=\prod_{j\ge 1}(1+x_jt),$$
so we immediately have
\begin{equation}\label{EHprod}
E(t)H(-t)=1.
\end{equation}
Now apply $\om$ to this equation (i.e., on both sides, we have formal power series
in $t$, with coefficients from $\La$, so we are applying $\om$ to the coefficients),
to get
$$H(t)\om\left( H(-t)\right) =1,$$
and replace $t$ by $-t$, which gives
$$H(-t)\om\left( H(t)\right) =1.$$
Comparing this with~(\ref{EHprod}), we obtain
\[ \om\left( H(t)\right) =\frac{1}{H(-t)} = E(t), \]
and hence we conclude that
\[ \om(h_i)=e_i,\qquad i\ge 1. \]
\medskip
\section{Lecture of May 17}
We conclude that $\om$ is an involution on $\La$, so it is an \textit{automorphism}.
This implies immediately that the $h_i$'s are algebraicly independent,
that $\{ h_{\la}: \la \vdash k \}$ is a basis for $\La^k$,
and that $\La={\mathbb{Z}}[h_1,h_2,\ld ]$.
\vspace{.1in}
Next we define the power sum symmetric functions in terms of monomials by $p_k=m_{k}$, $k\ge 1$,
and $p_0=1$. Again, we let
let $p_{\la}=p_{\la_1}p_{\la_2}\cdots$, where $\la$ is a partition with parts $\la_1,\la_2,\ld$. Then we have
$$\log H(t)=\sum_{j\ge 1}\sum_{k\ge 1} x_j^k\frac{t^k}{k}=\sum_{k\ge 1}p_k\frac{t^k}{k}.$$
Differentiating this with respect to $t$, and multiplying on both sides by $H(t)$, we obtain
$$\sum_{n\ge 1}nh_nt^{n-1}=\sum_{\ell\ge 0}h_{\ell}t^{\ell}\sum_{k\ge 1}p_kt^{k-1},$$
and equating coefficients of $t^{n-1}$ on both sides, this gives
$$nh_n=\sum_{k=1}^n h_{n-k}p_k,\qquad n\ge 1$$
which means, by induction on $n$, that we can write $h_n$, $n\ge 1$, as a polynomial in the $p_i$'s with
rational coefficients. But rearranging this equation, we also have
$$p_n=nh_n-\sum_{k=1}^{n-1}h_{n-k}p_k,\qquad n\ge 1,$$
which means, by induction on $n$, that we can write $p_n$, $n\ge 1$, as a polynomial in the $h_i$'s with
integer coefficients. But since the $h_i$'s are algebraicly independent over the integers, they must also
be algebraicly independent over the rationals, so the $p_i$'s are algebraicly independent over
the rationals. Thus we have $\{ p_{\la}: \la \vdash k \}$ is a basis
for $\La^k_{\mathbb{Q}}$ (where we write $\La_{\mathbb{Q}}$ for the algebra over the set of rationals ${\mathbb{Q}}$),
and that $\La={\mathbb{Q}}[p_1,p_2,\ld ]$. Now, we have
$$\log E(t)=\sum_{k\ge 1}(-1)^{k-1}p_k\frac{t^k}{k},$$
obtained similarly to the expression for $\log H(t)$ above, and applying $\om$, we obtain
$$\log H(t)=\sum_{k\ge 1}(-1)^{k-1}\om(p_k)\frac{t^k}{k}.$$
Comparing this to the expression for $\log H(t)$ above, we have $\om(p_k)=(-1)^{k-1}p_k$, $k\ge 1$, so
$$\om (p_{\la})=(-1)^{|\la|-\ell(\la)}p_{\la},$$
for all partitions $\la$, where $|\la|=\la_1+\la_2+\ld$, and $\ell(\la)$ is the number of (positive) parts
in $\la$. This implies that $\{ p_{\la}: \la \vdash k \}$ is a basis
of eigenvectors for $\La^k_{\mathbb{Q}}$.
\vspace{.1in}
Now we introduce a bilinear form $\langle\;,\;\rangle$ on $\La$, defined by
$$\langle h_{\la},m_{\mu}\rangle =\de_{\la,\mu},$$
where $\de_{\la,\mu}=1$, if $\la=\mu$, and $\de_{\la,\mu}=0$ otherwise. This means,
if $f,g\in\La$ with $f=\sum_{\la}c_{\la}h_{\la}$ and $g=\sum_{\mu}d_{\mu}m_{\mu}$, then
$$\langle f,g\rangle = \sum_{\la}\sum_{\mu} c_{\la}d_{\mu}\langle h_{\la},m_{\mu}\rangle
=\sum_{\la}c_{\la}d_{\la}.$$
\begin{theorem}\label{equivCauch}
Suppose that $\{ u_{\la}\}$ and $\{ v_{\la}\}$ are bases for $\La_{\mathbb{Q}}$. Then
the following are equivalent:
$$\mathrm{(i)}\quad\langle u_{\la},v_{\mu}\rangle =\de_{\la ,\mu },\quad\mathrm{for}
\;\mathrm{all}\;\la ,\mu.$$
$$\mathrm{(ii)}\sum_{\la} u_{\la}(x_1,\ld )v_{\la}(y_1,\ld )=\prod_{i,j\ge 1}(1-x_iy_j)^{-1}.$$
\end{theorem}
\begin{proof}
Let $u_{\la}=\sum_{\rho}a_{\la\,\rho}h_{\rho}$, $v_{\mu}=\sum_{\si}b_{\mu\,\si}m_{\si}$. Then
$$\langle u_{\la},v_{\mu}\rangle =\sum_{\rho}\sum_{\si}a_{\la\,\rho}b_{\mu\,\si}
\langle h_{\rho},m_{\si}\rangle =\sum_{\rho} a_{\la\,\rho}b_{\mu\,\rho}=
\left( AB^t\right)_{\la\,\mu},$$
where $A,B$ are matrices with rows and columns indexed by partitions.
We also have
\begin{equation}\label{hmCauchy}
\prod_{i,j\ge 1}(1-x_iy_j)^{-1} = \prod_{j\ge 1}\sum_{k_j\ge 0}h_{k_j}(x_1,\ld )y_j^{k_j} = \sum_{\la}h_{\la}(x_1,\ld )m_{\la}(y_1,\ld ).
\end{equation}
Continuing, we have
\begin{eqnarray*}
\sum_{\la} u_{\la}(x_1,\ld )v_{\la}(y_1,\ld )&=&\sum_{\la}
\left(\sum_{\rho}a_{\la\,\rho}h_{\rho}(x_1,\ld )\right)
\left(\sum_{\si}b_{\la\,\si}m_{\si}(y_1,\ld )\right)\\
&=& \sum_{\rho,\si}h_{\rho}(x_1,\ld )m_{\si}(y_1,\ld )
\sum_{\la}a_{\la\,\rho}b_{\la\,\si}\\
&=& \sum_{\rho,\si}h_{\rho}(x_1,\ld )m_{\si}(y_1,\ld )
\left( A^tB\right)_{\rho\,\si}.
\end{eqnarray*}
Thus condition (i) is equivalent to $AB^t=I$, and (ii) is
equivalent to $A^tB=I$. But this is equivalent (by taking transposes)
to $B^tA=I$, and the result follows, since conditions~(i) and~(ii) are both equivalent
to $A^{-1}=B^t$.
\end{proof}
\medskip
Now suppose that we modify~\eqref{hmCauchy} to obtain
\[ \prod_{i,j\ge 1}(1-x_iy_j)^{-1} = \prod_{i\ge 1}\sum_{k_i\ge 0}h_{k_i}(y_1,\ld )x_i^{k_i} = \sum_{\la}m_{\la}(x_1,\ld ) h_{\la}(y_1,\ld ). \]
Then Theorem~\ref{equivCauch} tells us that $\langle m_{\la},h_{\mu}\rangle =\de_{\la ,\mu }$ $=\de_{\mu ,\la }=\langle h_{\mu},m_{\la}\rangle$, where the last equality follows from the
definition of $\langle\; ,\;\rangle$. But this implies that the bilinear form $\langle\; ,\;\rangle$ is {\em symmetric} -- i.e., $\langle\, f , g\,\rangle = \langle\, g ,f\,\rangle$ for any $f,g\in \La_{\mathbb{Q}}$.
\medskip
\section{Lecture of May 23}
For the next result, it is convenient to use the notation
$$z(\la)=1^{i_1}2^{i_2}\cdots i_1!i_2!\cdots,$$
where the partition $\la$ has $i_j$ parts equal to $j$, $j\ge 1$.
\begin{corollary}
$$\mathrm{(i)} \quad\{ p_{\la}\}\;\mathrm{is}\;\mathrm{an}\;\mathrm{orthogonal}
\;\mathrm{basis,}\;\mathrm{with}\;
\langle p_{\la},p_{\mu}\rangle = z(\la )\,\de_{\la ,\mu},$$
$$\mathrm{(ii)} \quad\langle\; ,\;\rangle\quad\mathrm{is}
\;\mathrm{positive}\;\mathrm{definite},$$
$$\mathrm{(iii)} \quad\om\;\mathrm{is}\;\mathrm{an}\;\mathrm{isometry}
\;\mathrm{for}\;\langle\; ,\;\rangle
\;\mathrm{(i.e.,}\;\langle\om(f),\om(g)\rangle=\langle f,g\rangle ,\;\mathrm{for}\;\mathrm{all}\; f,g
\mathrm{)}.$$
\end{corollary}
\begin{proof}
For part(i), we have
\begin{eqnarray*}
\prod_{i,j\ge 1}(1-x_iy_j)^{-1}&=& \exp\sum_{i,j\ge 1}\sum_{k\ge 1}\frac{x_i^ky_j^k}{k}\\
&=& \exp\sum_{k\ge 1}\frac{p_k(x_1,\ld ) p_k(y_1,\ld )}{k}
=\prod_{k\ge 1}\exp \frac{p_k(x_1,\ld ) p_k(y_1,\ld )}{k}\\
&=&\prod_{k\ge 1}\sum_{i_k\ge 0}\frac{p_k(x_1,\ld )^{i_k}p_k(y_1,\ld )^{i_k}}{k^{i_k}i_k!}\\
&=&\sum_{i_1,i_2,\ld\ge 0}\prod_{k\ge 1}
\frac{p_k(x_1,\ld )^{i_k}p_k(y_1,\ld )^{i_k}}{k^{i_k}i_k!}
=\sum_{\la}\frac{p_{\la}(x_1,\ld )p_{\la}(y_1,\ld )}{z(\la )},
\end{eqnarray*}
so Theorem~\ref{equivCauch} gives $\langle p_{\la}/z(\la ),p_{\mu}\rangle =\de_{\la ,\mu }$,
and the result follows, using bilinearity.
For part (ii), consider $f\in\La_{{\mathbb{Q}}}$, and suppose that $f=\sum_{\la}c_{\la}p_{\la}$.
Then
$$\langle f,f\rangle =\langle \sum_{\la}c_{\la}p_{\la},\sum_{\mu}c_{\mu}p_{\mu}\rangle
=\sum_{\la,\mu}c_{\la}c_{\mu}\langle p_{\la},p_{\mu}\rangle =\sum_{\la}c_{\la}^2z(\la )\ge 0,$$
and this is equal to $0$ if and only if $c_{\la}=0$ for all partitions $\la$, in which
case $f=0$, giving the result.
For part (iii), it is sufficient to prove for any basis. Using power sums, we have
$$\langle \om (p_{\la}),\om(p_{\mu})\rangle =
\langle (-1)^{|\la|-\ell(\la )}p_{\la},(-1)^{|\mu|-\ell(\mu )}p_{\mu}\rangle
=\langle p_{\la},p_{\mu}\rangle,$$
giving the result.
\end{proof}
\medskip
The fact that $\{ s_{\la}: \}$ is an orthonormal basis for $\La_{\mathbb{Q}}$ (which means that $\langle s_{\la},s_{\mu}\rangle =\de_{\la\,\mu}$ for
all partitions $\la ,\mu$), follows immediately from the following result,
by applying Theorem~\ref{equivCauch}.
\begin{theorem}\label{cauchysum}
$$\sum_{\la} s_{\la}(x_1,x_2,\ld )s_{\la}(y_1,y_2,\ld )
=\prod_{i,j\ge 1}(1-x_iy_j)^{-1}.$$
\end{theorem}
\begin{proof}
Consider an arbitrary multiset of ordered pairs of positive integers,
$\{ (i_1,j_1),\ld ,$ $(i_m,j_m)\}$, arranged so that $i_k\le i_{\ell}$ for $k<\ell$,
and so that $j_k\le j_{\ell}$ whenever $i_k = i_{\ell}$ for $k<\ell$. We
map each such multiset to a pair of tableaux of the same shape as follows:
Start with a pair $(P_0,Q_0)$ of empty tableaux. For $\ell$ from $1$ to $m$,
row-insert $j_{\ell}$ in $P_{\ell -1}$ and place $i_{\ell}$ in a new
cell added to $Q_{\ell -1}$, in the same cell in which $P_{\ell}$ differs
from $P_{\ell -1}$. The multiset is mapped to the pair $(P_m,Q_m)$. For example, suppose
$$\{ (i_1,j_1),\ld ,(i_m,j_m)\} =\{ (1,1),(1,3),(1,3),(2,2),(2,2),(3,1),(3,3)\}.$$
Then, applying the above algorithm, we obtain:
$$
P_1=
\begin{tabular}{c}
1\\
\end{tabular}
\qquad\qquad
Q_1=
\begin{tabular}{c}
1\\
\end{tabular}
,\qquad\qquad\qquad
P_2=
\begin{tabular}{cc}
1&3\\
\end{tabular}
\qquad\qquad
Q_2=
\begin{tabular}{cc}
1&1\\
\end{tabular}
$$
$$
P_3=
\begin{tabular}{ccc}
1&3&3\\
\end{tabular}
\qquad\qquad
Q_3=
\begin{tabular}{ccc}
1&1&1\\
\end{tabular}
$$
$$
P_4=
\begin{tabular}{ccc}
1&2&3\\
3&&\\
\end{tabular}
\qquad\qquad
Q_4=
\begin{tabular}{ccc}
1&1&1\\
2&&\\
\end{tabular}
$$
$$
P_5=
\begin{tabular}{ccc}
1&2&2\\
3&3&\\
\end{tabular}
\qquad\qquad
Q_5=
\begin{tabular}{ccc}
1&1&1\\
2&2&\\
\end{tabular}
$$
$$
P_6=
\begin{tabular}{ccc}
1&1&2\\
2&3&\\
3&&\\
\end{tabular}
\qquad\qquad
Q_6=
\begin{tabular}{ccc}
1&1&1\\
2&2&\\
3&&\\
\end{tabular}
$$
$$
P_7=
\begin{tabular}{cccc}
1&1&2&3\\
2&3&&\\
3&&&\\
\end{tabular}
\qquad\qquad
Q_7=
\begin{tabular}{cccc}
1&1&1&3\\
2&2&&\\
3&&&\\
\end{tabular}
$$
In this case we have mapped the multiset to the pair $(P_7,Q_7)$, which are
tableaux of the same shape.
In general, note that, by construction, $P_m$ contains $j_1,\ld ,j_m$ in its cells,
and $Q_m$ contains $i_1,\ld ,i_m$ in its cells. The proof that $P_{\ell}$ and $Q_{\ell}$ are tableaux
for every $\ell$ is identical to the proof given on pages 12 -- 14 for the Robinson-Schensted Algorithm.
This mapping is reversible by the following fact, straightforward to prove and omitted:
if $i_{\ell}=i_{\ell +1}$, $P_{\ell}$ differs from $P_{\ell -1}$ by a cell in column $a$,
and $P_{\ell +1}$ differs from $P_{\ell}$ by a cell in column $b$, then $a** \ld >\al_k\ge 0$, and
$\be_1\> \ld >\be_k\ge 0$. We write $\la=((\al_1,\ld ,\al_k)$
$|(\be_1,\ld ,\be_k))$, in \textit{Frobenius} notation.
Now suppose that $r$ is a plane partition that decomposes into
the partitions $r^{(1)},\ld ,r^{(m)}$.
For $i=1,\ld ,m$, let $r^{(i)}=(s^i|t^i)$, in
Frobenius notation, and let $a$, $b$ have columns $s^1+1,\ld ,s^m+1$,
$t^1+1,\ld ,t^m+1$, respectively (where $+1$ means to add $1$ to all parts).
For example, if $r$ is the plane partition given above, then
we have
$$
a=
\begin{tabular}{ccccc}
3&3&3&2&2\\
2&2&2&&\\
1&&&&\\
\end{tabular}
,\qquad
b=
\begin{tabular}{ccccc}
6&4&4&3&1\\
2&2&2&&\\
1&&&&\\
\end{tabular}
.
$$
Note that, by construction, $a$ and $b$ are plane partitions of the
same shape, with columns that
are \textit{strictly} decreasing. Also, if $a$, $b$ are plane partitions of $A$, $B$,
respectively, then we have $A+B-D=n$, where $D$ is the number of cells in $a$ (and in $b$),
and this is bijective. But $a$ and $b$ are precisely tableaux of the same shape, with the integers in
reverse order, so we conclude that if $P_n$ is the number of plane partitions
of $n$, $n\ge 0$, then from Theorem~\ref{cauchysum} we have
\begin{eqnarray*}
\sum_{n\ge 0} P_n x^n&=& \sum_{\la}s_{\la}(x^1,x^2,x^3,\ld )s_{\la}(x^{1-1},x^{2-1},x^{3-1},\ld )\\
&=& \prod_{i,j\ge 1}(1-x^{i+j-1})^{-1}\\
&=&\prod_{k\ge 1}(1-x^k)^{-k},
\end{eqnarray*}
a classical result of MacMahon (for the last equality, we need only to determine that
the number of solutions to $i+j-1=k$ for $i,j\ge 1$ and each fixed $k\ge 1$, is equal to $k$).
There are a number of results known for the number of plane partitions
under various restrictions. For example, suppose we want to know the
number of plane partitions that are symmetric (under reflection about the main
diagonal). For example,
\begin{equation}\label{sympp}
\begin{tabular}{cccc}
5&4&3&2\\
4&4&2&1\\
3&2&2&1\\
2&1&1&1\\
\end{tabular}
\end{equation}
is a symmetric plane partition $q$ of $38$. To enumerate these, first
decompose into partitions as above. For example, when $q$ is given in~(\ref{sympp}),
we have maximum integer $m=5$, and so we get
$$
q^{(1)}=
\begin{tabular}{cccc}
1&1&1&1\\
1&1&1&1\\
1&1&1&1\\
1&1&1&1\\
\end{tabular},\;\;
q^{(2)}=
\begin{tabular}{cccc}
1&1&1&1\\
1&1&1&\\
1&1&1&\\
1&&&\\
\end{tabular},\;\;
q^{(3)}=
\begin{tabular}{ccc}
1&1&1\\
1&1&\\
1&&\\
&&\\
\end{tabular},\;\;
q^{(4)}=
\begin{tabular}{cc}
1&1\\
1&1\\
&\\
&\\
\end{tabular},\;\;
q^{(5)}=
\begin{tabular}{c}
1\\
\\
\\
\\
\end{tabular}
$$
Note that the symmetry of $q$ implies that the partitions $q^{(i)}$ are
also symmetric, or \emph{self-conjugate}; this means that $q^{(i)}=(u^i|u^i)$ in
Frobenius notation.
Now suppose that $q$ is a symmetric plane partition that decomposes into
the partitions $q^{(1)},\ld ,q^{(m)}$.
For $i=1,\ld ,m$, let $q^{(i)}=(u^i|u^i)$, in
Frobenius notation, and let $c$ have columns $2u^1+1,\ld ,2u^m+1$,
(where $2u^i+1$ means to multiply each part of $u^i$ by $2$, and add $1$).
For example, if $q$ is the plane partition given above, then
we have
$$
c=
\begin{tabular}{ccccc}
7&7&5&3&1\\
5&3&1&1&\\
3&1&&&\\
1&&&&
\end{tabular}
.
$$
Note that, by construction, $c$ is a tableau with integers in reverse order, and
all integers are odd, so if $Q_n$ is the number of symmetric plane partitions of $n$,
then we have
$$\sum_{n\ge 0}Q_nx^n=\sum_{\la}s_{\la}(x^1,0,x^3,0,x^5,\ld ),$$
and to complete this evaluation, we could use the result
\begin{equation}\label{schsum}
\sum_{\la}s_{\la}(x_1,\ld )=\prod_{i\ge 1}(1-x_i)^{-1}\prod_{1\le j n$) then $\si^{-1}$ corresponds
to $(Q,P)$). The extension of the Robinson-Schensted correspondence that we gave in order to prove Theorem~\ref{cauchysum} is called the {\em Robinson-Schensted-Knuth} correspondence.
Applying~\eqref{schsum}, we obtain
\[ \sum_{n\ge 0}Q_nx^n = \prod_{k\ge 1} (1-x^{2k-1})^{-1} \prod_{m\ge 1}(1-x^{2m})^{- \lfloor \frac{m}{2} \rfloor} , \]
where we have used the {\em floor} function notation $\lfloor x\rfloor$ to denote the largest integer $\le x$.
\vspace{.2in}
We now finish this segment on principal specializations of Schur functions by returning to Theorem~\ref{Schprinc}, which says that
\[ s_{\la}(x^1,x^2,x^3,\ld )= \frac{x^{\sum_{i\ge 1}i\la_i}}{\prod_{\al\in\la}(1-x^{h(\al )})}. \]
We consider the question of what happens on the right hand side above when on the left hand side we truncate the substitutions $x_i=x^i$ at $i=n$, and substitute $x_i=0$ thereafter, thus obtaining
\[ s_{\la}(x^1,x^2,,\ld,x^n,0,0,\ld ). \]
We'll proceed algebraicly (though there is a combinatorial proof due to Krattenthaler in the literature).
To begin, we note that we can work with the Schur function in a finite number of variables, and thus use the determinant formula~\eqref{scsf}, which says that for a partition $\la = (\la_1,\ld ,\la_n)$ with at most $n$ parts $\la_1\ge\ld\ge\la_n\ge 0$, we have
\[ s_{\la}(x_1,\ld,x_n) = \frac{ \det \left( x_i^{\la_j +n-j} \right)_{i,j=1,\ld ,n} }{ \det \left( x_i^{n-j} \right)_{i,j=1,\ld ,n} } = \frac{\det\left(x_i^{\la_j +n-j}\right)_{i,j=1,\ld ,n}}{\prod_{1\le im+k$, then $\mu$ terminates with more than $k$ $0$'s, and we would thus be in Case 3 for each $\ell > m+k$, with $\la = (\mu_1,\ld ,\mu_m, 0,\ld , 0,1,\ld 1)$, which terminates with exactly $k$ $1$'s.
We conclude that
\begin{equation}\label{mninduct}
p_k\, s_{\mu} = \sum_{\la} (-1)^{\height(\la / \mu)} s_{\la},
\end{equation}
where the summation is over all partitions $\la$ such that $\la / \mu$ is a border strip of size $k$. This is referred to as the {\em Murnaghan-Nakayama Rule}. For example, with $k=3$ and $\mu=(4,3,1)$, we obtain
\[ p_3 \, s_{(4,3,1)} = s_{(7,3,1)} - s_{(5,5,1)} - s_{(4,3,2,2)} + s_{(4,3,1,1,1,1)} . \]
\vspace{.1in}
\section{Lecture of June 14}
Applying~\eqref{mninduct} iteratively, for an arbitrary monomial $p_{\al} = p_{\al_1}\cdots p_{\al_m}$ in the power sums, and an arbitrary partition $\mu$, we obtain the formula
\begin{equation}\label{mpartns}
p_{\al} \, s_{\la^{(0)}} = \sum (-1)^{ \height ( \la^{(1)} / \la^{(0)} ) + \ldots + \height ( \la^{(m)} / \la^{(m-1)} ) } s_{ \la^{(m)} },
\end{equation}
where the summation is over all partitions $\la^{(1)}, \ld , \la^{(m)} $ such that $ \la^{(i)} / \la^{(i-1)} $ is a border strip of size $\al_i$, for $i=1,\ldots ,m$. In order to write~\eqref{mpartns} more compactly, we now introduce a single object that captures all the above information about the sequence of partitions $\la^{(0)},\ld,\la^{(m)}$. Suppose we place integer $i$ in each cell of the border strip $ \la^{(i)} / \la^{(i-1)} $, to obtain $B_i$, and draw all of $B_1,\ld ,B_m$ in a single figure $T$. Note that the cells containing $i$ and $j$ for different $i$ and $j$ are disjoint, and that $T$ is simply the skew shape $\la^{(m)} / \la^{(0)}$ with one of the positive integers $1,\ld ,m$ placed in each cell. In particular, there are $\al_i$ occurrences of $i$ for $i=1,\ld, m$. We then say that $T$ is a {\em border strip tableau} of (skew) {\em shape} $\la^{(m)} / \la^{(0)}$ and {\em type} $\al$ (note that $\al$ need not be a partition, because the parts can appear in any order). For example, one border strip tableau of skew shape $(8,8,5,4,4,1) / (2,1,1)$ and type $(3,6,3,4,2,5,3 )$ is given by
\vspace{.1in}
\[ \begin{array}{cccccccc}
& & 1 & 2 & 2 & 6 & 6 & 7 \\
& 1 & 1 & 2 & 6 & 6 & 7 & 7 \\
& 2 & 2 & 2 & 6& & & \\
3 & 3 & 3 & 5 & & & & \\
4 & 4 & 4 & 5 & & & & \\
4 & & & & & & &
\end{array} . \]
\vspace{.1in}
\noindent
We define the height $\height(T)$ of the border strip tableau $T$ to be the sum over $i=1,\ld ,m$ of the heights of the border strips $B_i$, so for example the height of the border strip tableau given above is $1+2+0+1+1+2+1=8$. Using this notation, we can write~\eqref{mpartns} (with $\la^{(0)}$ and $\la^{(m)}$ replaced by the more generic $\mu$ and $\la$, respectively) as
\[ p_{\al} \, s_{\mu} = \sum_{\la} s_{\la} \; \sum_{T} (-1)^{\height(T)} , \]
where the inner summation is over all border strip tableaux $T$ of skew shape $\la / \mu$, and type $\al$. The special case in which $\mu$ is the empty partition is of particular interest, giving
\begin{equation}\label{mnstand}
p_{\al} = \sum_{\la} s_{\la} \; \sum_{T} (-1)^{\height(T)} ,
\end{equation}
where the inner summation is over all border strip tableaux $T$ of shape $\la$, and type $\al$. As an example of~\eqref{mnstand}, consider the case $m=2$ and $\al_1=3$, $\al_2=2$. Then there are eight border strip tableaux of type $(3,2)$, given by
\[ \begin{array}{ccc}
1&1&1\\
2&&\\
2&&
\end{array}
\quad
\begin{array}{ccc}
1&1&1\\
2&2&
\end{array}
\quad
\begin{array}{ccccc}
1&1&1&2&2
\end{array}
\quad
\begin{array}{cc}
1&1\\
1&\\
2&\\
2&
\end{array}
\quad
\begin{array}{cccc}
1&1&2&2\\
1&&&
\end{array}
\quad
\begin{array}{c}
1\\
1\\
1\\
2\\
2
\end{array}
\quad
\begin{array}{cc}
1&2\\
1&2\\
1&
\end{array}
\quad
\begin{array}{ccc}
1&2&2\\
1&&\\
1&&
\end{array} .
\]
Thus formula~\eqref{mnstand} in this case gives
\[ p_3\, p_2 = s_{(3,2)} + s_{(5)} + s_{(2,1,1,1)} - s_{(4,1)} - s_{(1,1,1,1,1)} - s_{(2,2,1)} , \]
in which the Schur function $s_{(3,1,1)}$ doesn't appear because it has coefficient $1-1=0$. For comparison, consider the case in which the $\al_i$ appear in a different order, say $\al_1=2$ and $\al_2=3$. then there are {\em six} border strip tableaux of type $(2,3)$, given by
\[ \begin{array}{cc}
1&1\\
2&\\
2&\\
2&
\end{array}
\qquad
\begin{array}{cc}
1&1\\
2&2\\
2&
\end{array}
\qquad
\begin{array}{ccccc}
1&1&2&2&2
\end{array}
\qquad
\begin{array}{c}
1\\
1\\
2\\
2\\
2
\end{array}
\qquad
\begin{array}{ccc}
1&2&2\\
1&2&
\end{array}
\qquad
\begin{array}{cccc}
1&2&2&2\\
1&&&
\end{array} ,
\]
and formula~\eqref{mnstand} in this case gives
\[ p_2\, p_3 = s_{(2,1,1,1)} - s_{(2,2,1)} + s_{(5)} - s_{(1,1,1,1,1)} + s_{(3,2)} - s_{(4,1)} . \]
Of course, these have exactly the same linear combinations of Schur functions on the right hand sides, because $p_3\, p_2=p_2\, p_3$, though the linear combinations come about in different ways as a sum over border strip tableaux -- in the second case the Schur function $s_{(3,1,1)}$ has coefficient $0$ because it simply doesn't appear at all in that summation over border strip tableaux. In general we restrict attention in~\eqref{mnstand} to the case in which $\al$ is a partition.
Note that an equivalent way of writing~\eqref{mnstand} is to use the inner product for symmetric functions, so, using the orthonormality of the $s_{\la}$, we obtain
\begin{equation}\label{charinprodSch}
\langle \, p_{\al} , s_{\la} \, \rangle = \sum_{T} (-1)^{\height(T)} ,
\end{equation}
where the inner summation is over all border strip tableaux $T$ of shape $\la$, and type $\al$. But then, using the orthogonality of the $p_{\al}$, we also obtain
\begin{equation}\label{mnPwr}
s_{\la} = \sum_{\al} \frac{ \langle \, p_{\al} , s_{\la} \, \rangle }{ \langle \, p_{\al} , p_{\al} \, \rangle } p_{\al} = \sum_{\al} \langle \, p_{\al} , s_{\la} \, \rangle \frac{ p_{\al} }{ z(\al) } ,
\end{equation}
using the notation $z(\al)$ defined on page 23 of the Course Notes. Formula~\eqref{mnPwr} in conjunction with~\eqref{charinprodSch} requires us to consider the border strip tableaux of fixed shape $\la$, with type $\al$ that varies. For example, in the case that $\la=(2,1)$, there are five border strip tableaux of shape $(2,1)$, given by
\[ \begin{array}{cc}
1&1 \\
1&
\end{array}
\qquad
\begin{array}{cc}
1&1 \\
2&
\end{array}
\qquad
\begin{array}{cc}
1&2 \\
1&
\end{array}
\qquad
\begin{array}{cc}
1&2 \\
3&
\end{array}
\qquad
\begin{array}{cc}
1&3 \\
2&
\end{array} .
\]
Hence we obtain the expression
\[ s_{(2,1)} = - \frac{ p_3}{3}+( 1-1) \frac{p_2\, p_1}{2} + (1+1) \frac{p_1^3}{3!} = \frac{ p_1^3}{3} - \frac{ p_3}{3} \]
for the Schur function $s_{(2,1)}$ expanded in power sum monomials.
The reason that so much attention has been focussed on these expansions relating the Schur function and power sum bases for symmetric functions is that the coefficient $\langle \, p_{\al} , s_{\la} \, \rangle$ features centrally in the representation theory of the symmetric groups $S(n)$, $n\ge 0$ -- in particular, for $\al$ and $\la$ partitions of $n$, the coefficient $\langle \, p_{\al} , s_{\la} \, \rangle$ is the {\em character} of the irreducible representation of $S(n)$ indexed by $\la$, evaluated at any element of the conjugacy class of $S(n)$ indexed by $\al$. In this context, expression~\eqref{charinprodSch} is referred to as the Murnaghan-Nakayama Rule for the characters.
\vspace{.2in}
We now consider the basics of representation theory for finite groups, especially the symmetric group. For a finite group $G$, a linear representation is a family of square invertible matrices $M_g$, $g\in G$,
such that $M_g M_h=M_{g\cdot h}$ (here $G$ is a multiplicative group). That is, the {\em matrix} multiplication of these matrices is homomorphic with the {\em group} multiplication of their corresponding group elements. If the matrices
are $m\times m$, then we say that $m$ is the {\em dimension} or {\em degree} of the representation.
Note that this implies $M_e=I_m$ for the
identity element $e$ in $G$, and $M_{g^{-1}}=\left( M_g\right)^{-1}$ for any $g\in G$.
For any invertible $m\times m$ matrix $P$, clearly $PM_gP^{-1}$, $g\in G$ is also a
representation. Also, if $N_g$ is also a representation (with dimension not necessarily
equal to $m$) then their block diagonal direct sum $N_g\oplus M_g$, $g\in G$ is another representation.
A key result of representation theory for finite groups is that all representations
can be formed uniquely from a special finite set of \textit{irreducible} representations
using the above two constructions (similarity via some $P$, and direct sum of not necessarily different representations).
There is one irreducible representation for each conjugacy class in the group.
Then the \textit{character} of the representation evaluated at $g\in G$ is equal
to $\trace \!(M_g)$. Note that all of the representations obtained from $M_g$, $g\in G$ by similarity have the same character, since $\trace PM_gP^{-1} = \trace M_g$ for any invertible $P$ (for example, this is an easy consequence of the result for $m\times k$ and $k\times m$ matrices $A_{m\times k}$ and $B_{k\times m}$ that $\trace A\, B = \trace B\, A$).
\section{Lecture of June 19}
In a finite group $G$, two group elements $a$ and $b$ are {\em conjugate} when there exists $x\in G$ such that $b=x\cdot a\cdot x^{-1}$. Note that $a$ and $a$ are conjugate since $a=id \cdot a \cdot id^{-1}$. Note also that $b$ and $a$ are conjugate since, multiplying the equation $b=x\cdot a\cdot x^{-1}$ on the left by $x^{-1}$ and on the right by $x$, we obtain $a = x^{-1}\cdot b\cdot x= x^{-1}\cdot b\cdot \left( x^{-1}\right)^{-1}$. Finally, suppose that we have $c=y\cdot b\cdot y^{-1}$, so $b$ and $c$ are conjugate. Then, substituting for $b$, we obtain $c= y\cdot x\cdot a\cdot x^{-1}\cdot y^{-1} = \left( y\cdot x \right) \cdot a\cdot \left( y\cdot x \right)^{-1}$, and we conclude that $a$ and $c$ are conjugate. Hence, considered as a binary relation, conjugacy is reflexive, symmetric and transitive, which implies that it is an {\em equivalence relation}. The elements of the group are thus partitioned into equivalence classes consisting of the elements that are conjugate with each other, called {\em conjugacy classes}.
Now consider an {\em abelian} group, like the cyclic group, in which the group multiplication is commutative, so $a\cdot b = b\cdot a$ for all group elements $a$ and $b$. Then if $a$ and $b$ are conjugate, we have $b=x\cdot a\cdot x^{-1} = a\cdot x\cdot x^{-1} = a\cdot id = a$, so $a$ and $b$ must be equal, which means that all conjugacy classes have size $1$.
Similarly, in any finite group $G$, the conjugacy class containing the identity element $id$ has size $1$, since if $id$ and $b$ are conjugate, then for some group element $x$ we have $b=x\cdot id\cdot x^{-1}=x\cdot x^{-1}=id$.
The main example of a finite group we shall consider is the symmetric group $S(n)$ consisting of all permutations of $\{ 1,\ld ,n\}$, for some fixed $n\ge 0$. Consider the two row representation of a permutation $\si \in S(n)$, with $1,2,\ld ,n$ in the first row, and the permuted symbols $\si(1),\ld ,\si(n)$ in then second row. For example, when $n=7$, one such two row representation is given by
\[ \left(
\begin{array}{ccccccc}
1&2&3&4&5&6&7 \\
2&4&6&1&7&5&3
\end{array}
\right) . \]
Now regard this permutation $\si$ as a bijective function on the set $\{ 1,\ld ,n\}$, and construct the {\em functional digraph} of $\si$: the vertex-set is $\{ 1,\ld ,n\}$, and there is an edge directed from $i$ to $\si(i)$ for each $i=1,\ld ,n$. Each connected component of the resulting directed graph is a directed cycle, in which the cycles have length $1$ or more, and the directed graph is referred to as the {\em disjoint cycle representation} of the permutation. For example, the disjoint cycle representation of the permutation in $S(7)$ displayed above has a $3$-cycle that sends $1$ to $2$ to $4$, and then back to $1$, and a $4$-cycle that sends $3$ to $6$ to $5$ to $7$, and then back to $3$.
Now suppose that $a$ and $b$ are conjugate in $S(n)$, with $b=\si a\si^{-1}$. If we let $a(i)=j$, then there is an edge directed from vertex $i$ to vertex $j$ in the functional digraph of $a$. Then we have
\[ b(\si(i))=\si a\si^{-1}(\si(i)) = \si (a(i) ) =\si(j), \]
and so we have an edge directed from vertex $\si(i)$ to vertex $\si(j)$ in the functional digraph of $b$. But this means that the functional digraph of $b$ is obtained from the functional digraph of $a$ by relabelling vertex $i$ by $\si(i)$ for all $i=1,\ld ,n$. This relabelling cannot change the underlying structure of the digraph, and in particular preserves the unordered collection of lengths of the disjoint cycles. Thus the conjugacy classes of $S(n)$ are indexed by the partitions of $n$ (in which the parts specify the lengths of the disjoint cycles). To determine the size of the conjugacy class with cycle lengths given by partition $\la$, suppose that $\la$ has $i_j$ parts of size equal to $j$ for each $j\ge 1$. Then from the theory of exponential generating series, the number of permutations in this conjugacy class is given by
\begin{align*}
&\left[ p_1^{i_1}p_2^{i_2}\cdots \frac{t^n}{n!} \right] \exp\left( \sum_{k\ge 1} (k-1)! p_k \frac{t^k}{k!} \right) = \left[ p_1^{i_1}p_2^{i_2}\cdots \frac{t^n}{n!} \right] \exp\left( \sum_{k\ge 1} p_k \frac{t^k}{k} \right) \\
&\; = \left[ p_1^{i_1}p_2^{i_2}\cdots \frac{t^n}{n!} \right] \prod_{k\ge 1} \exp\left( p_k \frac{t^k}{k} \right) = \left[ \frac{t^n}{n!} \right] t^n \prod_{k\ge 1} \frac{1}{k^{i_k} i_k! } = \frac{n!}{z(\la)},
\end{align*}
again using the notation $z(\la)$ that appears at the top of page 23 of the Course Notes.
Now back to irreducible representations and characters. If $g$ and $h$ are conjugate in $G$, we have $g=x\cdot h\cdot x^{-1}$ for
some $x\in G$, so $M_g=M_xM_h\left( M_x\right)^{-1}$, which gives $\trace M_g =\trace M_h$,
so characters are constant on conjugacy classes. We suppose that the group $G$ has conjugacy classes $C^{(i)}$, $i=1,\ld ,k$ (so, for example $\sum_{i=1}^k\vert C^{(i)}\vert = \vert G\vert$). The character of the irreducible representation indexed by the $i$th conjugacy class is denoted by $\chi^{(i)}$, $i=1,\ld ,k$, and the value of this character evaluated at any element of conjugacy class $C^{(j)}$ is given by $\chi^{(i)}(j)$, $j=1,\ld ,k$ (where convenient, we shall also use the notation $\chi^{(i)}(g)$ for the value of $\chi^{(i)}$ evaluated at group element $g$). The degree of $\chi^{(i)}$ is denoted by $f^{(i)}$, $i=1,\ld ,k$. Note that $f^{(i)}= \chi^{(i)}(id)$, since the trace of an $m\times m$ identity matrix is equal to $m$. A basic fact about representations of finite groups is that
\[ \sum_{i=1}^k \left( f^{(i)}\right)^2 = \vert G\vert. \]
This implies immediately for the cyclic group that $f^{(i)}=1$ for all $i=1,\ld ,k$, since in this case $k=\vert G\vert$. For the symmetric group, it turns out that $f^{(i)}$ is equal to the number of Young tableaux whose shape is give by the $i$th indexed partition of $n$.
Suppose that we have an arbitrary representation $M_g$, $g\in G$ of the group $G$, with character $\Lambda(g)$. Since all representations are formed by direct sums and similarity from irreducible representations, then we have
$\Lambda (g) = \sum_{i=1}^k n_i \chi^{(i)}(g)$ for some nonnegative integers $n_i$, $i=1,\ld ,k$ (i.e., we have taken the direct sum of $n_i$ copies of the irreducible representation with character $\chi^{(i)}$, $i=1,\ld ,k$ -- using the fact that the trace of the direct sum of square matrices $A$ and $B$ is equal to $\trace A + \trace B$).
How do we create representations? We'll now consider a classical construction for the symmetric group due to Alfred Young. In particular we will construct an irreducible representation of $S(n)$ corresponding to the partition $\la$ of $n$, for each such $\la$. the degree of this representation $f^{(\la)}$ is the number of Young tableaux of shape $\la$. Suppose $S$ and $T$ are two different Young tableaux of the same shape, and suppose that $i$ appears in different cells of $S$ and $T$. Then we say $i$ is a {\em disagreeing} number between $S$ and $T$. The {\em last-letter order} for the Young tableaux of the same shape is defined in terms of disagreeing numbers as follows: If $\ell$ is the largest disagreeing number between $S$ and $T$, and $\ell$ appears in a lower indexed row of $S$ than $T$, then we say that $S**