#  Character polynomials for two rows and hook partitions
University of Western Ontario

Ahmed Umer Ashraf

###### Abstract

Representation theory of the symmetric group $\mathfrak{S}_{n}$ has a very
distinctive combinatorial flavor. The conjugacy classes as well as the
irreducible characters are indexed by integer partitions $\lambda\vdash n$. We
introduce class functions on $\mathfrak{S}_{n}$ that count the number of
certain tilings of Young diagrams. The counting interpretation gives a uniform
expression of these class functions in the ring of character polynomials, as
defined by [Mur37]. A modern treatment of character polynomials is given in
[OZ15]. We prove a relation between these combinatorial class functions in the
(virtual) character ring. From this relation, we were able to prove Goupil’s
generating function identity [Gou99], which can then be used to derive Rosas’
formula [Ros00] for Kronecker coefficients of hook shape partitions and two
row partitions.

###### Contents

  1. 1 Introduction
    1. 1.1 Partitions and compositions
    2. 1.2 Representation theory of symmetric group $\mathfrak{S}_{n}$
    3. 1.3 Brick tilings
    4. 1.4 Tiling class functions
    5. 1.5 Doubilet’s inversion formula
    6. 1.6 Face numbers of permutohedron
  2. 2 Combinatorics of tiling class functions
    1. 2.1 Character polynomials
    2. 2.2 Characters corresponding to two row partitions
    3. 2.3 Characters corresponding to hook partitions
    4. 2.4 The Tiling poset
    5. 2.5 Counting proof
  3. 3 Applications
    1. 3.1 Stability for sequence of polynomials and power series
    2. 3.2 The cycle-index generating function
    3. 3.3 Goupil’s generating function identity
    4. 3.4 Rosas’ formula for certain Kronecker coefficients

##  1 Introduction

Representation theory of the symmetric group $\mathfrak{S}_{n}$ employs a good
amount of combinatorics of (integer) partitions of $n$. The irreducible
representations of $\mathfrak{S}_{n}$ are indexed by partitions. One way to
generate these irreducible representations is through constructing a vector
space $M^{\lambda}$ generated by equivalence classes of tableaux, called
_tabloids_ of shape $\lambda$. And then show that each $M^{\lambda}$ contains
an irreducible representation of $\mathfrak{S}_{n}$ as a subspace. The number
of tabloids of shape $\lambda$ can also be viewed as certain tilings of Young
diagram of shape $\lambda$. This motivates us to define class functions over
$\mathfrak{S}_{n}$ that count certain tilings we call _brick tilings_. In this
section, we review representations theory of $\mathfrak{S}_{n}$, and define
these class functions. We also recall Doubilet’s inversion formula, and face
numbers of permutohedron which will be of use in the later sections.

###  1.1 Partitions and compositions

A _partition_ $\lambda$ of a positive integer $n$, denoted as $\lambda\vdash
n$, is a weakly decreasing sequence
$\lambda=(\lambda_{1},\lambda_{2},\cdots,\lambda_{r})$ of positive integers
adding up to $n$. The positive integers $\lambda_{i}$ are called _parts_ of
$\lambda$, and the number of parts is called the _length_ of $\lambda$,
denoted as $\ell(\lambda)$. If we want to emphasize that $\ell(\lambda)=r$, we
write $\lambda\vdash_{r}n$. In relation to $\lambda$, the integer $n$ is
called the _weight_ of $\lambda$, and it is denoted by $|\lambda|$. It is also
useful to write $\lambda=(1^{m_{1}},2^{m_{2}},\dots,n^{m_{n}})$, where $m_{i}$
denote the multiplicity of $i$ in the partition $\lambda$. Given a partition
$\lambda\vdash n$, the _reduced partition_ $\left<\lambda\right>$ is a
partition of $n-\lambda_{1}$ defined as
$\left<\lambda\right>=(\lambda_{2},\dots,\lambda_{r})\vdash|\lambda|-\lambda_{1}$.
Similarly, for a partition $\lambda\vdash k$, and a positive integer $n\geq
k+\lambda_{1}$, the _augmented partition_ $\lambda[n]$ is a partition of $n$
defined as $\lambda[n]=(n-k,\lambda_{1},\cdots,\lambda_{r})$. In other words,
the _reduced partition_ $\left<\lambda\right>$ is a partition we get by
removing the first part of $\lambda$, while the augmented partition is a
partition we get by augmenting a suitable first part to $\lambda$. We identify
partition $\lambda$ with its Young diagram, which is a finite collection of
unit cells arranged in left justified rows with $\lambda_{i}$ cells in the
$i$th row. A Young tableau of shape $\lambda$, is a labeling of the cells of
the Young diagram of $\lambda$ with integers $1,2,\dots,n$, with each number
occurring exactly once.

A composition $\mu$ of a positive integer $n$, denoted as $\mu\vDash n$, is a
sequence $(\mu_{1},\mu_{2},\cdots,\mu_{r})$ of positive integers adding to
$n$. We extend the definitions and notation introduced above for partitions to
compositions. Given a composition $\mu$, we denote by $\tilde{\mu}$ the
partition obtained by rearranging the parts of $\mu$ in weakly decreasing
order.

For any positive integer $n$, let $\mathsf{Comp}(n)$ denote the set of all
compositions of $n$. We define a partial order on $\mathsf{Comp}(n)$ in the
following manner: Given two compositions $\nu=(\nu_{1},\dots,\nu_{s})$ and
$\mu=(\mu_{1},\dots,\mu_{t})$ in $\mathsf{Comp}(n)$, we say that $\mu$ covers
$\nu$, and write $\nu\lessdot\mu$ if $\ell(\mu)=\ell(\nu)+1$ and there exists
a unique $j$ such that

$\displaystyle\mu_{i}$ $\displaystyle=\begin{cases}\nu_{i}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{for}\leavevmode\nobreak\
i<j\\\ \nu_{i}+\nu_{i+1}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ &\text{for}\leavevmode\nobreak\ i=j\\\
\nu_{i+1}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
&\text{for}\leavevmode\nobreak\ i>j\end{cases}$

i.e. the covering relations are given by adding adjacent entries. The partial
order on $\mathsf{Comp}(n)$ induced by this relation is denoted by $\leq$. For
instance, in figure 1 we see the Hasse diagram of this partial order on
$\mathsf{Comp}(5)$.

(1, 1, 1, 1, 1) (2, 1, 1, 1) (1, 2, 1, 1) (1, 1, 2, 1) (1, 1, 1, 2) (1,2,2)
(3,1,1) (1,3,1) (1,1,3) (2,2,1) (2,1,2) (4,1) (1, 4) (3,2) (2,3) (5) Figure 1:
Poset of composition $\mathsf{Comp}(5)$

We identify the abstract group $\mathfrak{S}_{n}$ with the group of
permutations on the set $[n]=\\{1,2,\dots,n\\}$. Let $w$ be an element of
$\mathfrak{S}_{n}$, then $w$ can be written as a product of pairwise disjoint
cycles, called _cyclic factors_ of $w$. Let $r$ denote the number of these
cyclic factors including the fixed points (1-cycles). Let $l_{i}$ be their
lengths for $i=1,\dots,r$. By choosing an element $j_{i}$ for the $i$-th
cyclic factor, we can write

$\displaystyle w$
$\displaystyle=\prod_{i=1}^{r}(j_{i},wj_{i},\cdots,w^{l_{i}-1}j_{i})$

We can make this notation unique by choosing $j_{i}$ such that for all
positive integer $m$,

$\displaystyle j_{i}\geq w^{m}j_{i}$

and for all $i=1,2,\dots,r-1$, take

$\displaystyle j_{i}<j_{i+1}$

Such a unique decomposition is called _canonical cycle decomposition_ of $w$.
This plays an important role in Foata’s first fundamental bijection [FS78].
Note that $l=(l_{1},l_{2},\cdots,l_{r})$ is a composition of $n$. The
underlying partition $\tilde{l}$ is called the _cycle type_ of $w$ and is
denoted as $\mathrm{cyc}(w)$. We know that two permutations $u,w$ belong to
the same conjugacy class in $\mathfrak{S}_{n}$ if and only if
$\mathrm{cyc}(u)=\mathrm{cyc}(w)$.

######  Example 1.1.

If $w=947213865\in\mathfrak{S}_{9}$, then we have the canonical cycle
decomposition

$\displaystyle w$ $\displaystyle=(4,2)(8,6,3,7)(9,5,1)$

with $\mathrm{cyc}(w)=(4,3,2)\vdash 9$.

###  1.2 Representation theory of symmetric group $\mathfrak{S}_{n}$

A tabloid $[t]$ of shape $\lambda$ is an equivalence class of Young tableaux
of shape $\lambda$, where we consider two tableaux $t$ and $t^{\prime}$
equivalent if the entries in each row of $t$ agrees with the corresponding
entries in row of $t^{\prime}$. Given the set $T(\lambda)$ of all Young
tableaux of shape $\lambda$, there is a natural action of $\mathfrak{S}_{n}$
on $T(\lambda)$ by just permuting the labels of tableaux. This induces an
action on tabloids. Given a Young tableau $t$, the polytabloid $e_{t}$
associated to $t$ is defined as the linear combination

$\displaystyle e_{t}$ $\displaystyle:=\sum_{\pi\in
C_{t}}\mathrm{sign}(\pi)\pi[t]$

where $C_{t}$ is the column group associated to $t$, i.e. the subgroup of
$\mathfrak{S}_{n}$ consisting of permutations that only permute elements
within each column of $t$. For each partition $\lambda\vdash n$,
$\mathbb{C}$-linear combination of polytabloids of shape $\lambda$ gives an
irreducible representation of $\mathfrak{S}_{n}$ over $\mathbb{C}$. This is
referred as Specht module $S^{\lambda}$ corresponding to $\lambda\vdash n$ in
the literature [Ste12]. Let $\mathrm{Cl}(\mathfrak{S}_{n})$ denote the vector
space of class functions on the group $\mathfrak{S}_{n}$ over $\mathbb{C}$.
The characters of Specht modules, $(\chi^{\lambda})_{\lambda\vdash n}$, gives
a basis for $\mathrm{Cl}(\mathfrak{S}_{n})$. There is a scalar product
$\left<\cdot,\cdot\right>_{\mathfrak{S}_{n}}$ on
$\mathrm{Cl}(\mathfrak{S}_{n})$ defined as

$\displaystyle\left<\chi^{\lambda},\chi^{\mu}\right>$
$\displaystyle=\frac{1}{n!}\sum_{\sigma\in\mathfrak{S}_{n}}\chi^{\lambda}(\sigma)\chi^{\mu}(\sigma)$

and extended linearly. The decomposition of the permutation character in terms
of the irreducible character basis $\\{\chi^{\mu}\\}$ is given by Young’s
rule, which gives:

$\zeta^{\lambda}=\sum_{\mu\unlhd\lambda}K_{\mu\lambda}\chi^{\mu}$ (1)

where $K_{\mu\lambda}$, are the Kostka numbers, and the sum is over all
partitions $\mu$ which are less than or equal to $\lambda$ in the _dominance
order_.

###  1.3 Brick tilings

A _brick_ of length $j$ is a labelled horizontal array of $j$ unit cells. We
will view it as a $1\times j$ rectangle. To each $j$-cycle
$a=(a_{1}a_{2}\cdots a_{j})$ in the canonical cycle decomposition of $w$, we
can associate a brick of length $j$ with $i$th square labelled $a_{i}$. Given
$w\in\mathfrak{S}_{n}$ where $w$ has cycle type
$\lambda=(\lambda_{1},\cdots,\lambda_{r})\vdash n$, we denote by $B_{w}$ the
set of associated bricks of length $\lambda_{1},\cdots,\lambda_{r}$
corresponding to each cyclic factor in the canonical cycle decomposition of
$w$. Note that the $1$-cycles correspond to $1\times 1$ square bricks. A
_tiling_ of a diagram $\lambda\vdash n$ by a set of bricks $B$ is a covering
of the diagram $\lambda$ with bricks from $B$ such that no brick is used twice
and each cell of $\lambda$ is covered by some brick from $B$. An _ordered
brick tiling_ of $\lambda\vdash k$ (or $\lambda\vDash k$) by
$w\in\mathfrak{S}_{n}$ is a tiling of Young diagram of $\lambda$ by bricks
from $B_{w}$, where no brick is in more than one row and the order of the
bricks in a row is irrelevant. To be more precise, the ordered brick tiling of
shape $\lambda=(\lambda_{1},\cdots,\lambda_{k})$ with $w\in\mathfrak{S}_{n}$
is an ordered tuple $(S_{1},S_{2},\cdots,S_{r})$ of disjoint subsets of
$B_{w}$ such that

$\displaystyle\bigg{|}\bigcup_{U\in S_{j}}U\bigg{|}=\lambda_{j}$

for all $j=1,\cdots,r$. The set of brick tilings of $\lambda\vdash n$ by
$w\in\mathfrak{S}_{n}$ is denoted by $B_{w}(\lambda)$. So in each element
$(S_{1},S_{2},\dots,S_{r})$ of $B_{w}(\lambda)$ with $\ell(\lambda)=r$, the
set $S_{i}$ represent the set of bricks used to tile the $i$-th row of Young
diagram of $\lambda$. Notice since the order of tiles in a row does not
matter, therefore there is no ambiguity in this notation. If need be, we write
$T_{i}$ explicitly using the canonical cycle decomposition.

We can define an equivalence relation among brick tilings of shape $\lambda$
as follows: Two brick tilings $S=(S_{1},S_{2},\dots,S_{r})$ and
$T=(T_{1},T_{2},\dots,T_{r})$ of partition $\lambda\vdash_{r}n$, are
equivalent if one is a permutation of other i.e.

$\displaystyle(S_{1},\cdots,S_{r})$
$\displaystyle=(T_{\pi(1)},\cdots,T_{\pi(r)})\leavevmode\nobreak\
\leavevmode\nobreak\ \text{for some}\leavevmode\nobreak\
\pi\in\mathfrak{S}_{r}$

We refer to these equivalence classes of tilings as _unordered brick tilings_
of $\lambda$ by $w$, and we denote the set of these equivalence classes by
$\widetilde{B}_{w}(\lambda)$. We say a brick tiling is _crackless_ whenever we
have exactly one tile in each row. Otherwise, we say it is _cracked_. A
_crack_ in a brick tiling is the occurrence of two tiles in one row of a Young
diagram. If a row contains $c$ many tiles, we say it has $c-1$ cracks, and the
number of cracks in a brick tiling is sum of number of cracks in its rows. For
a $T$ in $\widetilde{B}_{w}(\lambda)$ (resp. $B_{w}(\lambda)$), we call
$\lambda$ the _shape of $T$_ and denote it by $\mathrm{sh}(T)$. Furthermore,
for any subset $A=\\{b_{1},b_{2},\dots,b_{r}\\}$ of $B_{w}$, the _shape of
$A$_, denoted as $\mathrm{sh}(A)$ is the sequence of lengths of bricks $b_{i}$
in decreasing order.

######  Example 1.2.

Consider $\lambda=(2,2,1)\vdash 5$ and let $u=(3,1)(4)(5,2)$ and
$w=(2)(3,1)(4)(5)$ in $\mathfrak{S}_{5}$. We have
$B_{u}=\left\\{\leavevmode\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}*(red!20)\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern
0.39993pt\hbox{\pagecolor{red!20}\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern
0.19997pt\hbox{\kern 0.39993pt\hbox{\pagecolor{red!20}\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$3$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern
0.19997pt\hbox{\kern 0.39993pt\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$1$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\kern 21.99976pt}\kern
21.99976pt},\leavevmode\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}*(green!20)\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern
0.39993pt\hbox{\pagecolor{green!20}\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$4$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\kern 11.19987pt}\kern
11.19987pt},\leavevmode\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}*(blue!20)\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern
0.39993pt\hbox{\pagecolor{blue!20}\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern
0.19997pt\hbox{\kern 0.39993pt\hbox{\pagecolor{blue!20}\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$5$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern
0.19997pt\hbox{\kern 0.39993pt\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$2$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\kern 21.99976pt}\kern
21.99976pt}\right\\}$ and $B_{w}=\left\\{\leavevmode\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}*(blue!20)\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern
0.39993pt\hbox{\pagecolor{blue!20}\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$2$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\kern 11.19987pt}\kern
11.19987pt},\leavevmode\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}*(red!20)\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern
0.39993pt\hbox{\pagecolor{red!20}\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern
0.19997pt\hbox{\kern 0.39993pt\hbox{\pagecolor{red!20}\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$3$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern
0.19997pt\hbox{\kern 0.39993pt\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$1$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\kern 21.99976pt}\kern
21.99976pt},\leavevmode\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}*(green!20)\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern
0.39993pt\hbox{\pagecolor{green!20}\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$4$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\kern 11.19987pt}\kern
11.19987pt},\leavevmode\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}*(yellow!50)\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern
0.39993pt\hbox{\pagecolor{yellow!50}\vbox to10.39995pt{\vss\hbox
to10.00002pt{\hss$$\hss}\vss}}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\hbox{\vtop{
\offinterlineskip\openup-0.39993pt\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower
0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox
to10.39995pt{\vss\hbox to10.00002pt{\hss$5$\hss}\vss}\kern-10.39995pt\vrule
height=10.39995pt,width=0.39993pt\kern 10.00002pt\vrule
height=10.39995pt,width=0.39993pt}\kern-0.19997pt\kern-10.39995pt\hrule
width=10.79988pt,height=0.39993pt\kern 10.00002pt\hrule
width=10.79988pt,height=0.39993pt}\cr}}\kern 11.19987pt}\kern
11.19987pt}\right\\}$. The diagram of $\lambda$ is given by  . The ordered and
unordered tilings of $\lambda$ by $u$ and $w$ are given below

and

Note that all the elements of $\widetilde{B}_{u}(\lambda)$ are crackless, but
all the elements of $\widetilde{B}_{w}(\lambda)$ are cracked with one crack
each.

###  1.4 Tiling class functions

In this section, we define class functions on $\mathfrak{S}_{n}$ that count
the number of different types of brick tilings. Let $k$ be a positive integer
less than or equal to $n$ and let $\lambda\vdash k$ (or $\lambda\vDash k$). We
define functions
$\zeta^{\lambda},\xi^{\lambda},\eta^{\lambda}:\mathfrak{S}_{n}\longrightarrow\mathbb{N}$
as follow

$\displaystyle\zeta^{\lambda}(w)$ $\displaystyle:=\leavevmode\nobreak\
\text{number of ordered brick tilings of $\lambda$ by $w$ i.e.
\leavevmode\nobreak\ }|\widetilde{B}_{w}(\lambda)|$
$\displaystyle\xi^{\lambda}(w)$ $\displaystyle:=\leavevmode\nobreak\
\text{number of unordered brick tilings of $\lambda$ by $w$
i.e.\leavevmode\nobreak\ }|{B}_{w}(\lambda)|$ $\displaystyle\eta^{\lambda}(w)$
$\displaystyle:=\leavevmode\nobreak\ \text{number of unordered crackless brick
tilings of $\lambda$ by $w$}$

These are class functions on $\mathfrak{S}_{n}$. What that means is that they
are constant on each conjugacy class of $\mathfrak{S}_{n}$. The notion of
tiling of $\lambda\vdash k$ with $w\in\mathfrak{S}_{n}$ when $k\neq n$ still
make sense. For $k>n$, all of the above class functions are identically zero,
so we keep the condition $k\leq n$.

######  Example 1.3.

Going back to example 1.2, for the respective partition $\lambda$ and
permutations $u,w$, we have

$\zeta^{\lambda}(u)=2$ | $\zeta^{\lambda}(w)=6$
---|---
$\xi^{\lambda}(u)=1$ | $\xi^{\lambda}(w)=3$
$\eta^{\lambda}(u)=1$ | $\eta^{\lambda}(w)=0$
Table 1: Combinatorial class functions for example 1.2

The interesting case is when $k=n$. This means that all of the bricks from
$B_{w}$ are utilized to cover diagram $\lambda\vdash n$. So the ordered brick
tilings correspond precisely to tabloids, and hence we have the following
result.

######  Theorem 1.4.

For $\lambda\vdash n$,

  * •

$\zeta^{\lambda}$ is the character corresponding to the permutation
representation $M^{\lambda}$ of $\mathfrak{S}_{n}$. Furthermore,

$\displaystyle\xi^{\lambda}$ $\displaystyle=\frac{1}{\lambda!}\zeta^{\lambda}$

where $\lambda!:=m_{1}!m_{2}!\cdots$ for
$\lambda=(1^{m_{1}},2^{m_{2}},\cdots)$.

  * •

$\eta^{\lambda}$ is the indicator function of cycle structure i.e.

$\displaystyle\eta^{\lambda}(w)$
$\displaystyle=\begin{cases}1&\text{if}\leavevmode\nobreak\
\leavevmode\nobreak\ \mathrm{cyc}(w)=\lambda\\\ 0&\text{otherwise}\end{cases}$

###### Proof.

Recall that for a partition $\lambda=(\lambda_{1},\cdots,\lambda_{\ell})\vdash
n$ and $w\in\mathfrak{S}_{n}$ with
$\mathrm{cyc}(w)=\mu=(\mu_{1},\cdots,\mu_{r})$, the character of
$\mathfrak{S}_{n}$ corresponding to $M^{\lambda}$ is the coefficient of
$x_{1}^{\lambda_{1}}x_{2}^{\lambda_{2}}\cdots x_{\ell}^{\lambda_{\ell}}$ in
the product

$\displaystyle\prod_{i=1}^{r}(x_{1}^{\mu_{i}}+\cdots+x_{\ell}^{\mu_{i}})$

which precisely counts the ordered brick tilings of $w$ by $\lambda$.
Furthermore, to each unordered brick tiling of $\lambda$ we get
$\lambda!=m_{1}!m_{2}!\cdots$ ordered brick tilings by permuting the tilings
in the parts of same size, and vice versa. For the second part, a crackless
tiling of $\lambda$ is only possible if each part of $\mathrm{cyc}(w)$ fits
perfectly in a unique part of $\lambda$. This is just another way of saying
that $\mathrm{cyc}(w)=\lambda$.

∎

######  Lemma 1.5.

Let $k\leq n$, then

  * •

for any $\mu\vDash k$ the following holds as identities of class functions on
$\mathfrak{S}_{n}$.

$\displaystyle\zeta^{\mu}$
$\displaystyle=\zeta^{\tilde{\mu}}\leavevmode\nobreak\ \leavevmode\nobreak\
,\leavevmode\nobreak\ \leavevmode\nobreak\
\xi^{\mu}=\xi^{\tilde{\mu}}\leavevmode\nobreak\ \leavevmode\nobreak\
,\leavevmode\nobreak\ \leavevmode\nobreak\ \eta^{\mu}=\eta^{\tilde{\mu}}$

  * •

for any $\lambda\vdash n$ then the following holds as an identity of class
functions on $\mathfrak{S}_{n}$.

$\displaystyle\zeta^{\lambda}$ $\displaystyle=\zeta^{\left<\lambda\right>}$

and if $\lambda_{1}>\lambda_{2}$, then
$\xi^{\lambda}=\xi^{\left<\lambda\right>}$ and
$\eta^{\lambda}=\eta^{\left<\lambda\right>}$.

###### Proof.

The first statement is just a consequence of the fact that the brick tilings
of any type does not depend in the relative order of parts of $\lambda$. The
second says that if the weight of $\lambda$ and the weight of
$\mathrm{cyc}(w)$ are equal, then to determine a tiling of $\lambda$ by $w$,
we just need to determine a tiling of $\left<\lambda\right>$ by $w$. Because
whatever tiles are not being used will have to fit in $\lambda_{1}$, and there
is only one way of doing that, as the order of tiles in rows of $\lambda$ does
not matter. ∎

######  Example 1.6.

Let $\lambda=(2,2,1)\vdash 5$ and $u=(3,1)(4)(5,2)$ and $w=(2)(3,1)(4)(5)$,
recall

$\displaystyle\zeta^{\lambda}(u)$
$\displaystyle=|\widetilde{B}_{u}(\lambda)|=2$
$\displaystyle\zeta^{\lambda}(w)$
$\displaystyle=|\widetilde{B}_{w}(\lambda)|=6$

In this case, $\left<\lambda\right>=(2,1)\vdash 3$ diagram of $\lambda$ is
given by  , we have

which is in accordance with table 1. For $T\subseteq B_{w}$ be a set of bricks
coming from $w\in\mathfrak{S}_{n}$ and we denote by $\xi^{\lambda}_{T}$ the
number of tilings of $\lambda\vdash n$ with brick set given by $T$. Then
counting _brickwise_ , we have

$\xi^{\lambda}=\sum_{T\subseteq B_{w}}\xi^{\lambda}_{T}$ (2)

and

$\eta^{\lambda}=\sum_{\begin{subarray}{c}T\subseteq B_{w}\\\
\mathrm{sh}(T)=\lambda\end{subarray}}1$ (3)

Furthermore, since for the row shape $(k)\vdash k$, we can count the tilings
of all shapes, which gives

$\zeta^{(k)}=\xi^{(k)}=\sum_{\mu\vdash k}\eta^{\mu}$ (4)

These are some identities that will come handy in later to prove our main
result.

###  1.5 Doubilet’s inversion formula

Recall the Young’s rule which states that

$\displaystyle M^{\lambda}$
$\displaystyle=\bigoplus_{\mu\unlhd\lambda}K_{\mu\lambda}S^{\lambda}$

where $K_{\mu\lambda}$ are the Kostka numbers. If we denote by
$\chi^{\lambda}$ the irreducible character of $\mathfrak{S}_{n}$ corresponding
to the Specht module $S^{\lambda}$, then this implies

$\displaystyle\zeta^{\lambda}$
$\displaystyle=\sum_{\mu\unlhd\lambda}K_{\mu\lambda}\chi^{\mu}$

We also know that for partitions $\lambda,\mu\vdash n$, the coefficients
$K_{\mu\lambda}\neq 0$ if and only if $\mu\unlhd\lambda$. Furthermore,
$K_{\lambda\lambda}=1$. This implies that the Kostka matrix
$K=(K_{\mu\lambda})$ is invertible. Therefore, we can write the irreducible
character $\chi^{\lambda}$ as a linear combination of $\zeta^{\lambda}$’s.
Such an inversion formula was given by Doubilet in [Dou73], which states

$\displaystyle\chi^{\lambda}$
$\displaystyle=\sum_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{n}\\\
\widetilde{\sigma\lambda}\vdash
n\end{subarray}}\mathrm{sign}(\sigma)\zeta^{\widetilde{\sigma\lambda}}$

where $\sigma\lambda$ is the sequence defined as

$\displaystyle\sigma\lambda=(\lambda_{1}+\sigma(1)-1,\lambda_{2}+\sigma(2)-2,\cdots,\lambda_{n}+\sigma(n)-n)$

$(\sigma\lambda)_{i}=\lambda_{i}+\sigma(i)-i$ for all $i=1,2,\dots,n$ and
$\widetilde{\sigma\lambda}$ is the rearrangement of this sequence in a weakly
decreasing order. Since $\lambda_{i}=0$ for $\ell(\lambda)<i\leq n$, this
implies that for $\widetilde{\sigma\lambda}$ to be a partition, we should have

$\displaystyle\sigma(i)-i$ $\displaystyle\geq 0$

equivalently $\sigma(i)\geq i$ for all $\ell(\lambda)<i\leq n$. This implies
$\sigma(n)=n$ and since $\sigma$ is a bijection and hence injective
$\sigma(n-1)=n-1$. Inductively, we have $\sigma(i)=i$ for $\ell(\mu)<i<n$. Let
$\overline{\mathfrak{S}}_{\ell}(\lambda)$ be the subgroup of permutations that
pointwise fix all the elements from $\ell(\lambda)+1$ to $n$. Then, the above
observation implies that the sum on the right of the inversion formula can be
taken over $\sigma\in\overline{\mathfrak{S}}_{\ell(\lambda)}$ such that
$\widetilde{\sigma\lambda}\vdash n$. Hence we can restate the inversion
formula as:

######  Lemma 1.7.

(Doubilet’s inversion formula) Let $\lambda\vdash n$, then keeping the
notation of this section, we have

$\displaystyle\chi^{\lambda}$
$\displaystyle=\sum_{\begin{subarray}{c}\sigma\in\overline{\mathfrak{S}}_{\ell(\lambda)}\\\
\widetilde{\sigma\lambda}\vdash
n\end{subarray}}\mathrm{sign}(\sigma)\zeta^{\widetilde{\sigma\lambda}}$

For our purposes later, we will be able to reduce this sum to a smaller
indexing set using the condition that $\sigma\lambda$ needs to be a
composition of $n$. This enforces that none of the parts of $\sigma\lambda$
should be less than $1$. For the time being, we show a simple example.

######  Example 1.8.

For a positive integer $n\geq 1$, take the partition $\lambda=(n-1,1)\vdash
n$, then

$\displaystyle\chi^{(n-1,n)}$ $\displaystyle=\zeta^{(n-1,1)}-\zeta^{(n)}$

which reminiscent of the fact that the $M^{(n-1,1)}=S^{(n-1,1)}\oplus
M^{(n)}$, where we know that $S^{n-1,n}$ is the regular representation and
$M^{(n)}$ is the trivial representation of $\mathfrak{S}_{n}$.

###  1.6 Face numbers of permutohedron

The standard permutohedron is an example of a convex polytope associated to
permutations. To each permutation $w\in\mathfrak{S}_{n}$, we associate a point
in $\mathbb{R}^{n}$

$\displaystyle p_{w}$ $\displaystyle=(w(1),w(2),\cdots,w(n))\in\mathbb{R}^{n}$

The _standard permutohedron_ $\Pi_{n}$ is defined to be the convex hull of
these points, i.e.

$\displaystyle\Pi_{n}$
$\displaystyle=\mathsf{conv}\\{p_{w}:w\in\mathfrak{S}_{n}\\}$

Note that for each $p_{w}$, the sum of all the coordinates equals
$1+2+\cdots+n$, i.e.

$\displaystyle\sum_{i=1}^{n}p_{w,i}=1+2+\cdots+n=\binom{n+1}{2}$

This means that $\Pi_{n}$ lies in a hyperplane in $\mathbb{R}^{n}$ and
consequently $\dim(\Pi_{n})\leq n-1$. Furthermore, for each $p_{w}$, sum of
any $k$ coordinates is atleast $1+2+\dots+k$, i.e. for any $I\subset[n]$

$\displaystyle\sum_{i\in I}p_{w,i}\geq 1+2+\cdots+|I|=\binom{|I|+1}{2}$

It is known classically that these inequalities are enough to describe
$\Pi_{n}$. We need the following known result (see for example [Zie95]) from
polytope theory.

######  Theorem 1.9.

The standard permutohedron $\Pi_{n}$ is a simple $(n-1)$-dimensional convex
polytope given by

$\displaystyle\Pi_{n}$
$\displaystyle=\left\\{\mathbf{x}\in\mathbb{R}^{n}:\sum_{i=1}^{n}x_{i}=n\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{i\in
I}x_{i}\geq\binom{|I|+1}{2},\leavevmode\nobreak\ \leavevmode\nobreak\
\text{for all}\leavevmode\nobreak\ \leavevmode\nobreak\ I\subset[n]\right\\}$

with face numbers given by

$\displaystyle f_{k}(\Pi_{n})$ $\displaystyle=(n-k)!\begin{Bmatrix}n\\\
n-k\end{Bmatrix}$

for $k=0,\cdots,n-1$, where $\begin{Bmatrix}n\\\ k\end{Bmatrix}$ is the
Stirling number of the second kind (that counts the partitions of $[n]$ into
$k$ blocks).

Since $\Pi_{n}$ is simple convex polytope, its dual $\Pi_{n}^{*}$ is a
simplicial convex polytope. We can consider the simplicial complex
$\Delta_{n-1}:=\partial\Pi_{n}^{*}$ (the boundary complex of $\Pi_{n}^{*}$).
Its face numbers are given by

$\displaystyle f_{k-1}(\Delta_{n-1})$ $\displaystyle=(k+1)!\begin{Bmatrix}n\\\
k+1\end{Bmatrix}$

for $k=0,1,\cdots,n-1$. This implies that the reduced Euler characteristic of
$\Delta_{n-1}$ is given by

$\displaystyle\sum_{k=0}^{n-1}(-1)^{k-1}f_{k-1}(\Delta_{n-1})$
$\displaystyle=\sum_{k=0}^{n-1}(-1)^{k-1}(k+1)!\begin{Bmatrix}n\\\
k+1\end{Bmatrix}$ $\displaystyle=\sum_{k=1}^{n}(-1)^{k-1}k!\begin{Bmatrix}n\\\
k\end{Bmatrix}$

Since $\Delta_{n-1}$ is homeomorphic to the $(n-2)$-dimensional sphere
$S^{n-2}$, its reduced Euler characteristic equals to $(-1)^{n-2}$. This can
be rewritten as

$\sum_{k=1}^{n}(-1)^{k}k!\begin{Bmatrix}n\\\ k\end{Bmatrix}=(-1)^{n}$ (5)

We will use this identity in later section.

##  2 Combinatorics of tiling class functions

Characters of the symmetric group $\mathfrak{S}_{n}$ are examples of class
functions. What that means is that they are constant over conjugacy classes in
$\mathfrak{S}_{n}$. This implies that they only depend on cycle structure of
evaluating permutation. Simple examples of class functions are $c_{i}$’s which
count the number of cycles of length $i$ in a permutation. It is a result of
Frobenius [Fro04] that the every irreducible character of $\mathfrak{S}_{n}$
is a polynomial function of $c_{i}$’s, called _character polynomials_. They
were also studied later by Murnaghan [Mur51] and Specht [Spe60]. Macdonald
mentions them in [Mac79] and attribute them to Frobenius. Garsia and Goupil
[GG09] gave an umbral construction of these polynomials. Kerber also studied
them in his book [Ker99] on group actions. Recently, they have reoccurred in
the context of representation stability [CEF15]. We study our tiling class
functions as polynomials in $c_{i}$’s. The main result in this section is
identity 2.5, which equates two alternating sums of class functions. We
provide two proofs of it: one using homology on poset of brick tilings, and
the other using reduced Euler characteristic of boundary complex of dual
polytope to permutohedron.

###  2.1 Character polynomials

The class functions $\\{c_{i}\\}_{i\in\mathbb{N}}$ are defined as

$\displaystyle c_{i}:\mathfrak{S}_{n}$
$\displaystyle\longrightarrow\mathbb{N}$ $\displaystyle w$
$\displaystyle\longmapsto\leavevmode\nobreak\ \text{number of cycles of $w$ of
length $i$}$

Let $\mathbb{Q}[c_{1},c_{2},\cdots]$ be the ring of polynomials in $c_{i}$’s
with rational coefficient. We call a polynomial
$q(c_{1},c_{2},\cdots)\in\mathbb{Q}[c_{1},c_{2},\cdots]$ a _class polynomial_.
Frobenius [Fro04] showed the following

######  Theorem 2.1.

Let $\lambda=(\lambda_{1},\cdots,\lambda_{\ell})\vdash n$ and let
$w\in\mathfrak{S}_{n}$ be a permutation of cycle type
$\mathrm{cyc}(w)=\mu=(\mu_{1},\cdots,\mu_{r})\vdash n$, then
$\chi^{\lambda}(w)$ equals the coefficient of
$x_{1}^{\lambda_{1}+\ell-1}x_{2}^{\lambda+\ell-2}\cdots
x_{\ell}^{\lambda_{\ell}}$ in the expansion of

$\displaystyle\prod_{1\leq
i<j\leq\ell}(x_{i}-x_{j})\prod_{i=1}^{r}(x_{1}^{\mu_{i}}+x_{2}^{\mu_{i}}+\cdots+x_{\ell}^{\mu_{i}})$

The character polynomial $q_{\lambda}(c_{1},c_{2},\cdots)$ is defined as the
_unique_ polynomial in $\mathbb{Q}[c_{1},c_{2},\cdots]$ such that for all
partitions $\lambda\vdash k$ and $n\geq\lambda_{1}+k$, we have

$\chi^{\lambda[n]}(w)=q_{\lambda}(c_{1}(w),c_{2}(w),\cdots)$ (6)

for all $w\in\mathfrak{S}_{n}$. Note that the character polynomial
$q_{\lambda}$ as a polynomial does not depend on $n$, and hence gives a
uniform description of irreducible characters corresponding to augmented
partition $\lambda[n]$ for all symmetric groups at the same time (with
$n\geq\lambda_{1}+k$). This is quite remarkable.

######  Example 2.2.

The character polynomial for empty partition is the constant function $1$, as
it corresponds to the trivial representation. The character polynomial
for$\lambda=1$ is given by

$\displaystyle q_{(1)}$ $\displaystyle=c_{1}-1$

as $\lambda[n]=(n-1,1)$ corresponds to the regular representation.

For $\lambda\vdash k$, there is a special family of class polynomials called
_binomial class polynomials_ $\binom{c}{\lambda}$ defined as

$\displaystyle\binom{c}{\lambda}$
$\displaystyle:=\prod_{i=1}^{n}\binom{c_{i}}{m_{i}(\lambda)}$

where $m_{i}(\lambda)$ is the multiplicity of $i$ in $\lambda$. As an example,
for $\lambda=(4,2,2,1,1)$, we have

$\displaystyle\binom{c}{\lambda}$
$\displaystyle:=\binom{c_{4}}{1}\binom{c_{2}}{2}\binom{c_{1}}{2}$

Notice that for $\lambda\vdash k$ and $w\in\mathfrak{S}_{n}$ with $n\geq k$,
having a unordered crackless tiling of $\lambda$ by $\pi$ is equivalent to
choosing $m_{i}(\lambda)$ bricks from all $c_{i}(w)$ bricks of $w$ of length
$i$, for each $i=1,\cdots,n$. This implies

$\eta^{\lambda}=\binom{c}{\lambda}$ (7)

as class functions on $\mathfrak{S}_{n}$. This implies the generating function
equality

$\sum_{k=0}^{\infty}\left(\sum_{\mu\vdash
k}\eta^{\mu}\right)t^{k}=\prod_{i=1}^{\infty}(1+t^{i})^{c_{i}}$ (8)

in the ring of formal power series $\mathbb{Q}[c_{1},c_{2}\cdots][[t]]$.

###  2.2 Characters corresponding to two row partitions

We consider the case of $\lambda=(k)$ to generalize example 1.8. In this case,
we are looking at the augmented partition $\lambda[n]=(n-k,k)\vdash n$ for
$n\geq 2k$. The 1.7 implies as class functions on $\mathfrak{S}_{n}$

$\displaystyle\chi^{\lambda[n]}$
$\displaystyle=\sum_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{2}\end{subarray}}\mathrm{sign}(\sigma)\zeta^{\widetilde{\sigma\lambda[n]}}$
$\displaystyle=\zeta^{(n-k,k)}-\zeta^{(n-k+1,k-1)}$
$\displaystyle=\zeta^{(k)}-\zeta^{(k-1)}$ $\displaystyle=\sum_{\mu\vdash
k}\eta^{\mu}-\sum_{\mu\vdash k-1}\eta^{\mu}$

Therefore from equation 8 we have the following identity in
$\mathbb{Q}[c_{1},c_{2},\cdots][[t]]$

$\sum_{k=0}^{\infty}q_{(k)}t^{k}=(1-t)\prod_{i=1}^{\infty}(1-t^{i})^{c_{i}}$
(9)

We should be careful about stating the above equality. Becuase what we really
mean is that the coefficients of $t^{n}$ are equal as polynomial functions of
$c_{i}$’s.

######  Example 2.3.

We find first few character polynomials from the above equality. A table of
them can also be found[Ker99]

$\displaystyle q_{()}$ $\displaystyle=1$ $\displaystyle q_{(1)}$
$\displaystyle=\binom{c_{1}}{1}-1$ $\displaystyle q_{(2)}$
$\displaystyle=\binom{c_{2}}{1}+\binom{c_{1}}{2}-\binom{c_{1}}{1}$
$\displaystyle q_{(3)}$
$\displaystyle=\binom{c_{3}}{1}+\binom{c_{1}}{1}\binom{c_{2}}{1}+\binom{c_{1}}{3}-\binom{c_{2}}{1}-\binom{c_{1}}{2}$

###  2.3 Characters corresponding to hook partitions

Let us consider $\lambda=(1^{k})\vdash k$. The augmented partition in this
case is the hook partition $\lambda[n]=(n-k,1^{k})\vdash n$, for $n\geq 2k$.
Recall that the Doubilet inversion formula 1.7 says

$\chi^{\lambda[n]}=\sum_{\sigma\in\overline{\mathfrak{S}}_{k+1}}\mathrm{sign}(\sigma)\zeta^{\widetilde{\sigma\lambda[n]}}$
(10)

where $\overline{\mathfrak{S}}_{k+1}$ denote the subgroup consisting of
permutations in $\mathfrak{S}_{n}$ that fixes all the elements from $k+2$ to
$n$. The sum can further be restricted to those
$\sigma\in\overline{\mathfrak{S}}_{k}$ for which
$\widetilde{\sigma\lambda[n]}$ is a partition of $n$, i.e.

$\displaystyle(\widetilde{\sigma\lambda[n]})_{i}$
$\displaystyle=\lambda_{i}+\sigma(i)-i\geq 0$

For $i=2,\dots k+1$, $\lambda_{i}=1$, therefore we are looking for
$\sigma\in\overline{\mathfrak{S}}_{k+1}$ such that $\sigma(i)\geq i-1$. Note
that there is no condition on $\sigma(1)$ as $n\geq 2k$. So we can say that

$\displaystyle\sigma(i)\geq i-1$

for all $i=1,\dots,k+1$. This implies such a permutation is uniquely
determined by the set

$\displaystyle S(\sigma)=\\{(i,\sigma(i)):\sigma(i)\geq i\\}$

Fixing $j=k+1-\sigma(1)$, we see that there are $2^{j-1}$ such permutations
and each such permutation gives a composition $\mu\vDash j$. On the other
hand, given a composition $\mu\vDash j$, we can construct $\sigma$ by taking

$S(\sigma)=\\{(1,k+1-j),(k+1-j+1,k+1-j+\mu_{1}),\\\
(k+1-j+\mu_{1}+1,k+1-j+\mu_{1}+\mu_{2}),\cdots\\}$ (11)

And for such a $\sigma$, we have

$\displaystyle\sigma\lambda[n]$
$\displaystyle=(n-\sigma(1),\mu_{1},\mu_{2},\cdots,\mu_{\ell})$
$\displaystyle\left<\sigma\lambda[n]\right>$
$\displaystyle=(\mu_{1},\cdots,\mu_{\ell})\vDash j$

Combining these we can prove the following theorem:

######  Theorem 2.4.

For $\lambda=(1^{k})\vdash k$ and $n\geq 2k$, we have the following equality
of class functions

$\displaystyle\chi^{\lambda[n]}$
$\displaystyle=\sum_{j=0}^{k}(-1)^{j+1}\left(\sum_{\mu\vDash
j}(-1)^{\ell(\mu)}\zeta^{\mu}\right)$

###### Proof.

Due to the observations above, we can simplify equation 10 as follows: Fix
$\sigma(1)=k+1-j$, now each permutation gives a unique composition $\mu$ of
$j$, so we sum over all compositions of $j$. And we do this over all possible
images $\sigma(1)$, which can be any integer from 1 to $k+1$. This translates
to $j$ varying from $0$ to $k$.

$\displaystyle\chi^{\lambda[n]}$
$\displaystyle=\sum_{\sigma\in\overline{\mathfrak{S}_{k+1}}}\mathrm{sign}(\sigma)\zeta^{\widetilde{\sigma\lambda}}$
$\displaystyle=\sum_{\sigma\in\overline{\mathfrak{S}_{k+1}}}\mathrm{sign}(\sigma)\zeta^{\left<\widetilde{\sigma\lambda}\right>}$
$\displaystyle=\sum_{j=0}^{k}(-1)^{k+1-j}\left(\sum_{\mu\vDash
j}(-1)^{\sum\mu+1}\zeta^{\mu}\right)$
$\displaystyle=\sum_{j=0}^{k}(-1)^{k+1-j}\left(\sum_{\mu\vDash
j}(-1)^{\ell(\mu)+j}\zeta^{\mu}\right)$
$\displaystyle=(-1)^{k+1}\sum_{j=0}^{k}\left(\sum_{\mu\vDash
j}(-1)^{\ell(\mu)}\zeta^{\mu}\right)$

In above, we appropriately kept track of the sign as the cycle type of
$\sigma$ with $\sigma(1)=k+1-j$ that give rise to composition $\mu$ is given
by the weakly decreasing rearrangement of
$(k+1-j,\mu_{1}+1,\cdots,\mu_{\ell}+1)$. This gives

$\displaystyle\mathrm{sign}(\sigma)$
$\displaystyle=\bigg{(}\sum_{i=1}^{\ell(\mu)}(\mu_{i}+1)\bigg{)}+k+1-j$
$\displaystyle=\ell(\mu)+k+1$

This explains the simplification in the sum above. ∎

Now we move to an interesting observation that simplifies further the
calculation of $\chi^{\lambda[n]}$ for $\lambda=(1^{k})\vdash k$ where $n\geq
2k$. This result should be thought of as the main result of this paper.

######  Theorem 2.5.

For a positive integer $j\leq n$, we have the following equality of class
functions

$\displaystyle\sum_{\mu\vDash j}(-1)^{\ell(\mu)}\zeta^{\mu}$
$\displaystyle=\sum_{\mu\vdash j}(-1)^{\ell(\mu)}\eta^{\mu}$

on $\mathfrak{S}_{n}$

The left-hand side is an alternating sum over compositions of $j$, while the
right-hand side is an alternating sum over partitions of $j$. It is worth
noticing that not only the sum on the right has fewer terms but even each term
is _smaller_. In the sections to follow, we provide two proofs of this result.

###  2.4 The Tiling poset

Fix a positive integer $j\leq n$ and $w\in\mathfrak{S}_{n}$, then we can
consider the set $\mathrm{Til}(w;j)$ of all ordered brick tilings of all
compositions of $k$ by $w$, that is

$\displaystyle\mathrm{Til}(w;j)$
$\displaystyle:=\bigcup\left\\{\widetilde{B}_{w}(\lambda):\lambda\vDash
j\right\\}$

We equip this set with a partial order that is induced by the following
covering relations: For two ordered brick tilings
$A^{\prime}=(A^{\prime}_{1},\dots,A^{\prime}_{k+1})$ and
$A=(A_{1},\dots,A_{k})$ in $\mathrm{Til}(w;j)$, we say $A$ covers
$A^{\prime}$, and write $A^{\prime}\lessdot A$ if both of the following
conditions are satisfied:

  * •

$\mathrm{sh}(A^{\prime})\lessdot\mathrm{sh}(A)$ in $\mathsf{Comp}(k)$.

  * •

There exists a unique $t\in\\{1,\cdots,k\\}$ such that for all $i=1,\dots,k$

$\displaystyle A_{i}$
$\displaystyle=\begin{cases}A^{\prime}_{i}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{for}\leavevmode\nobreak\
i<t\\\ A^{\prime}_{i}\cup A^{\prime}_{i+1}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{for}\leavevmode\nobreak\
i=t\\\ A^{\prime}_{i+1}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ &\text{for}\leavevmode\nobreak\ i>t\end{cases}$

######  Example 2.6.

For $w=(31)(4)(5,2)$, and $j=5$, we show the Hasse diagram of the poset
$\mathrm{Til}(w;j)$ in figure 2.

$5$ $2$ $3$ $1$ $4$ $3$ $1$ $5$ $2$ $4$ $3$ $1$ $4$ $5$ $2$ $5$ $2$ $4$ $3$
$1$ $4$ $3$ $1$ $5$ $2$ $4$ $5$ $2$ $3$ $1$ $3$ $4$ $5$ $2$ $3$ $1$ $5$ $4$
$5$ $4$ $3$ $1$ $5$ $2$ $3$ $4$ $4$ $3$ $2$ $3$ $2$ $4$ $3$ $4$ Figure 2:
Poset $\mathrm{Til}(w;j)$ for $w=(3,1)(4)(5,2)$ and $j=4$

Notice that in general $\mathrm{Til}(w;j)$ can be thought of as disjoint union
of smaller posets, that is,

$\mathrm{Til}(w;j)=\bigsqcup_{\begin{subarray}{c}T\subseteq
B_{w}\end{subarray}}\mathrm{Til}(T;j)$ (12)

where $\mathrm{Til}(T;j)$ is the set of all ordered brick tilings of all
compositions of $j$, whose brick set is $T$. From the poset
$\mathrm{Til}(w;j)$, we define following chain complex over field with 2
elements $\mathbb{F}_{2}$

$\displaystyle 0\longrightarrow C_{j-1}\longrightarrow
C_{j-2}\longrightarrow\cdots\longrightarrow C_{1}\longrightarrow
C_{0}\longrightarrow 0$

where the chains are defined as

$\displaystyle
C_{i}=\mathbb{F}_{2}\left\\{e_{A}:A\in\mathrm{Til}(w;j)\leavevmode\nobreak\
\text{such that}\leavevmode\nobreak\ \mathrm{sh}(A)\vDash_{j-i}j\right\\}$

where $e_{T}$ are just formal symbols. And the differentials is induced by the
down map of the poset, i.e. for $i=1,\dots,j-1$

$\displaystyle\partial_{i}:C_{i}$ $\displaystyle\longrightarrow C_{i-1}$
$\displaystyle e_{A}$ $\displaystyle\longmapsto\sum_{A^{\prime}\lessdot
T}e_{A^{\prime}}$

To show we indeed have a chain complex we still need to show that
$\partial^{2}=0$. Without loss of generality, assume that there exist some
$A^{\prime\prime}<A$ such that $[A^{\prime\prime},A]$ is an interval of length
2 . Then let

$\displaystyle\partial_{i-1}\circ\partial_{i}(e_{A})=\sum\alpha_{AA^{\prime\prime}}e_{A^{\prime\prime}}$

where the sum is over all $A^{\prime\prime}$ for which there exists
$A^{\prime}$ such that $A^{\prime\prime}\lessdot A^{\prime}\lessdot A$ and the
coefficients are given by

$\displaystyle\alpha_{AA^{\prime\prime}}$
$\displaystyle=|\\{A^{\prime}:\text{such that}\leavevmode\nobreak\
A^{\prime\prime}\lessdot A^{\prime}\lessdot A\\}|\pmod{2}$

Let $\beta_{AA^{\prime\prime}}=|\\{A^{\prime}:\text{such
that}\leavevmode\nobreak\ A^{\prime\prime}\lessdot A^{\prime}\lessdot A\\}|$.
We claim that for every pair $(A^{\prime\prime},A)$ such that there exists
$A^{\prime}$ with $A^{\prime\prime}\lessdot A^{\prime}\lessdot A$, we have
$\beta_{AA^{\prime\prime}}=2$. Let
$A^{\prime\prime}=(A^{\prime\prime}_{1},A^{\prime\prime}_{2},\dots,A^{\prime\prime}_{k+2})$
and $A=(A_{1},A_{2},\dots,A_{k})$, then we can have one of the following
situations:

  * •

We have two indices $a,b$, with $a<b$, such that

$\displaystyle A_{i}$
$\displaystyle=\begin{cases}A^{\prime\prime}_{i}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{if}\leavevmode\nobreak\
i<a\\\ A^{\prime\prime}_{i}\cup A^{\prime\prime}_{i+1}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{if}\leavevmode\nobreak\
i=a\\\ A^{\prime\prime}_{i+1}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ &\text{if}\leavevmode\nobreak\ a\leq i\leq b\\\
A^{\prime\prime}_{i+1}\cup A^{\prime\prime}_{i+2}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{if}\leavevmode\nobreak\
i=b\\\ A^{\prime\prime}_{i+2}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ &\text{if}\leavevmode\nobreak\ b<i\leq k\end{cases}$

In this case, there are two possible $A^{\prime}$:
$(A^{\prime\prime}_{1},\dots,A^{\prime\prime}_{a}\cup
A^{\prime\prime}_{a+1},\dots,A^{\prime\prime}_{k+2})$ or
$(A^{\prime\prime}_{1},\dots,A^{\prime\prime}_{b}\cup
A^{\prime\prime}_{b+1},\dots,A^{\prime\prime}_{k+2})$. Then,
$\beta_{AA^{\prime\prime}}=2$.

  * •

We have an index $a$ such that

$\displaystyle A_{i}$
$\displaystyle=\begin{cases}A^{\prime\prime}_{i}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{if}\leavevmode\nobreak\
i<a\\\ A^{\prime\prime}_{i}\cup A^{\prime\prime}_{i+1}\cup
A^{\prime\prime}_{i+2}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ &\text{if}\leavevmode\nobreak\ i=a\\\
A^{\prime\prime}_{i+2}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ &\text{if}\leavevmode\nobreak\ a<i\leq k\end{cases}$

In this case, $A^{\prime}=(A^{\prime\prime}_{1},\dots,A^{\prime\prime}_{a}\cup
A^{\prime\prime}_{a+1},\dots,A^{\prime\prime}_{k+2})$ or
$A^{\prime}=(A^{\prime\prime}_{1},\dots,A^{\prime\prime}_{a+1}\cup
A^{\prime\prime}_{a+2},\dots,A^{\prime\prime}_{k+2})$, and we also have that
$\beta_{AA^{\prime\prime}}=2$.

Since we are dealing with coefficients $\mathrm{mod}\leavevmode\nobreak\ 2$,
in both cases $\alpha_{AA^{\prime\prime}}=0$. This proves that
$\partial^{2}=0$, and so we indeed have a chain complex. To illustrate the
idea, we show an example

######  Example 2.7.

For $w=(3,1)(5,2)(4)$, we get the following for $k=5$

An element $J\in C_{i}$ for some positive integer $i<j$, can be written as

$\displaystyle J$ $\displaystyle=\sum_{T\in L}e_{T}$

The set $L$ is called the _support_ of $J$, and we denote it by
$\mathrm{supp}(J)$. For a subspace $V$ of the chain complex, let
$\overline{V}$ be the subspace of $V$ generated by elements in $V$ whose
support is crackless brick tilings, and let $\widetilde{V}$ be the subspace of
$V$ generated by elements in $V$ whose support is cracked brick tilings. An
interesting consequence of equation 12 is the following decomposition:

$\displaystyle\ker\partial_{i}$
$\displaystyle=\widetilde{\ker\partial_{i}}\oplus\overline{\ker\partial_{i}}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\mathrm{im}\partial_{i+1}=\widetilde{\mathrm{im}\partial_{i+1}}\oplus\overline{\mathrm{im}\partial_{i+1}}$

One inclusion is obvious. The other inclusion is the consequence of the fact
that a cracked brick tiling and a crackless brick tiling with $j-i$ parts
cannot have the same set of bricks for all $i=1,\cdots,j-1$. Therefore the
decomposition follows from the partition 12. Hence, we can write the homology
of the above chain complex as

$\displaystyle H_{i}(C)$
$\displaystyle=\frac{\text{ker}\partial_{i}}{\text{im}\partial_{i+1}}$
$\displaystyle=\frac{\widetilde{\text{ker}\partial_{i}}\oplus\overline{\text{ker}\partial_{i}}}{\widetilde{\text{im}\partial_{i+1}}\oplus\overline{\text{im}\partial_{i+1}}}$

Notice in proving $\partial^{2}=0$, we concluded something more than that. We
proved that each subinterval of rank 2 in $\mathrm{Til}(w;j)$ is isomorphic to
the boolean interval of length $B(2)$ as posets, which implies
$\widetilde{\text{im}\partial_{i+1}}=\widetilde{\text{ker}\partial_{i}}$. This
simplifies the above expression to

$\displaystyle H_{i}(C)$
$\displaystyle=\frac{\overline{\text{ker}\partial_{i}}}{\overline{\text{im}\partial_{i+1}}}$

Now notice that every crackless brick tiling with $k-i$ parts is in the kernel
of $\partial_{i}$, hence

$\displaystyle H_{i}(C)$
$\displaystyle=\frac{\overline{C}_{i}}{\overline{\text{im}\partial_{i+1}}}$

We know that $\mathrm{im}\partial_{i+1}$ is generated by $\partial_{i}e_{A}$
for $e_{A}\in C_{i+1}$. The crackless part of $\mathrm{im}\partial_{i+1}$ is
generated by image of $e_{A}\in C_{i+1}$ which have exactly one crack, and for
each such $A$ we have

$\displaystyle\partial_{i+1}e_{A}$ $\displaystyle=e_{B}+e_{B^{\prime}}$

where $B$ and $B^{\prime}$ you get by “ _cracking_ ” $A$ in either way. This
implies we can thought of $H_{i}(C)$ as

$\displaystyle H_{i}(C)$
$\displaystyle=\frac{\overline{C}_{i}}{(e_{B}=e_{B^{\prime}})}$

Since this says $e_{B}=e_{B^{\prime}}$, whenever the Young diagram of $B$
differs from $B^{\prime}$ by a simple transposition. Now notice that if
$e_{A}\in\overline{C}_{i}$, then for every permutation $A^{\prime}$ of $A$,
$e_{A^{\prime}}\in\overline{C}_{i}$. But the relation $e_{B}=e_{B^{\prime}}$
identify all of them since all permutations are generated by transpositions.
This implies $H_{i}(C)$ is generated by $e_{A}$, where $A$ is an unordered
crackless brick tiling with $j-i$ parts. Hence

$\dim H_{i}(C)=\sum_{\begin{subarray}{c}\mu\vdash j\\\
\ell(\mu)=j-i\end{subarray}}\eta^{\mu}(w)$ (13)

Now using this, we provide a proof for theorem 2.5.

###### Proof.

Given positive integer $j\leq n$, for any permutation $w\in\mathfrak{S}_{n}$,
we construct the poset $\mathrm{Til}(w;j)$, and consider the chain complex
associated to it as defined above. The construction implies that the
$\dim(C_{i})$ is given by

$\displaystyle\dim(C_{i})$ $\displaystyle=\sum_{\begin{subarray}{c}\mu\vDash
j\\\ \ell(\mu)=j-i\end{subarray}}\zeta^{\mu}(w)$

Now we can compute Euler characteristic of this chain complex as an
alternating sum of these dimensions, which gives

$\displaystyle\sum_{i=0}^{j-1}(-1)^{i}\dim(C_{i})$
$\displaystyle=\sum_{i=0}^{j-1}(-1)^{i}\sum_{\begin{subarray}{c}\mu\vDash j\\\
\ell(\mu)=j-i\end{subarray}}\zeta^{\mu}(w)$ $\displaystyle=\sum_{\mu\vDash
j}(-1)^{j-\ell(\mu)}\zeta^{\mu}(w)$

while, computing the Euler characteristic via alternating sum of dimensions of
homologies (employing equation 13 ) gives

$\displaystyle\sum_{i=0}^{j-1}(-1)^{i}\dim(H_{i})$
$\displaystyle=\sum_{i=0}^{j-1}(-1)^{i}\sum_{\begin{subarray}{c}\mu\vdash j\\\
\ell(\mu)=j-i\end{subarray}}\eta^{\mu}(w)$ $\displaystyle=\sum_{\mu\vdash
j}(-1)^{j-\ell(\mu)}\eta^{\mu}(w)$

Since both of the them are Euler characteristic of the same complex, hence
they are equal for each $w\in\mathfrak{S}_{n}$. This implies that the equality
holds as equality of class functions on $\mathfrak{S}_{n}$. ∎

###  2.5 Counting proof

Though the proof using homology on brick tiling poset was quite interesting,
we were also tempted to provide a counting proof. This is given below:

###### Proof.

Since $\zeta^{\lambda}=\zeta^{\mu}$ for $\mu\vdash j$ and $\lambda\vDash j$
such that $\tilde{\lambda}=\mu$, we can write

$\displaystyle\sum_{\mu\vDash j}(-1)^{\ell(\mu)}\zeta^{\mu}$
$\displaystyle=\sum_{\mu\vdash
j}(-1)^{\ell(\mu)}\sum_{\tilde{\lambda}=\mu}\zeta^{\lambda}$

The sum $\sum_{\tilde{\lambda}=\mu}\zeta^{\lambda}(w)$ counts the number of
ordered tilings by $w$ of all compositions $\lambda$ whose underlying
partition is $\mu$. This can also be regarded as counting all permutations (of
parts) of unordered brick tilings of $\mu$. Therefore, we can rewrite

$\displaystyle\sum_{\mu\vdash
j}(-1)^{\ell(\mu)}\sum_{\tilde{\lambda}=\mu}\zeta^{\lambda}(w)$
$\displaystyle=\sum_{\mu\vdash j}(-1)^{\ell(\mu)}\ell(w)!\xi^{\mu}(w)$

where $\xi^{\mu}(w)$ is the number of unordered tilings of $\mu$ by $w$. For a
subset of bricks $T\subseteq B_{w}$, let $\xi^{\mu}_{T}$ be the number of
unordered brick tilings of $\mu$ by $T$, then we can count the sum over $T$’s

$\displaystyle\sum_{\mu\vdash j}(-1)^{\ell(\mu)}\ell(\mu)!\xi^{\mu}(w)$
$\displaystyle=\sum_{\mu\vdash j}(-1)^{\ell(\mu)}\ell(\mu)!\sum_{T\subseteq
B_{w}}\xi^{\mu}_{T}$ $\displaystyle=\sum_{T\subseteq B_{w}}\sum_{\mu\vdash
j}(-1)^{\ell(\mu)}\ell(\mu)!\xi^{\mu}_{T}$ $\displaystyle=\sum_{T\subseteq
B_{w}}\sum_{k=1}^{j}\sum_{\begin{subarray}{c}\mu\vdash j\\\
\ell(\mu)=k\end{subarray}}(-1)^{\ell(\mu)}\ell(\mu)!\xi^{\mu}_{T}$
$\displaystyle=\sum_{T\subseteq
B_{w}}\sum_{k=1}^{j}(-1)^{k}k!\sum_{\begin{subarray}{c}\mu\vdash j\\\
\ell(\mu)=k\end{subarray}}\xi^{\mu}_{T}$

Since the tilings counted in $\sum_{\begin{subarray}{c}\mu\vdash j\\\
\ell(\mu)=k\end{subarray}}\xi^{\mu}_{T}$ is in one to one correspondence with
unordered partitions of $T$ into $k$ sets. These are counted by Stirling
numbers of second kind $\begin{Bmatrix}\ell(\mathrm{sh}(T))\\\
k\end{Bmatrix}$.

$\displaystyle\sum_{T\subseteq
B_{w}}\sum_{k=1}^{j}(-1)^{k}k!\sum_{\begin{subarray}{c}\mu\vdash j\\\
\ell(\mu)=k\end{subarray}}\xi^{\mu}_{T}(\pi)$ $\displaystyle=\sum_{T\subseteq
B_{w}}\sum_{k=1}^{j}(-1)^{k}k!\begin{Bmatrix}\ell(\mathrm{sh}(T))\\\
k\end{Bmatrix}$

We have encountered the inner alternating sum in before, and from equation 5
it equals $(-1)^{\ell(\mathrm{sh}(T))}$. Hence,

$\displaystyle\sum_{\mu\vDash j}(-1)^{\ell(\mu)}\zeta^{\mu}$
$\displaystyle=\sum_{T\subseteq B_{w}}(-1)^{\ell(\mathrm{sh}(T))}$
$\displaystyle=\sum_{\mu\vdash j}\sum_{\begin{subarray}{c}T\subseteq B_{w}\\\
\mathrm{sh}(T)=\mu\end{subarray}}(-1)^{\ell(\mu)}$
$\displaystyle=\sum_{\mu\vdash
j}(-1)^{\ell(\mu)}\sum_{\begin{subarray}{c}T\subseteq B_{w}\\\
\mathrm{sh}(T)=\mu\end{subarray}}1$

Now the interior sum just counts the number of unordered tilings of $\mu$ by
$B_{w}$ as indicated by equation 3. Therefore

$\displaystyle\sum_{\mu\vDash j}(-1)^{\ell(\mu)}\zeta^{\mu}$
$\displaystyle=\sum_{\mu\vdash j}(-1)^{\ell(\mu)}\eta^{\mu}(w)$

∎

Let us illustrate the identity 2.5 using a small example:

######  Example 2.8.

In the table 2, we take the case of $j=4$.

$\zeta^{(4)}$ | $=$ | $\eta^{(4)}$ | $+$ | $\eta^{(3,1)}$ | $+$ | $\eta^{(2,2)}$ | $+$ | $\eta^{(2,1,1)}$ | $+$ | $\eta^{(1,1,1,1)}$
---|---|---|---|---|---|---|---|---|---|---
$\zeta^{(3,1)}$ | $=$ |  |  | $\eta^{(3,1)}$ |  |  |  | $2\eta^{(2,1,1)}$ | $+$ | $4\eta^{(1,1,1,1)}$
$\zeta^{(1,3)}$ | $=$ |  |  | $\eta^{(3,1)}$ |  |  |  | $2\eta^{(2,1,1)}$ | $+$ | $4\eta^{(1,1,1,1)}$
$\zeta^{(2,2)}$ | $=$ |  |  |  |  | $2\eta^{(2,2)}$ | $+$ | $2\eta^{(2,1,1)}$ | $+$ | $12\eta^{(1,1,1,1)}$
$\zeta^{(2,1,1)}$ | $=$ |  |  |  |  |  |  | $2\eta^{(2,1,1)}$ | $+$ | $6\eta^{(1,1,1,1)}$
$\zeta^{(1,2,1)}$ | $=$ |  |  |  |  |  |  | $2\eta^{(2,1,1)}$ | $+$ | $6\eta^{(1,1,1,1)}$
$\zeta^{(1,1,2)}$ | $=$ |  |  |  |  |  |  | $2\eta^{(2,1,1)}$ | $+$ | $6\eta^{(1,1,1,1)}$
$\zeta^{(1,1,1,1)}$ | $=$ |  |  |  |  |  |  |  |  | $24\eta^{(1,1,1,1)}$
Table 2: Example for $j=4$

From the table 2, we can see that $\sum_{\mu\vDash
4}(-1)^{\ell(\mu)}\zeta^{\mu}$ equals

$\displaystyle-\eta^{(4)}+\eta^{(3,1)}+\eta^{(2,2)}-\eta^{(2,1,1)}+\eta^{(1,1,1,1)}$

##  3 Applications

In order to continue our study for generating functions of character
polynomals, and apply our results to get some previously known identities we
define the notion of stability in first subsection. The generating function
relevant to our discussion is cycle-index generating function. We go back to
our main identity 2.5 and use it to derive Goupil’s generating function
identity [Gou99] for hook partitions. Lastly, combining this identity with
stability of cycle-index generating function, we were able to provide an
alternating proof of Rosas’ formula [Ros00].

###  3.1 Stability for sequence of polynomials and power series

We say a sequence $(f_{n})_{n\in\mathbb{N}}$ of polynomials
$f_{n}\in\mathbb{Q}[x]$, _stabilizes_ to $f\in\mathbb{Q}[[x]]$ if for each
positive integer $k$, there exists a positive integer $N_{k}$ such that for
all $m,n>N_{k}$, we can find $f\in\mathbb{Q}[x]$ satisfying

$\displaystyle[x^{k}]f_{m}$ $\displaystyle=[x^{k}]f_{n}=[x^{k}]f$

where $[x^{k}]f$ denote the coefficient of $x^{k}$ in $f$. If $f$ exists, then
it is seen to be unique. This definition can also be generalized to
multivariable case. We say a sequence $(f_{n})_{n\in\mathbb{N}}$ of
multivariable polynomials $f_{n}\in\mathbb{Q}[x_{1},x_{2},\cdots,x_{r}]$,
_stabilizes_ to $f\in\mathbb{Q}[[x_{1},\cdots,x_{r}]]$ if for each sequence of
positive integers $k=(k_{1},\cdots,k_{r})$, there exists a positive integer
$N_{k}$ such that for all $m,n>N_{k}$, we can find $f\in\mathbb{Q}[x]$
satisfying

$\displaystyle[x_{1}^{k_{1}}\cdots x_{r}^{k_{r}}]f_{m}$
$\displaystyle=[x_{1}^{k_{1}}\cdots x_{r}^{k_{r}}]f_{n}=[x^{k}]f$

######  Example 3.1.

Let $f_{n}(x)=x^{n}+x^{n-1}+\dots+x+1$ is a sequence which stabilizes to
$f(x)=\frac{1}{1-x}$. On the other hand the sequence $f_{n}(x)=x^{n}$ does not
stabilize. An example for multivariable case would be the sequence

$\displaystyle g_{n}(x,y)$ $\displaystyle=\sum_{i+j=n}x^{i}y^{j}$

this sequence stabilize to

$\displaystyle g(x,y)$ $\displaystyle=\frac{1}{1-x}\frac{1}{1-y}$

For a commutative ring $R$ and an element $f\in R[[t]]$, we say _coefficients
of $f$ stabilize_ if there exists a least integer $k$ such that for all $n>k$,
we have

$\displaystyle[t^{n}]f=[t^{n+1}]f$

The limiting coefficient is called _coefficient of stabilization_ , and such a
$k$ is called _point of stability_.

######  Example 3.2.

Given a polynomial $p(t)\in\mathbb{Q}[t]$, the coefficents of the power series

$\displaystyle\frac{p(t)}{1-t}\in\mathbb{Q}[[t]]$

stabilizes with coefficient of stabilization $p(1)$ and point of stability is
$\deg(p)+1$.

We require a generalization of the above notion for the ring
$\mathbb{Q}[c_{1},c_{2},\cdots][[t]]$ of formal power series. Consider an
element $f\in\mathbb{Q}[c_{1},c_{2},\cdots][[t]]$, given by

$\displaystyle f$ $\displaystyle=\sum_{n=0}^{\infty}f_{n}t^{n}$

where $f_{n}\in\mathbb{Q}[c_{1},c_{2},\cdots]$ are polynomials in $c_{i}$’s.
We say $f$ _stabilizes_ if the sequence of polynomials
$(f_{n})_{n\in\mathbb{N}}$ stabilizes to some $g$. In that case, there exists
sequence $(m_{1},\cdots,m_{r})$ such that we have the equality

$\displaystyle[c_{1}^{k_{1}}\cdots c_{r}^{k_{r}}]f$
$\displaystyle=[c_{1}^{k_{1}}\cdots c_{r}^{k_{r}}]\frac{g}{1-t}$

for $k_{i}>m_{i}$ for all $i$.

######  Example 3.3.

Consider the element $f\in\mathbb{Q}[x][[t]]$ given by

$\displaystyle f$ $\displaystyle=1+(1+x)t+(1+x+x^{2})t+\cdots$

then $g=\frac{1}{1-x}$, and therefore $f$ stabilizes to

$\displaystyle\frac{1}{1-x}\frac{1}{1-t}$

###  3.2 The cycle-index generating function

Recall the _cycle index_ of the symmetric group $\mathfrak{S}_{n}$ which is
defined as

$\displaystyle Z(\mathfrak{S}_{n})$
$\displaystyle=\frac{1}{n!}\sum_{w\in\mathfrak{S}_{n}}\prod_{i=1}^{n}x_{i}^{c_{i}(w)}$

It is well known, for example from [Cam99], that the generating function
$\Gamma$ of cycle indices of $\mathfrak{S}_{n}$ is given by

$\displaystyle\Gamma$
$\displaystyle=1+\sum_{n=1}^{\infty}Z(\mathfrak{S}_{n})t^{n}$

can also be written as

$\Gamma=\exp\left(\sum_{i=1}^{\infty}\frac{x_{i}t^{i}}{i}\right)$ (14)

This is a very useful result as indicated by the following example:

######  Example 3.4.

Consider the formal equality

$\displaystyle 1+\sum_{n=1}^{\infty}Z(\mathfrak{S}_{n})t^{n}$
$\displaystyle=\exp\left(\sum_{i=1}^{\infty}\frac{x_{i}t^{i}}{i}\right)$

Evaluating the formal partial derivative $\frac{\partial}{\partial x_{k}}$ of
both sides at $x_{i}=1$ for all $i=1,2,\cdots$, gives the following

$\displaystyle\sum_{n=1}^{\infty}\bigg{(}\frac{1}{n!}\sum_{w\in\mathfrak{S}_{n}}c_{k}(w)\bigg{)}t^{n}$
$\displaystyle=\frac{1}{k}\frac{t^{k}}{1-t}$

which is saying that the expected number of $k$ cycles in a permutation of
$\mathfrak{S}_{n}$ for $n\geq k$ equals $\frac{1}{k}$. This is a classical
result in combinatorial probability theory [B1́2].

Some other identities we would like to highlight here are

$\Gamma[x_{i}\longrightarrow x^{i}]=\frac{1}{1-xt}$ (15)

and

$\Gamma[x_{i}\longrightarrow 1-x^{i}]=\frac{1-xt}{1-t}$ (16)

where the notation $\Gamma[x_{i}\longrightarrow f(x_{i})]$ means substituting
$f(x_{i})$ for $x_{i}$ in the expression for $\Gamma$.

###  3.3 Goupil’s generating function identity

Going back to our identity 2.5, we consider the class function

$\displaystyle\sum_{\mu\vdash j}(-1)^{\ell(\mu)+1}\eta^{\mu}$

from the identity 8, we have the following generating function

$\displaystyle\sum_{j=0}^{\infty}\left(\sum_{\mu\vdash
j}(-1)^{\ell(\mu)+1}\eta^{\mu}\right)t^{j}$
$\displaystyle=\prod_{i=1}^{\infty}\bigg{(}1-(-t)^{i}\bigg{)}^{c_{i}}$

Using this and theorem 2.4 we have another proof of the following identity of
Goupil [Gou99] for generating function for hook characters

######  Theorem 3.5.

For $\lambda=(1^{k})\vdash k$, we have the following generating function

$\sum_{k=0}^{\infty}q_{(1^{k})}t^{k}\doteq\frac{1}{1+t}\prod_{i=1}^{\infty}\bigg{(}1-(-t)^{i}\bigg{)}^{c_{i}}$
(17)

###### Proof.

Since from theorem 2.4, we have

$\displaystyle\chi^{\lambda[n]}$
$\displaystyle=\sum_{j=0}^{k}(-1)^{j+1}\left(\sum_{\mu\vDash
j}(-1)^{\ell(\mu)}\zeta^{\mu}\right)$

which corresponds to alternating sum of class function whose generating
function is given by equation 17. Now recall that the generating function for
alternating sum of a sequence can be constructed by multiplying the generating
function by $\frac{1}{1+t}$. This gives the required result. ∎

######  Example 3.6.

From the above expression we derive expressions for first few character
polynomials. A table of these can also be found in [Ker99]

$\displaystyle q_{()}$ $\displaystyle=1$ $\displaystyle q_{(1)}$
$\displaystyle=\binom{c_{1}}{1}-1$ $\displaystyle q_{(1^{2})}$
$\displaystyle=\binom{c_{1}}{2}-\binom{c_{2}}{1}-\binom{c_{1}}{1}+1$
$\displaystyle q_{(1^{3})}$
$\displaystyle=\binom{c_{1}}{2}-\binom{c_{1}}{1}\binom{c_{2}}{1}+\binom{c_{3}}{1}-\binom{c_{1}}{2}+\binom{c_{2}}{1}+\binom{c_{1}}{1}-1$

###  3.4 Rosas’ formula for certain Kronecker coefficients

Let $\lambda,\mu$ and $\nu$ be partitions of $n$. The Kronecker coefficients
$g^{\lambda}_{\mu\nu}(\mathfrak{S}_{n})$ are defined as the coefficient of
$\chi^{\lambda}$ in the expansion of $\chi^{\mu}\chi^{\nu}$ into irreducible
characters:

$\displaystyle
g^{\lambda}_{\mu\nu}({\mathfrak{S}_{n}})=\left<\chi^{\lambda},\chi^{\mu}\chi^{\nu}\right>_{\mathfrak{S}_{n}}=\frac{1}{n!}\sum_{\sigma\in\mathfrak{S}_{n}}\chi^{\lambda}(\sigma)\chi^{\mu}(\sigma)\chi^{\nu}(\sigma)$

Using the equation 17 for generating function of irreducible hook character,
here we will derive the formula for Kronecker coefficients indexed by hooks
given by Rosas [Ros00], which says:

######  Theorem 3.7.

Let $\overline{g}_{k_{1}k_{2}k_{3}}$ be the reduced Kronecker coefficients
corresponding to the triple
$((n-k_{1},1^{k_{1}}),(n-k_{2},1^{k_{2}}),(n-k_{3},1^{k_{3}}))$, then

$\displaystyle\sum_{k_{1},k_{2},k_{3}}\overline{g}_{k_{1}k_{2}k_{3}}x^{k_{1}}y^{k_{2}}z^{k_{3}}$
$\displaystyle=\frac{1+xyz}{(1-xy)(1-yz)(1-xz)}$

###### Proof.

We start with the substituion $x_{i}\leftarrow(1-(-x)^{i})$ in the cycle index
function

$\displaystyle Z(\mathfrak{S}_{n})[x_{i}\leftarrow(1-(-x)^{i})]$
$\displaystyle=\frac{1}{n!}\sum_{w\in\mathfrak{S}_{n}}\prod_{i=1}^{n}(1-(-x)^{i})^{a_{i}(w)}$
$\displaystyle[x^{k}]\frac{1}{1+x}Z(\mathfrak{S}_{n})[x_{i}\leftarrow(1-(-x)^{i})]$
$\displaystyle=\frac{1}{n!}\sum_{w\in\mathfrak{S}_{n}}\chi^{(1^{k})[n]}(w)$

This suggests that if we let
$Y_{n}=Z(\mathfrak{S}_{n})[x_{i}\leftarrow(1-(-x)^{i})(1-(-y)^{i})(1-(-z)^{i})]$,
we have

$\displaystyle[x^{k_{1}}y^{k_{2}}z^{k_{3}}]\frac{1}{(1+x)(1+y)(1+z)}Y_{n}$
$\displaystyle=\frac{1}{n!}\sum_{w\in\mathfrak{S}_{n}}\chi^{(1^{k_{1}})[n]}(w)\chi^{(1^{k_{2}})[n]}(w)\chi^{(1^{k_{3}})[n]}(w)$
$\displaystyle=g_{k_{1}k_{2}k_{3}}$

Now notice that $Y:=\sum_{n=0}^{\infty}Y_{n}t^{n}$ is given by substituting
$[x_{i}\leftarrow(1-(-x)^{i})(1-(-y)^{i})(1-(-z)^{i})]$ in $\Gamma$ which
using equation 14 becomes

$\displaystyle Y$
$\displaystyle=\exp\left(\sum_{i=1}^{\infty}\frac{x_{i}}{i}t^{i}\right)[x_{i}\leftarrow(1-(-x)^{i})(1-(-y)^{i})(1-(-z)^{i})]$

Now using equation 16, we have

$\displaystyle Y$
$\displaystyle=\frac{1}{1-t}\frac{(1+xyzt)(1+xt)(1+yt)(1+zt)}{(1-xyt)(1-yzt)(1-xzt)}$

Note that the identity

$\displaystyle W:=\frac{1}{1-t}\frac{1}{(1-xyt)(1-yzt)(1-xzt)}$
$\displaystyle=\left(\sum_{i=0}^{\infty}\left(\sum_{j=0}^{n}\sum_{a+b+c=j}(xy)^{a}(yz)^{b}(xz)^{c}\right)t^{n}\right)$

implies that $W$ as member of $\mathbb{Q}[x,y,z][[t]]$ stabilize to

$\displaystyle\frac{1}{1-t}\frac{1}{(1-xy)(1-yz)(1-xz)}$

which in turn implies that $\frac{1}{(1+x)(1+y)(1+z)}Y$ stabilizes to

$\displaystyle\frac{1}{1-t}\frac{(1+xyz)}{(1-xy)(1-yz)(1-xz)}$

but $\frac{1}{(1+x)(1+y)(1+z)}Y$ is the generating function of
$g_{k_{1}k_{2}k_{3}}$. This implies that the generating function for the
reduced Kronecker coefficients $\overline{g}_{k_{1}k_{2}k_{3}}$ is given by

$\displaystyle\frac{(1+xyz)}{(1-xy)(1-yz)(1-xz)}$

∎

## References

  * [B1́2] Miklós Bóna, _Combinatorics of permutations_ , second ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2012, With a foreword by Richard Stanley. MR 2919720
  * [Cam99] Peter J. Cameron, _Permutation groups_ , London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999. MR 1721031
  * [CEF15] Thomas Church, Jordan S. Ellenberg, and Benson Farb, _FI-modules and stability for representations of symmetric groups_ , Duke Math. J. 164 (2015), no. 9, 1833–1910. MR 3357185
  * [Dou73] Peter Doubilet, _An inversion formula involving partitions_ , Bull. Amer. Math. Soc. 79 (1973), 177–179. MR 0307933
  * [Fro04] G. Frobenius, _Über die charaktere der mehrfach transitiven gruppen_ , Preussische Akademie der Wissenschaften Berlin: Sitzungsberichte der Preußischen Akademie der Wissenschaften zu Berlin, Reichsdr., 1904.
  * [FS78] Dominique Foata and Marcel-Paul Schützenberger, _Major index and inversion number of permutations_ , Math. Nachr. 83 (1978), 143–159. MR 506852
  * [GG09] A. M. Garsia and A. Goupil, _Character polynomials, their $q$-analogs and the Kronecker product_, Electron. J. Combin. 16 (2009), no. 2, Special volume in honor of Anders Björner, Research Paper 19, 40. MR 2576382
  * [Gou99] Alain Goupil, _Generating functions for irreducible characters of $S_{n}$ indexed with multiple hooks_, Ann. Sci. Math. Québec 23 (1999), no. 2, 189–198. MR 1748144
  * [Ker99] Adalbert Kerber, _Applied finite group actions_ , second ed., Algorithms and Combinatorics, vol. 19, Springer-Verlag, Berlin, 1999. MR 1716962
  * [Mac79] I. G. Macdonald, _Symmetric functions and Hall polynomials_ , The Clarendon Press, Oxford University Press, New York, 1979, Oxford Mathematical Monographs. MR 553598
  * [Mur37] F. D. Murnaghan, _The Characters of the Symmetric Group_ , Amer. J. Math. 59 (1937), no. 4, 739–753. MR 1507276
  * [Mur51] Francis D. Murnaghan, _The characters of the symmetric group_ , Proc. Nat. Acad. Sci. U.S.A. 37 (1951), 55–58. MR 0039725
  * [OZ15] Rosa Orellana and Mike Zabrocki, _Symmetric group characters as symmetric functions (extended abstract)_ , ArXiv e-prints (2015), arXiv:1510.00438.
  * [Ros00] Mercedes H. Rosas, _The Kronecker product of Schur functions indexed by two-row shapes or hook shapes_ , Formal power series and algebraic combinatorics (Moscow, 2000), Springer, Berlin, 2000, pp. 344–355. MR 1798227
  * [Spe60] Wilhelm Specht, _Die Charaktere der symmetrischen Gruppe_ , Math. Z. 73 (1960), 312–329. MR 0113955
  * [Ste12] Benjamin Steinberg, _Representation theory of finite groups_ , Universitext, Springer, New York, 2012, An introductory approach. MR 2867444
  * [Zie95] Günter M. Ziegler, _Lectures on polytopes_ , Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028


# Finite Gaussian Neurons:
Defending against adversarial attacks
by making neural networks say “I don’t know”

Felix Grezes

Pr. Michael I. MandelPr. Rivka LevitanPr. Ioannis StamosDr. Andrew
RosenbergPr. Ping Ji

Pr. Michael I. Mandel Since 2014, artificial neural networks have been known
to be vulnerable to adversarial attacks, which can fool the network into
producing wrong or nonsensical outputs by making humanly imperceptible
alterations to inputs.

While defenses against adversarial attacks have been proposed, they usually
involve retraining a new neural network from scratch, a costly task.

In this work, I introduce the Finite Gaussian Neuron (FGN), a novel neuron
architecture for artificial neural networks111The code used for this work is
available at https://github.com/grezesf/FGN---Research under the GPL 3.0 open
source license. Work done with PyTorch..

My works aims to:

  * •

easily convert existing models to Finite Gaussian Neuron architecture,

  * •

while preserving the existing model’s behavior on real data,

  * •

and offering resistance against adversarial attacks.

I show that converted and retrained Finite Gaussian Neural Networks (FGNN)
always have lower confidence (i.e., are not overconfident) in their
predictions over randomized and Fast Gradient Sign Method adversarial images
when compared to classical neural networks, while maintaining high accuracy
and confidence over real MNIST images. To further validate the capacity of
Finite Gaussian Neurons to protect from adversarial attacks, I compare the
behavior of FGNs to that of Bayesian Neural Networks against both randomized
and adversarial images, and show how the behavior of the two architectures
differs. Finally I show some limitations of the FGN models by testing them on
the more complex SPEECHCOMMANDS task, against the stronger Carlini-Wagner and
Projected Gradient Descent adversarial attacks.