\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{\sH}{{\mathcal H}}
\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{\sfD}{{\mathsf{D}}}
\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 s,
\end{cases} \]
where the $x_{rs}$, $r,s=1,\ld ,n$, are real numbers. Then for any polynomial $f(H)$ in the entries of $H$, we define the matrix integral
\[ \int_{\sH_n} f(H)dH \]
to be the iterated integral over the $n^2$ reals $-\infty < x_{rs} < \infty$, where $dH = \prod_{r,s=1}^n dx_{rs}$. In the context of rooted maps in orientable surfaces, we consider the normalized integral
\[ \langle f(H)\rangle_{\sH_n} = \frac{ \int_{\sH_n} f(H)e^{-\frac{1}{2}\trace H^2} dH }{ \int_{\sH_n} e^{-\frac{1}{2}\trace H^2} dH }. \]
Note that
\[ \trace H^2 = \sum_{r,s=1}^n h_{rs}h_{sr}= \sum_{r=1}^n x_{rr}^2+2\sum_{\substack{r,s=1\\ r\neq s}}^n x_{rs}^2, \]
and that we have
\[ \int_{-\infty}^{\infty} \frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}dx = 1, \]
since $\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}$ is the probability density for $N(0,1)$, the normal distribution with mean $0$ and variance $1$. Hence we can evaluate $\langle f(H)\rangle_{\sH_n}$ for any given $f(H)$ in terms of the moments of the $N(0,1)$ distribution.
A basic fact about the normalized matrix integral $\langle f(H)\rangle_{\sH_n}$, often referred to as {\em Wick's Lemma}, is that
\begin{equation}\label{wick}
\langle h_{r_1s_1}\cdots h_{r_{\ell} s_{\ell}} \rangle_{\sH_n} =
\begin{cases}
0, \qquad\qquad \qquad\qquad \qquad\qquad \qquad\qquad \mathrm{if}\; \ell \; \mathrm{is}\; \mathrm{odd}, \\
\sum_{P} \prod_{ \{ c,d \} \in P} \langle h_{r_c s_c} h_{r_d s_d } \rangle_{\sH_n}
, \qquad\qquad\quad\, \mathrm{if}\; \ell \; \mathrm{is}\; \mathrm{even},
\end{cases}
\end{equation}
where the sum is over all matchings $P$ on the set $\{ 1,\ldots ,\ell \}$. We also have
\begin{equation}\label{pairijkm}
\langle h_{ij} \, h_{km} \rangle_{\sH_n} = \de_{im}\de_{jk},
\end{equation}
where as usual $\de_{im}= 1$ if $i=m$, and $\de_{im}=0$ otherwise.
The evaluations given in~\eqref{wick} and~\eqref{pairijkm} arise exactly in the following context: suppose we have a set of vertices of given degree, with ``half-edges'' attached, and the ``corners'' between half edges assigned one of the colours $1,\ld ,n$, with repetition allowed. For~\eqref{pairijkm}, suppose two of the half edges that are joined together are incident with vertices $v_1$ and $v_2$, as drawn in Figure~\ref{ijkmjoin}, connected by a dotted line. Suppose also that the corners above and below these half-edges are coloured $i,j,k,m$, as indicated in Figure~\ref{ijkmjoin}. Then~\eqref{pairijkm} gives an evaluation of $1$ exactly when $i=m$ and $j=k$, and in terms of the map with the edge obtained by joining these two half-edges, this occurs exactly when the consecutive corners in both of the faces incident with the edge have the same colour.
\begin{figure}[ht]
\begin{center}
\includegraphics[trim=0in 8.0in 0in .25in, width=6in]{ijkmjoin.pdf}
\end{center}
\caption{Two half edges joined together. }\label{ijkmjoin}
\end{figure}
For~\eqref{wick}, suppose that we wish to construct rooted maps with vertices of degrees $\la_1,\ld,\la_t$, and we consider
\begin{equation}\label{vtxla}
\langle \frac{1}{\la_1}\trace H^{\la_1}\cdots \frac{1}{\la_t}\trace H^{\la_t} \rangle_{\sH_n} .
\end{equation}
For example, for a vertex of degree $4$, we have $\frac{1}{4}\trace H^4$. Now a typical term in the expansion of $\frac{1}{4}\trace H^4$ is $h_{i_1,i_2}h_{i_2,i_3}h_{i_3,i_4}h_{i_4,i_1}$ (in which the division by $4$ is to remove cyclic symmetry). As pictured in Figure~\ref{tracevtx}, this corresponds to colouring the $4$ corners $i_1.i_2,i_3,i_4$, in clockwise order.
\begin{figure}[ht]
\begin{center}
\includegraphics[trim=0in 7.5in 0in 0in, width=5in]{tracevtx.pdf}
\end{center}
\caption{A vertex of degree $4$, with coloured corners. }\label{tracevtx}
\end{figure}
Then, from~\eqref{wick}, the normalized matrix integral~\eqref{vtxla} accounts for all maps with vertex degrees given by the parts of $\la$, with the half-edges matched in pairs in all possible ways. Adjustment needs to be made by rescaling to properly account for the $(2E-1)!$ labellings of the half-edges (where $E$ is the number of edges, and for the fact that the maps with $F$ faces are created $n^F$ times (since the corner colour checking in~\eqref{pairijkm} gives a product of $1$'s each time we have a face-coloured map, with $n$ choices of colour). Also, there is no guarantee that the resulting map is connected, so we need to form an exponential generating function by summing over all choices of $\la$, and then take the logarithm to get the generating function for the connected objects, as we have seen before for exponential generating functions.
Finally, suppose we wish to evaluate integrals of the form $ \int_{\sH_n} f(H)dH $, where $f(H)$ is a function, say, of the $\trace H^i$, $i\ge 1$. Then if we diagonalize matrix $H$ and change variables to its eigenvalues $\la_1,\ld ,\la_n$, we get
\[ \int_{\sH_n} f(\trace H^1,\ld)dH =\int f(p_1(\la_1,\ld ,\la_n),\ld) V(\la_1,\ld ,\la_n)^2 d\la_1\cdots d\la_n , \]
where on the right hand side we have an iterated integral over the $n$ reals $-\infty < \la_i < \infty$, and $V$ is the Vandermonde determinant.
\vspace{.1in}
Now consider rooted maps in {\em locally} orientable surfaces (the union of orientable and non-orientable surfaces). Here we consider the set $\sS_n$ of $n \times n$ real symmetric matrices. A matrix $A \in \sS_n$ is of the form $A= (a_{rs})_{n \times n}$, with entries specified by
\[ a_{rs} = \begin{cases}
x_{rs}, \qquad r \leq s,\\
x_{sr}, \qquad r> s,
\end{cases} \]
Then for any polynomial $f(A)$ in the entries of $A$, we define the matrix integral
\[ \int_{\sS_n} f(A)dA \]
to be the iterated integral over the ${n+1 \choose 2}$ reals $-\infty < x_{rs} < \infty$, where $dA = \prod_{1 \leq r \leq s \leq n} dx_{rs}$. In the context of rooted maps in locally orientable surfaces, we consider the normalized integral
\[ \langle f(A)\rangle_{\sS_n} = \frac{ \int_{\sS_n} f(A)e^{-\frac{1}{4}\trace A^2} dA }{ \int_{\sS_n} e^{-\frac{1}{4}\trace A^2} dA }. \]
Note that
\[ \trace A^2 = \sum_{r,s=1}^n a_{rs}a_{sr}= \sum_{r=1}^n x_{rr}^2+2\sum_{\substack{r,s=1\\ r < s}}^n x_{rs}^2. \]
The version of Wick's Lemma that holds for normalized integrals over real symmetric matrices is
\begin{equation}\label{wickRS}
\langle a_{r_1s_1}\cdots a_{r_{\ell} s_{\ell}} \rangle_{\sS_n} =
\begin{cases}
0, \qquad\qquad \qquad\qquad \qquad\qquad \qquad\qquad \mathrm{if}\; \ell \; \mathrm{is}\; \mathrm{odd}, \\
\sum_{P} \prod_{ \{ c,d \} \in P} \langle a_{r_c s_c} a_{r_d s_d } \rangle_{\sS_n}
, \qquad\qquad\quad\, \mathrm{if}\; \ell \; \mathrm{is}\; \mathrm{even},
\end{cases}
\end{equation}
where the sum is over all matchings $P$ on the set $\{ 1,\ldots ,\ell \}$. We also have
\begin{equation}\label{pairijkmRS}
\langle a_{ij} \, a_{km} \rangle_{\sS_n} = \de_{im}\de_{jk} + \de_{ik}\de_{jm}.
\end{equation}
The evaluations given in~\eqref{wickRS} and~\eqref{pairijkmRS} arise exactly in the following context: suppose we have a set of vertices of given degree, with ``half-edges'' attached, and the ``corners'' between half edges assigned one of the colours $1,\ld ,n$, with repetition allowed. For~\eqref{pairijkmRS}, suppose two of the half edges that are joined together are incident with vertices $v_1$ and $v_2$, as drawn in Figure~\ref{ijkmtwo}. Here, since we are in a locally orientable surface, there are two cases: the edges can be joined as in the orientable case (pictured on the left side of Figure~\ref{ijkmtwo}), or they can be ``twisted'', and joined in the opposite way (pictured on the right side of Figure~\ref{ijkmtwo}). Suppose also that the corners above and below these half-edges are coloured $i,j,k,m$, as indicated in Figure~\ref{ijkmtwo}. Then~\eqref{pairijkmRS} gives an evaluation of $1$ when $i=m$ and $j=k$, or when $i=k$ and $j=m$, and $2$ when $i=j=k=m$. In terms of the map with the edge obtained by joining these two half-edges, with or without a twist, these cases occurs exactly when the consecutive corners in both of the faces incident with the edge (and on the correct side of the edge) have the same colour.
\begin{figure}[ht]
\begin{center}
\includegraphics[trim=.5in 8.5in 0in .25in, width=6in]{ijkmtwo.pdf}
\end{center}
\caption{Two half edges joined together, with or without a ``twist''. }\label{ijkmtwo}
\end{figure}
For~\eqref{wickRS}, suppose that we wish to construct rooted maps with vertices of degrees $\la_1,\ld,\la_t$, and we consider
\begin{equation}\label{vtxlaRS}
\langle \frac{1}{\la_1}\trace A^{\la_1}\cdots \frac{1}{\la_t}\trace A^{\la_t} \rangle_{\sS_n} .
\end{equation}
Then, from~\eqref{wickRS}, the normalized matrix integral~\eqref{vtxlaRS} accounts for all maps with vertex degrees given by the parts of $\la$, with the half-edges matched in pairs in all possible ways, and then twisted or not. Adjustment needs to be made by rescaling to properly account for the $(2E-1)!$ labellings of the half-edges (where $E$ is the number of edges, and for the fact that the maps with $F$ faces are created $n^F$ times (since the corner colour checking in~\eqref{pairijkmRS} gives a product of $1$'s each time we have a face-coloured map, with $n$ choices of colour). Also, there is no guarantee that the resulting map is connected, so we need to form an exponential generating function by summing over all choices of $\la$, and then take the logarithm to get the generating function for the connected objects, as we have seen before for exponential generating functions.
Finally, suppose we wish to evaluate integrals of the form $ \int_{\sS_n} f(A)dA $, where $f(A)$ is a function, say, of the $\trace A^i$, $i\ge 1$. Then if we diagonalize matrix $A$ and change variables to its eigenvalues $\la_1,\ld ,\la_n$, we get
\[ \int_{\sS_n} f(\trace A^1,\ld)dA =\int f(p_1(\la_1,\ld ,\la_n),\ld) \, \vert V(\la_1,\ld ,\la_n) \vert \, d\la_1\cdots d\la_n , \]
where on the right hand side we again have an iterated integral over the $n$ reals $-\infty < \la_i < \infty$.
\vspace{.2in}
\section{Lecture of July 19}
We now consider rooted maps embedded in locally orientable surfaces via algebra - analogous to the use of conjugacy classes in the symmetric group for rooted maps embedded in orientable surfaces. For example, in Figure~\ref{projmap} we have a rooted map embedded in the projective plane (note that in the rectangular drawing, the top boundary is identified with the bottom boundary, but with the direction reversed; also, the left boundary is identified with the right boundary, but with the direction reversed).
\begin{figure}[ht]
\begin{center}
\includegraphics[trim=1.5in 7.7in 1.5in 0in, width=7in]{projmap.pdf}
\end{center}
\caption{A map in the projective plane. }\label{projmap}
\end{figure}
In a similar way that we used for rooted maps in orientable surfaces, we have assigned $4$ of numbers $1,\ld ,4E$ as labels to each of the $E$ edges, with one label at each end and side of each edge. The label $1$ is reserved for the root position, so there are $(4E-1)!$ different ways to label each rooted map. One such labelling is displayed in Figure~\ref{projmap}. We now create three matchings $M_s$ , $M_e$ , $M_c$ on the set $\{ 1,\ld ,4E\}$: the pairs of $M_s$ are the labels on the same side of each edge, the pairs of $M_e$ are the labels at the same end of each edge, and the pairs of $M_c$ are the labels in each corner around a vertex. For example, from the diagram in Figure~\ref{projmap}, we obtain
\begin{align*}
M_s &= \{ 1\, 13, 2\, 20,3\, 18, 4\, 14,5\, 12,6\, 10,7\, 11,8\, 19,9\, 17,15\, 16 \}, \\
M_e &= \{ 1\, 5, 2\, 6,3\, 14, 4\, 18,7\, 19,8\, 11,9\, 15,10\, 20,12\, 13,16\, 17 \}, \\
M_c &= \{ 1\, 20, 2\, 9,3\, 18, 4\, 10,5\, 14,6\, 16,7\, 17,8\, 12,11\, 13,15\, 19 \},
\end{align*}
where we have omitted the brace brackets and commas for the individual pairs in the matchings. Note that in general if we superimpose two matchings, then we always obtain a set of cycles of even lengths - if we superimpose the matchings $M_s$ and $M_e$, we get a graph with cycles of length $4$ only; if we superimpose $M_e$ and $M_c$, we get a graph with cycles of lengths $2\la_1,\ld 2\la_t$, where $\la_1,\ld ,\la_t$ are the vertex degrees; if we superimpose $M_s$ and $M_c$, we get a graph with cycles of lengths $2\nu_1,\ld ,2\nu_r$, where $\nu_1,\ld ,\nu_r$ are the face degrees.
Now we describe an algebraic setting in which triples of matchings occur in a natural way. We consider the symmetric group $S(2m)$, acting on symbols $1,\widehat{1},\ld ,m,\widehat{m}$. Let $B(m)$ be the hyperoctahedral subgroup of $S(2m)$ that fixes the matching $\{ 1 \, \widehat{1},\ld ,m\, \widehat{m} \}$. Thus there are $2^m\, m!$ permutations in $B(m)$. For any permutation $\si \in S(2m)$, the {\em twin matching diagram} is a graph with vertices $(i,\si(i))$, for $i \in \{ 1,\widehat{1},\ld ,m,\widehat{m} \}$, and two types of edges. Solid edges are drawn between vertices $(i,\si(i))$ and $(\, \widehat{i}, \si( \, \widehat{i} \, ))$, and dotted edges are drawn between vertices $(\si^{-1}(i),i)$ and $(\si^{-1}( \, \widehat{i} \, ), \widehat{i} \, )$, for $i=1,\ld ,m$.
\begin{figure}[ht]
\begin{center}
\includegraphics[trim=0in 8in 0in 0in, width=6in]{doubdiag.pdf}
\end{center}
\caption{The twin matching diagram of a permutation on an even set. }\label{doubdiag}
\end{figure}
For example, the twin matching diagram for the permutation with cycles $( 1\, \widehat{3} \, 2\, \widehat{1} \, 4 \, \widehat{4} \, 3 )$, $( \, \widehat{2} \, \widehat{5}\, )$ and $(5)$ is displayed in Figure~\ref{doubdiag}. Of course, because the twin matching diagram of $\si$ consists of two superimposed matchings, its components are cycles of even length. Note that if we multiply $\si$ on the right by an element $b_1$ of the hyperoctahedral group, then the cycles in the diagram of $\si \, b_1$ have exactly the same lengths, and if we multiply $\si$ on the left by an element $b_2$ of the hyperoctahedral group, then the cycles in the diagram of $b_2 \, \si $ also have exactly the same lengths. Thus, if we consider double cosets $b_2\, \si \,, b_1$ in $S(2m)$, where $b_1,b_2\in B(m)$, then the double cosets are indexed by the cycle lengths in the twin matching diagram. Hence for a partition $\la$ of $m$ let $\sfD_{\la}$ be the formal sum, in the group algebra of $S(2m)$, of the permutations whose twin matching diagram has even cycles whose lengths are given by $2\la_1,\ld$ (where the parts of $\la$ are given by $\la_1,\ld$). Then the $\sfD_{\la}$ form a commutative algebra for which the coefficient
\begin{equation}\label{condcosets}
\left[ \sfD_{\nu} \right] \sfD_{\mu}\sfD_{\la}
\end{equation}
can be combinatorially identified as $\vert \sfD_{\nu} \vert / \vert B(m) \vert^2$ times the number of matchings $M_1$, $M_2$, $M_3$ such that, when we superimpose $M_1$ and $M_3$, we get cycles of lengths $2\nu$, when we superimpose $M_1$ and $M_2$, we get cycles of lengths $2\mu$, when we superimpose $M_2$ and $M_3$, we get cycles of lengths $2\la$. This means that we can use the double cosets $\sfD_{\la}$ to enumerate rooted maps in locally orientable surfaces in an analogous way that we used the conjugacy classes $\sfC_{\la}$ to enumerate rooted maps in orientable surfaces, with a suitable scaling. In the orientable case, we were then able to exploit the connection between multiplication of the $\sfC_{\la}$ and the Schur symmetric functions to obtain the exponential generating function for rooted maps as the logarithm of a Schur function summation. It turns out, that in the locally orientable case, there is a similar connection between multiplication of the $\sfD_{\la}$ and the zonal symmetric functions, which then gives the exponential generating function for rooted maps as the logarithm of a zonal function (usually referred to as ``zonal polynomial'') summation.
\vspace{.2in}
Now we consider {\em Jack} symmetric functions, which give zonal symmetric functions as a special case. Define the inner product $\langle \; , \; \rangle_{\al}$ on $\La_{\mathbb{Q}(\al)}$, the algebra of symmetric functions with coefficients that are rational functions of $\al$ with rational coefficients, by
\[ \langle \, p_{\la}\, , \, p_{\mu} \, \rangle_{\al} = \de_{\la \, \mu} z(\la) \al^{l(\la)}. \]
Then the Jack symmetric functions $\{ J_{\la}(x_1,\ld ;\al)\}$ are a basis for $\La_{\mathbb{Q}(\al)}$ determined by:
\begin{itemize}
\item
$\langle \, J_{\la}\, , \, J_{\mu}\, \rangle_{\al} = 0,\qquad \la \neq \mu$,
\item
$\left[ m_{\mu} \right] J_{\la} = 0, \qquad \mathrm{unless}\; \mu\leq \la$,
\item
$\left[ m_{(1^n)} \right] J_{\la} = n!, \qquad \la\vdash n$.
\end{itemize}
In the second condition above, $\leq$ is reverse lexicographic order. Note that when $\al=1$, then $ \langle \, , \, \rangle_{1}$ is the usual inner product $ \langle \, , \, \rangle $ that we have previously encountered. Indeed, for the new inner product, we can compute the analogous sum
\begin{align*}
\sum_{\la} \frac{ p_{\la}(x_1,\ld ) p_{\la}(y_1,\ld ) }{ \langle \, p_{\la}\, , \, p_{\la}\, \rangle_{\al} } &= \sum_{\la} \frac{ p_{\la}(x_1,\ld ) p_{\la}(y_1,\ld ) }{ z(\la) {\al}^{l(\la)} } \\
&= \sum_{k_1,k_2,\ld \geq 0} \prod_{m \geq 1} \frac{p_m(x_1,\ld )^{k_m} p_m(y_1,\ld )^{k_m} }{ m^{k_m} \, {\al}^{k_m} k_m! }\\
&= \exp \left( \frac{1}{\al} \sum_{m\ge 1} \frac{1}{m} p_m(x_1,\ld ) p_m(y_1,\ld ) \right) \\
&= \exp \left( \frac{1}{\al} \sum_{j,i,m \ge 1} \frac{1}{m} x_i^m y_j^m \right) \\
&= \prod_{i,j \ge 1} \exp \left( \frac{1}{\al} \log( (1-x_i y_j)^{-1} \right) \\
&= \prod_{i,j \ge 1} (1-x_i y_j)^{-\frac{1}{\al}} .
\end{align*}
It is now straightforward to prove the analogue of Theorem~\ref{equivCauch}, that bases $\{ u_{\la}\}$ and $\{v_{\la}\}$ for $\La_{\mathbb{Q}(\al)}$ are orthonormal for the inner product $\langle \; , \; \rangle_{\al}$ (i.e., $\langle \, u_{\la} \, , \, v_{\mu} \, \rangle_{\al}=\de_{\la , \mu}$) if and only if
\[ \sum_{\la} u_{\la}(x_1,\ld ) v_{\la}(y_1,\ld ) = \prod_{i,j \ge 1} (1-x_i y_j)^{-\frac{1}{\al}} . \]
In particular, this means that
\begin{equation}\label{JackCauch}
\sum_{\la} \frac{ J_{\la}(x_1,\ld ;\al ) J_{\la}(y_1,\ld ;\al) }{ \langle \, J_{\la}\, , \, J_{\la}\, \rangle_{\al} } = \prod_{i,j \ge 1} (1-x_i y_j)^{-\frac{1}{\al}} .
\end{equation}
\vspace{.2in}
\section{Lecture of July 24}
We now describe two special cases of the Jack symmetric functions. When $\al=2$, the Jack functions become the zonal polynomials that have appeared in the enumeration of rooted maps in nonorientable surfaces (arising from the commutative algebra of double cosets).When $\al=1$, the Jack functions are almost the same as Schur functions - note that when $\al = 1$, the first two bulleted conditions for the Jack functions are satisfied by Schur functions. However, the third bulleted condition is not satisfied by Schur functions, since we have
\[ \left[ m_{(1^n)} \right] s_{\la} = f^{\la} = \frac{n!}{\prod_{x\in\la}h(x)}, \qquad \la\vdash n \]
from~\eqref{hookform}. This implies that when~$\al=1$, the Jack functions become~$H_{\la}\, s_{\la}$, the scalar multiple of Schur functions where $H_{\la} = \prod_{x\in\la}h(x)$. It turns out that hooks are featured in almost every formula associated with Jack functions. For example, the value on the diagonal of the inner product $ \langle \, , \, \rangle_{\al}$ that appeared in the denominator of the summation in~\eqref{JackCauch} is given by
\begin{equation}\label{inprodJ}
\langle \, J_{\la}\, , \, J_{\la}\, \rangle_{\al} = \prod_{x\in \la} (L(x) + \al A(x) + \al ) (L(x) + \al A(x) + 1),
\end{equation}
where as in~\eqref{hookform}, $x\in\la$ means that $x$ is a cell in the Ferrers graph of $\la$. The value of $L(x)$, often called the ``leg-length'' for cell~$x$, is the number of cells strictly below and in the same column as $x$, and the value of $A(x)$, often called the ``arm-length'' for cell~$x$, is the number of cells strictly to the right of and in the same row as $x$. Note that~\eqref{inprodJ} specializes in the case~$\al=1$ to
\[ \langle \, J_{\la}\, , \, J_{\la}\, \rangle_{1} = \prod_{x\in \la} (L(x) + A(x) + 1) (L(x) + A(x) + 1) = \prod_{x\in\la} h(x)^2 = H_{\la}^2, \]
which is consistent with the specialization $J_{\la}=H_{\la}\, s_{\la}$ when $\al=1$.
Unlike Schur functions, there are relatively few explicit formulas known for Jack functions. For example, there are no known deteminantal formulas that would generalize the ratio of alternants or Jacobi-Trudi formulas. There is however a combinatorial formula in the spirit of the tableau description for Schur functions. This was given by Knop and Sahi in 1997 for variables $x_1,\ld ,x_n$, and involves placing positive integers $1,\ld ,n$ in each cell of the Ferrers graph of~$\la$, to form an {\em array} of shape $\la$ (N.B., in an array, there is no requirement for row weakness nor column strictness as in a tableau). The formula is
\begin{equation}\label{Jackarray}
J_{\la} = \sum_{T} d_T(\al) \prod_{k=1}^n x_k^{N_k},
\end{equation}
where the sum is over {\em admissible} arrays $T$ of shape $\la$, and $N_k$ is the number of cells containing $k$ in $T$, $k=1,\ld ,n$. To define admissible, let $T(i,j)$ denote the integer in the cell in row $i$ and column $j$ of array $T$. Then~$T$ is an admissible array if
\begin{itemize}
\item
$T(i,j) \neq T(i^{\prime},j),\qquad \qquad i^{\prime} > i$ ,
\item
$T(i,j) \neq T(i^{\prime},j-1),\qquad\, i^{\prime} < i, \; j > 1$ .
\end{itemize}
A cell~$(i,j)$ in~$\la$ is {\em critical} in $T$ if $T(i,j)=T(i,j-1)$, $j > 1$, and we define
\[ d_T(\al) = \prod_x (L(x)+\al A(x) + \al + 1), \]
where the product is over all critical cells $x$ in $T$. One of the immediate consequences of the combinatorial formula~\eqref{Jackarray} is the remarkable property that Jack functions are polynomials in $\al$ with positive integer coefficients.
Among the many other families of symmetric functions, one that is currently studied by many researchers is Macdonald symmetric functions, a two-parameter generalization of Jack functions.
\vspace{.2in}
For our final topic, we will consider {\em supersymmetric} functions. For a combinatorial definition, we consider tableaux of skew shape $\la / \mu$, in which {\em integers} (not simply positive integers) are placed in the cells so that the rows are weakly increasing left to right, and the columns are strictly increasing top to bottom. Let $X=\{ \ld ,x_{-1},x_0,x_1,\ld \}$ and $Y=\{ \ld ,y_{-1},y_0,y_1,\ld \}$. Then we define
\begin{equation}\label{superG}
G_{\la / \mu}(X,Y) = \sum_T \prod_{z\in \la / \mu} \left( x_{T(z)} + y_{T(z) + c(z)} \right),
\end{equation}
where the sum is over all tableaux $T$ of skew shape $\la / \mu$, the integer in cell $z$ is denoted by $T(z)$, and $c(z)$ is the content of cell $z$.
One specialization of the supersymmetric function $G_{\la /\mu}$ that is immediate is
\begin{equation}\label{Xonly}
[ G_{\la / \mu}(X,0)=s_{\la / \mu}(X).
\end{equation}
For another specialization, given a tableau of skew shape $\la / \mu$, suppose that we place the integer $T(z)+c(z)$ in cell $z$ for each $z\in \la / \mu$. Then the resulting entries are strictly increasing from left to right along each row, and weakly increasing from top to bottom down each column. Hence, reflecting about the main diagonal, we obtain a tableau of shape $\la' / \mu'$, and thus we have the specialization
\begin{equation}\label{Yonly}
G_{\la / \mu}(0,Y)=s_{\la' / \mu'}(Y).
\end{equation}
Noting that $T(z)=(T(z)+c(z))-c(z)= (T(z)+c(z))+c(z')$, where $z'$ is the image of cell $z$ when the skew shape is reflected about the main diagonal, we also obtain the symmetry result
\begin{equation}\label{XYswap}
G_{\la / \mu} (X,Y) = G_{\la' / \mu'} (Y,X) .
\end{equation}
{}From the definition~\eqref{superG} of $G_{\la / \mu}(X,Y)$, we can interpret it as a generating function in a straightforward way. Suppose that $\la / \mu$ has $k$ cells, and that $T$ is a tableau of skew shape $\la / \mu$. Then we create $2^k$ {\em circled} tableaux from $T$, by arbitrarily placing a circle around the entries in some subset of the cells of $\la / \mu$, in all possible ways. Then $G_{\la / \mu}(X,Y)$ is the generating function for all circled tableaux of skew shape $\la / \mu$, in which each uncircled entry $j$ is marked by $x_j$, and each circled entry $j$, in cell $z$, is marked by $y_{j+c(z)}$.
This interpretation allows us to prove a fact about $G_{\la / \mu}(X,Y)$ that may seem surprising in view of the form of~\eqref{superG}: the series $G_{\la / \mu}(X,Y)$ is symmetric in the $x_i$'s (keeping the $y_j$'s fixed)! To prove this, we proceed as in the proof that the Schur functions are symmetric, on pages 8 and 9 of the Course Notes. Since every permutation can be written as a product of adjacent transpositions, we prove for the adjacent transposition that interchanges $i$'s and $i+1$'s. For any integer $i$, and any tableau $T$ of skew shape $\la / \mu$, consider the cells that contain $i$ and $i+1$ (in both cases, circled or uncurled). These cells must appear in $T$ as disjoint collections, each of the form that appears in either the bottom portion or the top portion of Figure~\ref{supersyminv} (in which $i=2$) -- horizontal segments containing a weakly increasing sequence of circled or uncircled $i$'s and $i+1$'s, with vertical pairs containing an $i$ above an $i+1$ (circled or uncircled), in between.
\begin{figure}[ht]
\begin{center}
\includegraphics[trim=.5in 7.5in 0in 0in, width=8in]{supersyminv.pdf}
\end{center}
\caption{The cells containing $2$'s and $3$'s in a tableau. }\label{supersyminv}
\end{figure}
Define a mapping $\ga_i$ on such circled tableaux as follows.
\begin{itemize}
\item
for each vertical pair $i$ above $i+1$ in which either both are circled or neither is circled, do nothing,
\item
for each vertical pair $i$ above $i+1$ in which exactly one is circled, transfer the circle to the other,
\item
replace each horizontal segment containing $k$ uncircled $i$'s followed by $m$ uncircled $i+1$'s in some set of $k+m$ cells (there are possibly interleaved cells containing circled $i$'s and $i+1$'s), by a horizontal segment containing $m$ $i$'s followed by $k$ $i+1$'s, in the same set of $k+m$ cells; the circled entries are unchanged, and so the entries in the resulting horizontal segment might not be weakly increasing, in which case there are occurrences of (a) an uncircled $i+1$ immediately to the left of a circled $i$, or (b) a circled $i+1$ immediately to the left of an uncircled $i$; replace each pair of type (a) by a circled $i+1$ immediately to the left of an uncircled $i+1$, and each pair of type (b) by an uncircled $i$ immediately to the left of a circled $i$.
\end{itemize}
It is straightforward to check that $\ga_i$ is an involution that interchanges the exponents on $x_i$ and $x_{i+1}$ (which are, respectively, the numbers of cells containing uncircled $i$'s and $i+1$'s), and that leaves the exponents on the $y_j$'s unchanged. For the latter, note in the description of $\ga_i$ that when we replace a circled $i$ by a circled $i+1$, the newly circled entry is in a cell whose content is reduced by $1$, and that when we replace a circled $i+1$ by a circled $i$, the newly circled entry is in a cell whose content is increased by $1$; in both cases, this leaves the $y_j$'s unchanged. For example, $\ga_2$ interchanges the top and bottom portions of Figure~\ref{supersyminv}.
Now that we have proved that $G_{\la / \mu}(X,Y)$ is symmetric in the $x_i$'s for all skew shapes $\la / \mu$, the fact that it is also symmetric in the $y_i$'s follows immediately from~\eqref{XYswap}. This is perhaps the reason that these are referred to as ``supersymmetric''. In fact, the following summation expression for $G_{\la / \mu}(X,Y)$ is explicitly symmetric both in~$X$ and~$Y$, and interpolates between~\eqref{Xonly} and~\eqref{Yonly}:
\begin{equation}\label{nestXY}
G_{\la / \mu}(X,Y) = \sum_{\mu\subseteq\nu\subseteq\la} s_{\nu / \mu}(X) s_{\la' / \nu'}(Y).
\end{equation}
Though we won't provide the details here, it is quite straightforward to prove~\eqref{nestXY} by interpreting all circled entries in a circled tableau as larger than the uncircled entries, and then moving them deterministically to the right and down. It is immediate by comparing~\eqref{nestXY} and~\eqref{skewzy} that
\[ G_{\la / \mu}(X,Y) = \omega_{Y}\left( s_{\la / \mu}(X,Y) \right) , \]
where $\omega_Y$ is the involution $\omega$ defined on page 20 of the Course Notes, but acting only on $Y$.
The final class of symmetric functions that we mention are the {\em factorial} Schur functions, defined for skew shape $\la /\mu$ by
\[ t_{\la / \mu}(x_1,\ld ) = \sum_T \prod_{z\in \la / \mu} \left( x_{T(z)} - T(z) - c(z) + 1 \right). \]
By comparing this summation to~\eqref{superG}, it is clear that the factorial symmetric function $t_{\la / \mu}$ can be obtained as the specialization $y_j=-j+1$ of the super symmetric function $G_{\la / \mu}$. The name {\em factorial} is used because one of its properties for non-skew shapes is the following analogue of the ratio of alternants formula for the Schur function $s_{\la}(x_1,\ld ,x_n)$:
\[ t_{\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} } , \]
where we are using the falling factorial notation $(x)_k=x(x-1)\cdots (x-k+1)$.
\end{document}
**