\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Permutations and Combinations of Colored \\
\vskip .1in
Multisets
}
\vskip 1cm
\large
Jocelyn Quaintance\\
Department of Mathematics \\
West Virginia University \\
Morgantown, WV 26506 \\
USA \\
\href{mailto:jquainta@math.wvu.edu}{\tt jquainta@math.wvu.edu}\\
\bigskip
Harris Kwong\\
SUNY Fredonia\\
Department of Mathematical Sciences\\
State University of New York at Fredonia\\
Fredonia, NY 14063 \\
USA\\
\href{mailto:kwong@fredonia.edu}{\tt kwong@fredonia.edu}\\
\end{center}

\vskip .2 in

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

\def\rnum#1{\mbox{\textcolor{red}{\bf\sf #1}}}
\def\bnum#1{\mbox{\textcolor{blue}{\bf\sf #1}}}
\def\gnum#1{\mbox{\textcolor{green}{\bf\sf #1}}}

\begin{abstract}
Given positive integers $m$ and $n$, let $S_n^m$ be the $m$-colored
multiset $\{1^m,2^m,\ldots,n^m\}$, where $i^m$ denotes $m$ copies of
$i$, each with a distinct color.  This paper discusses two types of
combinatorial identities associated with the permutations and
combinations of $S_n^m$.  The first identity provides, for $m\geq 2$,
an $(m-1)$-fold sum for ${mn\choose n}$.  The second type of
identities can be expressed in terms of the Hermite polynomial, and
counts color-symmetrical permutations of $S_n^2$, which are
permutations whose underlying uncolored permutations remain fixed
after reflection and a permutation of the uncolored numbers.
\end{abstract}

%%%%%%%%%%%
% Section 1
%%%%%%%%%%%

\section{Introduction}

The primary object of study in this paper is a certain class of
multisets, namely the $m$-colored multisets $S_n^m=\{1^m,2^m,\ldots,
n^m\}$, where $i^m$ denotes $m$ copies of $i$ with distinct colors.
Where does $S_n^m$ naturally arise in combinatorics?  Suppose we want
to count the permutations of $S_n^m$ of length $n$ which consist of
\emph{distinct} integers.  First, we ignore the colors of the integers
and notice we have a set of $n$ distinct uncolored numbers.  There are
$n!$ ways to arrange these $n$ uncolored numbers.  We then decide what
color to paint such numbers.  Since there are $m$ colors, this color
choice gives us a factor of $m^n$, for a total of $m^nn!$ such
permutations.  In \cite{df}, the authors studied properties of
multifactorials $n!_m$, where for a positive integer $m$, $n!_m =
n(n-m)!_m$, with $0!_m = 1$.  From this recursive definition, we can
show that $(mn)!_m = m^nn!$.  Therefore, the $m$-colored multiset
provides a combinatorial meaning for well-known multifactorial
identity.

This observation leads us to wonder if $m$-colored multisets could
provide nice combinatorial proofs for other well known identities.  In
the process of investigating this question, the authors found two
general classes of identities that are readily proven in the context
of $S_n^m$.  The first type of identity provides a $(m-1)$-sum formula
for the binomial coefficient ${mn\choose n}$.  This result is
Theorem~\ref{thm:1.1}.  The second type of identity counts
color-symmetrical permutations of $S_n^2$, where a
\textbf{\emph{color-symmetrical}} permutation of $S_n^2$ is a colored
permutation whose underlying set partition structure is fixed via
vertical reflection.  The color-symmetrical permutation identities
occur in Section~\ref{sec3} have connections with Hermite polynomials.
The techniques used to prove the identities of Section~\ref{sec3}
recall the methodology the first author used to enumerate
symmetrically inequivalent two dimensional proper arrays \cite{jq2}.

%%%%%%%%%%%
% Section 2
%%%%%%%%%%%

\section{Enumerating Combinations and Permutations}

Let $i$, $m$, and $n$ be positive integers.  Let $i^m$ denote $m$
copies of $i$, with the property that each copy of $i$ has a
\emph{distinct} color.  Let $S_n^m$ be the
\textbf{\emph{$m$-colored multiset}} $\{1^m,
2^m,\ldots,n^m\}$.  For examples,  
  \[ S_4^2 = \{
  \rnum{1}, \bnum{1}, \rnum{2}, \bnum{2}, 
  \rnum{3}, \bnum{3}, \rnum{4}, \bnum{4}\}, 
  \qquad\mbox{and}\qquad
  S_4^3 = \{
  \rnum{1}, \bnum{1}, \gnum{1}, \rnum{2}, \bnum{2}, \gnum{4}, 
  \rnum{3}, \bnum{3}, \gnum{3}, \rnum{4}, \bnum{4}, \gnum{4}\}. \]
Note that $|S_n^m| = mn$.  If we consider different colored copies of
$i$ as distinct, the number of permutations of $S_n^m$ is $(mn)!$.
From this simple observation, we are able to derive an identity for
$(mn)!$ involving an $(m-1)$-fold summation.  We will now assume
$m\geq 2$.  The proof of this identity utilizes simple combinatorial
arguments.  We demonstrate the argument for the case of $m = 2$, and
then state the general result for $m\geq 2$.

Consider $S^2_n = \{1^2, 2^2,\ldots,n^2\}$, where each number occurs in
red and blue.  The number of permutations of $S_n^2$ is $(2n)!$.  We
think of a permutation of $S_n^2$ as a horizontal row of $2n$ elements
arranged in $2n$ slots.  Our analysis proceeds by carefully analyzing
the manner in which we fill in the first half, or the first $n$ slots,
of the permutation.  We say a number $i$, where $1\leq i\leq n$, has a
\textbf{\emph{repetition}} in the first half if and only if both the
red $i$ and the blue $i$ can be found there.  Let $s$ be the number of
repetitions that occur in the first half of the permutation.  Note
that $0\leq s\leq [\frac{n}{2}]$.  For each $s$, the number of ways to
fill the first $n$ slots can be computed in three steps (see
Figure~\ref{fig:3step}). 

\begin{enumerate} 
\item
Pick the locations, in the first half of the permutation, where the
repetitions will occur.  The number of ways to select $s$ pairs of
slots from the $n$ slots is
  \[ \prod_{j=1}^s\frac{{n-2j+2\choose 2}}{s!} 
  = \frac{n!}{s!(n-2s)!2^s}. \]

\item
Pick the numbers to fill these $s$ pairs of slots.  In order to do
this, we first form an $s$-permutation from $D = \{1,2,\ldots,n\}$.
The $k^{th}$ number in this $s$-permutation will fill the $k^{th}$
pair of slots.  For each pair of slots, we must decide if we want red
first, then blue, or vice versa.  Hence, the number of ways to fill
these $s$ pairs of slots is $\frac{n!}{(n-s)!}2^s$.

\item
Fill the remaining $n-2s$ spaces in the first half of the permutation
with numbers that have not been used in Step 2.  The number of ways to
do this is $\frac{(n-s)!}{s!}2^{n-2s}$.
\end{enumerate}

\begin{figure}[htb]
\begin{center}  \setlength{\unitlength}{0.85pt}
\begin{picture}(280,40)(-80,-10)
\put(-60,0){\makebox(60,20)[l]{Step 1:}}
\multiput(0,0)(0,20){ 2}{\line(1,0){200}}
\multiput(0,0)(20,0){11}{\line(0,1){ 20}}
\put(100,-10){\line(0,1){40}}
\multiput(10,10)(20,0){2}{\circle*{10}}
\multiput(40, 0)(40,0){2}{\makebox(20,20){\bf\sf X}}
\end{picture}
\\ \ \\
\begin{picture}(280,40)(-80,-10)
\put(-60,0){\makebox(60,20)[l]{Step 2:}}
\multiput(0,0)(0,20){ 2}{\line(1,0){200}}
\multiput(0,0)(20,0){11}{\line(0,1){ 20}}
\put(100,-10){\line(0,1){40}}
\put( 0,0){\makebox(20,20){\rnum{2}}}
\put(20,0){\makebox(20,20){\bnum{2}}}
\put(40,0){\makebox(20,20){\bnum{4}}}
\put(80,0){\makebox(20,20){\rnum{4}}}
\end{picture}
\\ \ \\
\begin{picture}(280,70)(-80,-30)
\put(-60,0){\makebox(60,20)[l]{Step 3:}}
\multiput(0,0)(0,20){ 2}{\line(1,0){200}}
\multiput(0,0)(20,0){11}{\line(0,1){ 20}}
\put(100,-10){\line(0,1){40}}
\put( 0,0){\makebox(20,20){\rnum{2}}}
\put(20,0){\makebox(20,20){\bnum{2}}}
\put(40,0){\makebox(20,20){\bnum{4}}}
\put(80,0){\makebox(20,20){\rnum{4}}}
\put(60,0){\makebox(20,20){\rnum{3}}}
\put(0,-40){\makebox(200,20){Remaining numbers: 
  \rnum{1}, \bnum{1}, \bnum{3}, \rnum{5}, \bnum{5}.}}
\end{picture}
\end{center}
\caption{Constructing the first half of a permutation of $S_5^2$.}
\label{fig:3step}
\end{figure}

After completing these three steps, we have $n$ colored numbers
remaining.  They fill the second half of the permutation in $n!$ ways.
Varying $s$ and combining the aforementioned combinatorial reasoning
proves Lemma~\ref{lem:1.1}.

\begin{lemma} \label{lem:1.1}
Let $n$ be a nonnegative integer. Then,
\begin{equation}
  (2n)! 
  = n!\sum_{s=0}^{[\frac{n}{2}]} \frac{n!n!2^{n-2s}}{s!s!(n-2s)!} 
  = (n!)^2 \sum_{s=0}^{[\frac{n}{2}]} {n\choose s} {n-s\choose
    n-2s}2^{n-2s}. 
  \label{Eq1}
\end{equation}
\end{lemma}

\begin{remark} 
Lemma~\ref{lem:1.1} provides a combinatorial proof of Equation (3.99)
in \cite{ci} since we may rewrite Equation (\ref{Eq1}) as follows. 
  \begin{eqnarray*}
  {2n\choose n} 
  &=& \sum_{s=0}^{[\frac{n}{2}]} \frac{n!2^{n-2s}}{s!s!(n-2s)!} \\
  &=& \sum_{s=0}^{[\frac{n}{2}]} \frac{n!}{(2s)!(n-2s)!} \cdot 
      \frac{(2s)!}{s!s!}2^{n-2s} \\
  &=& \sum_{s=0}^{[\frac{n}{2}]} {n\choose 2s} {2s\choose s}2^{n-2s}.
  \end{eqnarray*}
\end{remark}

Here is an alternative argument for deriving Equation~(\ref{Eq1}).  Let
$D = \{1,2,\ldots,n\}$.  The number of permutations of $S_n^2$ is
$(n!)^2$ times the number of ways to select the $n$ colored numbers
which occur in the first half.  Let $s$ denote the number of numbers
that occur twice, that is, both the red and blue copies are selected.
We note that $0\leq s\leq [\frac{n}{2}]$.  There are ${n\choose s}$
ways to select these $s$ numbers.  From the remaining $n-s$ numbers in
$D$, there are ${n-s\choose n-2s}$ ways to select $n-2s$ uncolored
numbers, where each uncolored number has a choice of two colors to chose
from.  Summing over $s$ yields the right side of Equation~(\ref{Eq1}).

We are now in a position to generalize Lemma~\ref{lem:1.1}.  We will
only describe how to generalize the second argument.  Those readers
interested in the generalization of the first argument may contact the
authors.  We think of a permutation of $S_n^m$ as a horizontal
arrangement of $mn$ elements into $mn$ slots.  Subdivide, from left to
right, these $mn$ slots into $m$ sections, each containing $n$ slots.
We analyze the number of repetitions that occur the first section, or
the leftmost $n$ slots, of the permutation.

We say a number has a \textbf{\emph{repetition of type $k$}} if it
appears exactly $k$ times in the first section.  Let $s_k$ be the
number of numbers of type $k$.  The number of ways to choose $n$
colored numbers to fill the first section of the permutation is
clearly ${mn\choose n}$.  Alternatively, we could choose these $n$
colored numbers from $D = \{1,2,\ldots,n\}$ as follows.  First, we
select the type $m$ numbers, then the type $m-1$ numbers, and so
forth.  There are ${n\choose s_m}$ ways to chose the type $m$ numbers,
each of which will use up all $m$ colors.  In general, after numbers
of types $m$ through $k+1$ are chosen, we have $n-\sum_{i=k+1}^ms_i$
numbers left in $D$ from which to select $s_k$ numbers of type $k$.
Each such number can be colored in ${m\choose k}$ ways.  This argument
proves the following theorem.

\begin{theorem} \label{thm:1.1}
Let $n$ be a positive integer.  Let $m$ be a positive integer,
$m\geq2$.  Then,   
  \begin{equation} \label{Eq4}
  {mn\choose n} 
  = \sum_{\scriptstyle{s_1,s_2,\ldots,s_m\geq 0}
     \atop\scriptstyle{s_1+2s_2+\cdots+ms_m = n}} 
    \prod_{k=1}^m {n-\sum_{i=k+1}^m s_i \choose s_k} {m\choose k}^{s_k}.
 \end{equation}
\end{theorem}

Two important non-trivial examples of Theorem~\ref{thm:1.1} occur when
$m = 3$ and $m = 4$.  Let $m = 3$, and $s_3 = s$, and $s_2 = t$.
Then, Equation~(\ref{Eq4}) becomes
  \[ {3n\choose n} 
  = \sum_{s=0}^{[\frac{n}{3}]} \sum_{t=0}^{[\frac{n-3s}{2}]}
    {n\choose 3s+2t} {3s+2t\choose s,t,2s+t}3^{n-3s-t}. \]
If $m=4$, Equation~(\ref{Eq4}) becomes
  \[ {4n\choose n} 
  = \sum_{s_4=0}^{[\frac{n}{4}]} \sum_{s_3=0}^{[\frac{n-4s_4}{3}]}
    \sum_{s_2=0}^{[\frac{n-4s_4-3s_3}{2}]} 
    A {n\choose n-4s_4-3s_3-2s_2} 
    {4s_4+3s_3+2s_2\choose s_4,s_3,s_2,s_2+2s_3+3s_4}, \]
where, 
  \[ A 
  = \frac{4^{n-4s_4-3s_3-2s_2}(4\cdot3\cdot2)^{s_3}(4\cdot3)^{s_2}}
    {(3!)^{s_3}(2!)^{s_2}}. \]
On closer inspection of the proof of Theorem~\ref{thm:1.1}, we see
that argument describes how to select any $l$ colored numbers from
$S_m^n$.  Thus, we have actually proven the next result.

\begin{theorem} \label{thm:1.2}
Let $n$ and $m$ be positive integers.  Let $l$ be a positive integer
such that $1\leq l\leq mn$.  Then, 
  \[ {mn\choose l}
  = \sum_{\scriptstyle{s_1,s_2,\ldots,s_m\geq 0}\atop
    \scriptstyle{s_1+2s_2+\cdots+ms_m = l}} \prod_{k=1}^m 
    {n-\sum_{i=k+1}^ms_i\choose s_k} {m\choose k}^{s_k}. \]
\end{theorem}

%%%%%%%%%%%
% Section 3
%%%%%%%%%%%

\section{Color-Symmetrical Permutations of $S_n^2$}
\label{sec3}

We now study a special kind of reflective symmetry in the permutations
of $S_n^2$.  Think of a permutation $\sigma$ of $S_n^2$ as a way to
fill the $2n$ squares of a $1\times 2n$ rectangular array, and
associate with it a partition of $\{1,2,\ldots,2n\}$ in the form
$\pi(\sigma)=\{S_1,S_2,\ldots,S_n\}$ such that $S_i$ is the 2-subset
containing the two positions occupied by $i$.  We call $\pi(\sigma)$
the \textbf{\emph{set partition associated with $\sigma$}}.  We say a
permutation is \textbf{\emph{color-symmetrical}} if, upon reflection
about the vertical line through its middle, the resulting permutation
has the same collection of 2-subsets in its associated set partition.
For example, the permutation $p_2$ in Figure~\ref{fig:CSperm1} is
obtained from $p_1$ by reflection.  Notice that
  \[ \pi(p_1) = \pi(p_2) 
  = \big\{\{2,6\}, \{5,9\}, \{3,4\}, \{7,8\}, \{1,10\}\big\}. \]
Therefore $p_1$ is color-symmetrical, and, so is $p_2$.  

\begin{figure}[htb]
\begin{center}  \setlength{\unitlength}{0.85pt}
\begin{picture}(230,40)(-30,0)
\put(-30,0){\makebox(30,20)[l]{$p_1$:}}
\multiput(0,0)(0,20){ 2}{\line(1,0){200}}
\multiput(0,0)(20,0){11}{\line(0,1){ 20}}
\put(100,-10){\line(0,1){40}}
\put(  0,0){\makebox(20,20){\rnum{5}}}
\put( 20,0){\makebox(20,20){\bnum{1}}}
\put( 40,0){\makebox(20,20){\bnum{3}}}
\put( 60,0){\makebox(20,20){\rnum{3}}}
\put( 80,0){\makebox(20,20){\bnum{2}}}
\put(100,0){\makebox(20,20){\rnum{1}}}
\put(120,0){\makebox(20,20){\bnum{4}}}
\put(140,0){\makebox(20,20){\rnum{4}}}
\put(160,0){\makebox(20,20){\rnum{2}}}
\put(180,0){\makebox(20,20){\bnum{5}}}
\end{picture}
\qquad\qquad
\begin{picture}(230,40)(-30,0)
\put(-30,0){\makebox(30,20)[l]{$p_2$:}}
\multiput(0,0)(0,20){ 2}{\line(1,0){200}}
\multiput(0,0)(20,0){11}{\line(0,1){ 20}}
\put(100,-10){\line(0,1){40}}
\put(  0,0){\makebox(20,20){\bnum{5}}}
\put( 20,0){\makebox(20,20){\rnum{2}}}
\put( 40,0){\makebox(20,20){\rnum{4}}}
\put( 60,0){\makebox(20,20){\bnum{4}}}
\put( 80,0){\makebox(20,20){\rnum{1}}}
\put(100,0){\makebox(20,20){\bnum{2}}}
\put(120,0){\makebox(20,20){\rnum{3}}}
\put(140,0){\makebox(20,20){\bnum{3}}}
\put(160,0){\makebox(20,20){\bnum{1}}}
\put(180,0){\makebox(20,20){\rnum{5}}}
\end{picture}
\end{center}
\caption{Two color-symmetrical permutations of $S_5^2$.}
\label{fig:CSperm1}
\end{figure}

Another way to understand this notion of color-symmetry is as follows.
Let $p_2$ be the permutation obtain from $p_1$ via reflection.  The
reflection can be viewed as a function $\phi:S_n^2\rightarrow S_n^2$
such that $\phi(p_1)=p_2$.  We say that $\sigma$ is color-symmetrical
if, for each $i$, $\phi(i^2)=j^2$, for some $j$ (recall that $i^2$
means the two copies of $i$ colored red and blue).  In other words,
$p_1$ is color-symmetrical if one could obtain $p_2$ by renaming the
colored numbers while preserving the associated set partition.  Due to
symmetry, if $\phi(i^2)=j^2$, we also $\phi(j^2)=i^2$.  So in effect
we are interchanging $i^2$ with $j^2$ in the reflection.  For example,
in the two permutations $p_1$ and $p_2$ in Figure~\ref{fig:CSperm1},
the numbers~1 and~2 are interchanged, and so are~3 and~4.  Note that
it is possible for $\phi(i^2)=i^2$, as are the two copies of~5 in
Figure~\ref{fig:CSperm1}.

The idea of fixing set partition structure and interchanging labels
was described by Ross Drewe in sequence \seqnum{A047974} of the OEIS
\cite{OEIS}.  The difference between our context, and that of Drewe's,
is that our set label, namely the numbers, contain an extra parameter
of color.

Our goal is to describe a formula for $SS_n^2$, the number of
color-symmetrical permutations of $S_n^2$.  Our strategy is to divide
the $1\times 2n$ rectangle into two halves, each with $n$ squares.  We
fill the first half, or the leftmost $n$ squares, with an arbitrary
colored permutation of length $n$ derived from the elements of
$S^2_n$.  We then use reflective symmetry to complete the second half
of the $1\times 2n$ rectangle.  Since reflective symmetry \emph{must}
preserve the set partition structure, there are three types of numbers
that can occur in the first half of the $1\times 2n$ rectangle.  These
possibilities are the same possibilities the first author used to
calculate $H_{2m}$ in \cite{jq2}.  In particular,

\begin{itemize}
\item A number could map to a number that does \emph{not} occur in the
      first half.  
\item A number could map to itself under reflection.
\item A number could map to another number which also \emph{appears}
      in the first half.  If this happens, we say a 
      \textbf{\emph{first-half interchange}} (or simply FHI) occurs.   
\end{itemize}

\noindent
Figure~\ref{fig:CSperm2} illustrates these three cases for a
color-symmetric permutation of $S_5^2$.     

\begin{figure}[htb]
\begin{center}  \setlength{\unitlength}{0.85pt}
\begin{picture}(360,40)(-160,-10)
\put(-160,0){\makebox(160,20)[l]{Filling in the first half:}}
\multiput(0,0)(0,20){ 2}{\line(1,0){200}}
\multiput(0,0)(20,0){11}{\line(0,1){ 20}}
\put(100,-10){\line(0,1){40}}
\put( 0,0){\makebox(20,20){\bnum{5}}}
\put(20,0){\makebox(20,20){\rnum{1}}}
\put(40,0){\makebox(20,20){\bnum{2}}}
\put(60,0){\makebox(20,20){\bnum{1}}}
\put(80,0){\makebox(20,20){\rnum{3}}}
\end{picture}
\\ \ \\
\begin{picture}(360,30)(-160,0)
\put(-160,  5){\makebox(160,20)[l]{Vertical reflection, with}}
\put(-160,-10){\makebox(160,20)[l]{
  $1\leftrightarrow4$, $2\leftrightarrow3$, $5\leftrightarrow5$:}}
\multiput(0,0)(0,20){ 2}{\line(1,0){200}}
\multiput(0,0)(20,0){11}{\line(0,1){ 20}}
\put(100,-10){\line(0,1){40}}
\put(  0,0){\makebox(20,20){\bnum{5}}}
\put( 20,0){\makebox(20,20){\rnum{1}}}
\put( 40,0){\makebox(20,20){\bnum{2}}}
\put( 60,0){\makebox(20,20){\bnum{1}}}
\put( 80,0){\makebox(20,20){\rnum{3}}}
\put(100,0){\makebox(20,20){\rnum{2}}}
\put(120,0){\makebox(20,20){\rnum{4}}}
\put(140,0){\makebox(20,20){\bnum{3}}}
\put(160,0){\makebox(20,20){\bnum{4}}}
\put(180,0){\makebox(20,20){\rnum{5}}}
\end{picture}
\end{center}
\caption{Constructing a color-symmetrical permutation of $S_5^2$.}
\label{fig:CSperm2}
\end{figure}

Going through these three possibilities, we are able to derive a
formula that counts color-symmetrical permutations of $S_n^2$, as
follows. 

\begin{enumerate}
\item
Determine, in the first half, where the repetitions occur.  Under 
reflection, a repetition must map to a different repetition in the
second half.  We arbitrarily assign a color scheme to each repetition.
If $s$ is the number of repetitions that occur in the first $n$
squares, the number of ways to complete these $s$ double repetitions
in a color-symmetrical manner is
  \[ \frac{n!}{2^ss!(n-2s)!}\cdot\frac{n!2^{2s}}{(n-2s)!}. \]

\item
There are now $n-2s$ spaces in the first half that remain to be
filled.  We must fill these $n-2s$ spaces with a colored permutation
that does not have any repetitions.  The number of ways to do that is
$(n-2s)!2^{n-2s}$.

\item
Determine where the FHIs occur.  Notice that any numbers that do not
form a FHI pair must map to themselves.  Let $t$ be the number of FHI
pairs that occur among the $n-2s$ non-repeating positions in the first
$n$ slots.  The number of ways to place these $t$ FHI pairs is
$\frac{(n-2s)!}{2^tt!(n-2s-2t)!}$.
\end{enumerate}

\begin{lemma}
For $n\geq1$, 
  \[ SS_n^2 
  = \sum_{s=0}^{[\frac{n}{2}]} \sum_{t=0}^{[\frac{n-2s}{2}]}
    \frac{n!n!2^{n-s-t}}{s!t!(n-2s-2t)!}, \]
\end{lemma}

By standard convolution arguments, it is easy to show that 
  \begin{equation} \label{gen1}
  \sum_{n=0}^{\infty} SS_n^2 \frac{x^n}{(n!)^2} 
  = \sum_{n=0}^{\infty}\sum_{\scriptstyle{r,s,t\geq 0}\atop 
    \scriptstyle{r+2s+2t = n}}
    \frac{(2x^2)^s}{s!}\cdot\frac{(2x^2)^t}{t!}\cdot
    \frac{(2x)^r}{r!} 
  = e^{2x^2}\cdot e^{2x^2}\cdot e^{2x} 
  = e^{4x^2+2x}.
  \end{equation}
We can write the right hand side of Equation~(\ref{gen1}) as 
  \begin{equation} \label{cal1}
  e^{4x^2+2x} 
  = \sum_{k,j=0}^{\infty} \frac{(4x^2)^k}{k!}\cdot\frac{(2x)^j}{j!} 
  = \sum_{k,j=0}^{\infty} \frac{(2x)^{2k+j}}{k!j!} 
  = \sum_{j=0}^{\infty} \sum_{k=0}^{[\frac{j}{2}]}
    \frac{2^j}{k!(j-2k)!}\,x^j.
  \end{equation}
Comparing the coefficients in (\ref{gen1}) and (\ref{cal1}) yields the
next result.

\begin{lemma} \label{lem:2.2}
For $n\geq1$, 
  \begin{equation} \label{cor1}
  SS_n^2 
  = \sum_{k=0}^{[\frac{n}{2}]} \frac{n!n!2^n}{k!(n-2k)!} 
  = 2^nn!\sum_{k=0}^{[\frac{n}{2}]} {n\choose k} {n-k\choose k}k!. 
  \end{equation}
\end{lemma}

We should note that the right sum of Equation~(\ref{cor1}) is
reminiscent of $H_n(x)$, the Hermite polynomial of degree $n$, whose
explicit formula is \cite{ci}
  \begin{equation} \label{herm}
  H_n(x) 
  = \sum_{k=0}^{[\frac{n}{2}]} (-1)^k {n\choose k} {n-k\choose k}
    k!(2x)^{n-2k}. 
  \end{equation}
If we let $x = \frac{i}{2}$ in Equation~(\ref{herm}), we obtain
another representation for $SS_n^2$.

\begin{corollary}
For $n\geq1$, 
  \[ SS_n^2 = (-2i)^n n! H_n \left(\frac{i}{2}\right). \]
\end{corollary}

%%%%%%%%%%%
% Section 4
%%%%%%%%%%%

\section{Three Variations on $SS_n^2$}
\label{sec4}

When we defined the notion of a color-symmetrical permutation of
$S_n^2$, we only concerned ourselves with fixing the set partition
associated with the permutation.  The color scheme for each part of
the set partition was arbitrarily assigned, and hence played \emph{no}
role in determining whether a permutation of $S_n^2$ was
color-symmetric.  We now want to put restrictions on our color scheme.

The most natural restriction is to require colors to map to themselves
whenever possible.  Recall that for $S_n^2 = \{1^2, 2^2,\ldots,n^2\}$,
we have one red $i$ and one blue $i$ for each $i$.  The
aforementioned color restriction would require that if the set
partition structure maps $i$ to $j$, where $1\leq i < j\leq n$, we
\emph{also} require that a red $i$ maps to a red $j$, and hence, a
blue $i$ maps to a blue $j$.

Note that there is no color restriction on $i$ if the reflection maps
$i$ to itself.  One possibility for color restriction involves the
repetitions in the first half of the $1\times 2n$ rectangle, since
these repetitions have an arbitrarily assigned color scheme.
Figure~\ref{fig:CSperm3} illustrates how the color restriction (or
lack thereof) applies to a subset of color-symmetrical permutation of 
$S_3^2$ which has repetitions in the first half.

\begin{figure}[htb]
\begin{center}  \setlength{\unitlength}{0.85pt}
\def\colorperm#1#2#3#4#5#6{%
  \begin{picture}(120,20)(0,0)
  \multiput(0,0)(0,20){2}{\line(1,0){120}}
  \multiput(0,0)(20,0){7}{\line(0,1){ 20}}
  \put(  0,0){\makebox(20,20){#1}}
  \put( 20,0){\makebox(20,20){#2}}
  \put( 40,0){\makebox(20,20){#3}}
  \put( 60,0){\makebox(20,20){#4}}
  \put( 80,0){\makebox(20,20){#5}}
  \put(100,0){\makebox(20,20){#6}}  
  \end{picture}} 
\ \\ [12pt]
\colorperm{\rnum{1}}{\bnum{1}}{\rnum{3}}{\bnum{3}}{\rnum{2}}{\bnum{2}}\quad
\colorperm{\rnum{1}}{\bnum{1}}{\rnum{3}}{\bnum{3}}{\bnum{2}}{\rnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{1}}{\rnum{3}}{\bnum{3}}{\rnum{2}}{\bnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{1}}{\rnum{3}}{\bnum{3}}{\bnum{2}}{\rnum{2}}\\[12pt]
\colorperm{\rnum{1}}{\bnum{1}}{\bnum{3}}{\rnum{3}}{\rnum{2}}{\bnum{2}}\quad
\colorperm{\rnum{1}}{\bnum{1}}{\bnum{3}}{\rnum{3}}{\bnum{2}}{\rnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{1}}{\bnum{3}}{\rnum{3}}{\rnum{2}}{\bnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{1}}{\bnum{3}}{\rnum{3}}{\bnum{2}}{\rnum{2}}\\
No color restrictions \\ \ \\ 
\colorperm{\rnum{1}}{\bnum{1}}{\rnum{3}}{\bnum{3}}{\bnum{2}}{\rnum{2}}\quad
\colorperm{\rnum{1}}{\bnum{1}}{\bnum{3}}{\rnum{3}}{\bnum{2}}{\rnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{1}}{\rnum{3}}{\bnum{3}}{\rnum{2}}{\bnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{1}}{\bnum{3}}{\rnum{3}}{\rnum{2}}{\bnum{2}}\\
Color restricted 
\end{center}
\caption{Color-symmetrical permutations of $S_3^2$ with and without
  color restrictions.} 
\label{fig:CSperm3}
\end{figure}

The only change in the formula associated with Step~1 in
Section~\ref{sec3} is that the factor $2^{2s}$ in the numerator of the
second fraction becomes a $2^s$.  Note that Steps~2 and~3 stay the
same.  We find the following double sum formula for
$\widehat{SS}_n^2$, the number of color-symmetrical permutations of
$S_n^2$ whose double repetition blocks obey the color restriction.

\begin{lemma} \label{lem:2.3}
For $n\geq1$, 
  \[ \widehat{SS}_n^2 
  = \sum_{s=0}^{[\frac{n}{2}]} \sum_{t=0}^{[\frac{n-2s}{2}]}
    \frac{n!n!2^{n-2s-t}}{s!t!(n-2s-2t)!}. \]
\end{lemma}

Using standard convolution arguments, we can show that
  \[ \sum_{n=0}^{\infty} \widehat{SS}_n^2 \frac{x^n}{(n!)^2} 
  = e^{3x^2+2x}. \]
With the appropriate changes to the argument used to prove
Lemma~\ref{lem:2.2}, we can prove the following result.

\begin{lemma} \label{lem:2.4}
For $n\geq1$, 
  \[ \widehat{SS}_n^2 
  = \sum_{k=0}^{[\frac{n}{2}]} \frac{n!n!3^k2^n}{2^{2k}k!(n-2k)!} 
  = 2^nn!\sum_{k=0}^{[\frac{n}{2}]} {n\choose k} {n-k\choose k}
    \left(\frac{3}{4}\right)^k k!. \]
\end{lemma}

An alternative proof to Lemma~\ref{lem:2.4}, which could also prove
Lemma~\ref{lem:2.3}, is as follows.
  \begin{eqnarray*}
  \widehat{SS}_n^2 
  &=& \sum_{k=0}^{[\frac{n}{2}]} \frac{2^{n-k}(n!)^2}{(n-2k)!} 
      \sum_{\scriptstyle{s,t\geq 0}\atop \scriptstyle{s+t=k}}
      \frac{1}{s!t!2^s} \\
  &=& \sum_{k=0}^{[\frac{n}{2}]} \frac{2^{n-k}(n!)^2}{k!(n-2k)!}
      \sum_{s=0}^k{k\choose s} \frac{1}{2^s} \\
  &=& \sum_{k=0}^{[\frac{n}{2}]} \frac{2^{n-k}(n!)^2}{k!(n-2k)!}
      \left(\frac{3}{2}\right)^k \\
  &=& 2^n n! \sum_{k=0}^{[\frac{n}{2}]} {n\choose k} {n-k\choose k}
      \left(\frac{3}{4}\right)^k. 
  \end{eqnarray*}
We should also note that we can use the Hermite polynomial to
calculate $\widehat{SS}_n^2$. 

\begin{corollary}
For $n\geq1$, 
  \[ \widehat{SS}_n^2 
  = (-i\sqrt{3})^n n! H_n \left(\frac{i}{\sqrt{3}}\right). \]
\end{corollary}

The second way to place the color restriction is in a FHI pair.  This
is done in the following manner.  Let $1\leq i < j\leq n$.  Suppose
both $i$ and $j$ appear in the first $n$ slots.  Furthermore, suppose
vertical reflection maps $i$ to $j$.  If we determine which color of
$i$ occurs in the first $n$ slots, we have \emph{also} determined the
color scheme for $j$.  We demonstrate in Figure~\ref{fig:CSperm4} the
color restriction for those color-symmetrical permutations of $S_3^2$
which have a FHI.

\begin{figure}[htb]
\begin{center}  \setlength{\unitlength}{0.85pt}
\def\colorperm#1#2#3#4#5#6{%
  \begin{picture}(120,20)(0,0)
  \multiput(0,0)(0,20){2}{\line(1,0){120}}
  \multiput(0,0)(20,0){7}{\line(0,1){ 20}}
  \put(  0,0){\makebox(20,20){#1}}
  \put( 20,0){\makebox(20,20){#2}}
  \put( 40,0){\makebox(20,20){#3}}
  \put( 60,0){\makebox(20,20){#4}}
  \put( 80,0){\makebox(20,20){#5}}
  \put(100,0){\makebox(20,20){#6}}  
  \end{picture}} 
\ \\ [12pt]
\colorperm{\rnum{1}}{\rnum{2}}{\rnum{3}}{\bnum{3}}{\bnum{1}}{\bnum{2}}\quad
\colorperm{\rnum{1}}{\bnum{2}}{\rnum{3}}{\bnum{3}}{\bnum{1}}{\rnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{2}}{\rnum{3}}{\bnum{3}}{\rnum{1}}{\bnum{2}}\quad
\colorperm{\bnum{1}}{\bnum{2}}{\rnum{3}}{\bnum{3}}{\rnum{1}}{\rnum{2}}\\[12pt]
\colorperm{\rnum{1}}{\rnum{2}}{\bnum{3}}{\rnum{3}}{\bnum{1}}{\bnum{2}}\quad
\colorperm{\rnum{1}}{\bnum{2}}{\bnum{3}}{\rnum{3}}{\bnum{1}}{\rnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{2}}{\bnum{3}}{\rnum{3}}{\rnum{1}}{\bnum{2}}\quad
\colorperm{\bnum{1}}{\bnum{2}}{\bnum{3}}{\rnum{3}}{\rnum{1}}{\rnum{2}}\\
No color restrictions \\ \ \\ 
\colorperm{\rnum{1}}{\bnum{2}}{\rnum{3}}{\bnum{3}}{\bnum{1}}{\rnum{2}}\quad
\colorperm{\rnum{1}}{\bnum{2}}{\bnum{3}}{\rnum{3}}{\bnum{1}}{\rnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{2}}{\rnum{3}}{\bnum{3}}{\rnum{1}}{\bnum{2}}\quad
\colorperm{\bnum{1}}{\rnum{2}}{\bnum{3}}{\rnum{3}}{\rnum{1}}{\bnum{2}}\\
Color restricted 
\end{center}
\caption{Color-symmetrical permutations of $S_3^2$ with~1 and~2
  interchanged.} 
\label{fig:CSperm4}
\end{figure}

We construct an isomorphism between those color-symmetrical
permutations of $S_n^2$ with color restriction on the repetitions and
those with color restriction on the interchanges, as follows.  For
each pair of slots where a repetition occurs in the first half of the
permutation, switch the second colored number with its reflective
image.  This operation changes a repetition into a FHI.  This
procedure is reversible, that is, it maps a FHI to a repetition .  For
example, this isomorphism maps the first four permutations in
Figure~\ref{fig:CSperm3} to the first four permutations in
Figure~\ref{fig:CSperm4} (and vice versa).  If we let
$\widetilde{SS}_n^2$ be the number of color-symmetrical permutations
of $S_n^2$ whose FHIs obey the color restriction, the previous
reasoning leads to our next lemma.

\begin{lemma} \label{lem:2.5}
Let $\widetilde{SS}_n^2$ be as previously defined.  Then,
  \begin{equation} \label{2.11}
  \widetilde{SS}_n^2 
  = \widehat{SS}_n^2  
  = \sum_{s=0}^{[\frac{n}{2}]} \sum_{t=0}^{[\frac{n-2s}{2}]}
    \frac{n!n!2^{n-2s-t}}{s!t!(n-2s-2t)!}.
  \end{equation}
\end{lemma}

We could also derive Equation~(\ref{2.11}) by carefully analyzing how
we place the FHI pairs, and their associated color scheme, in the
first half of the permutation.  Details of this method are available
upon request from the authors.

For the third variation, we will place the color restriction on
\emph{both} the repetitions and the FHI pairs.  Combining the
techniques for the previous two variations, we obtain the following
result.

\begin{lemma} \label{lem:2.6}
Let $\dddot{SS}_n^2$ be the number of color-symmetrical permutations
of $S_n^2$ which have the color restriction on repetitions \emph{and}
the interchange pairs.  Then, 
  \[ \dddot{SS}_n^2 
  = \sum_{s=0}^{[\frac{n}{2}]} \sum_{t=0}^{[\frac{n-2s}{2}]}
    \frac{n!n!2^{n-2s-2t}}{s!t!(n-2s-2t)!}. \]
\end{lemma}

By applying standard convolution arguments, we find 
  \[ \sum_{n=0}^{\infty} \dddot{SS}_n^2 \frac{x^n}{(n!)^2} 
  = e^{2x^2+2x}. \]
The next result is obtained from an argument similar to that of
Lemma~\ref{lem:2.4}.

\begin{lemma} \label{lem:2.7}
For $n\geq1$, 
  \begin{equation} \label{dd2}
  \dddot{SS}_n^2 
  = \sum_{k=0}^{[\frac{n}{2}]} \frac{n!n!2^{n-k}}{k!(n-2k)!} 
  = 2^n n! \sum_{k=0}^{[\frac{n}{2}]} {n\choose k} {n-k\choose k}
    \left(\frac{1}{2}\right)^k k!. 
  \end{equation}
\end{lemma}

\begin{corollary}
For $n\geq1$, 
  \[ \dddot{SS}_n^2 
  = (-i\sqrt{2})^n n! H_n \left(\frac{i}{\sqrt{2}}\right). \]
\end{corollary}

We end this section with a table that records the values of $SS_n^2$,
$\widehat{SS}_n^2 = \widetilde{SS}_n^2$, and $\dddot{SS}_n^2$ for\\
$1\leq n\leq 8$.

\begin{table}[htb]
\begin{center}
\begin{tabular}{||l|c|c|c|c|c|c|c|c||} \hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline
$SS_n^2$ & 2 & 24 & 336 & 9600 & 311040 & 15252480 & 840591360 &
  61281239040\\ \hline
$\widehat{SS}_n^2$ & 2 & 20 & 264 & 6432 & 191040 & 8081280 &
  401990400 & 25439016960\\ \hline
$\dddot{SS}_n^2$ & 2 & 16 & 192 & 3840 & 99840 & 3502080 & 149667840 &
  7865946880\\ \hline
\end{tabular}
\end{center}
\caption{Values for $SS_n^2$, $\widehat{SS}_n^2 = \widetilde{SS}_n^2$,
  and $\dddot{SS}_n^2$.} 
\end{table} 

%%%%%%%%%%%
% Section 5
%%%%%%%%%%%

\section{Closing Remarks and Open Questions}

In this paper, we have discussed two classes of identities which are
readily proven using colored permutations and colored combinations.
The first such identity is, for $m\geq 2$, an $(m-1)$-fold sum for
${mn\choose n}$.  The second class of identities enumerates the
color-symmetrical permutations of the 2-colored multiset $S_n^2$.  It
is natural to ask for a generalization in $S_n^m$.  Currently, the
authors are working on the cases of $m=3$ and $m=4$.  There are two
basic differences between the $m=2$ situation and the $m=3$ case.
When $m=3$, no number can be mapped to itself under vertical
reflection.  Also, one must analyze the case of even $n$ separately
from odd $n$.

Another possible topic for future research involves arranging the
colored permutations of $S_n^m$ into an $m\times n$ rectangular grid,
and then using a symmetry operation of the $m\times n$ rectangle to
enumerate those colored permutations whose set partition structure is
fixed with respect to this symmetry operation.  Such an enumeration
will rely on the techniques the first author used to count the
symmetrical inequivalent $m\times n\times p$ letter representations
\cite{jq2}.

Instead of using the colored multiset $S_n^m$, we could relate the
problems to the set $[mn]=\{1,2,\ldots,mn\}$ by matching the integer
$i$ colored $k$ from $S_n^m$ with the integer $(i-1)m+k$ from $[mn]$.
Essentially we are grouping the integers from $S_n^m$ according to
their values, and within the same value, lining up the integers
according to their colors.

Of course, we can also match the integer $i$ colored $k$ from $S_n^m$
with the integer $(k-1)n+i$ from $[mn]$.  This time, all the integers
of the same color are grouped together, and within the same color,
the integers are lined up in ascending order.  

These two correspondences could lead to other questions.  For
instance, the symmetry in the permutations can be defined according to
certain number-theoretic properties.  These symmetries may be rather
different from what we have discussed above.  The options are
plentiful, and we invite the readers to explore them.

\section{Acknowledgment}

The authors would like to thank the anonymous referee for the
suggestions that have improved the exposition in this paper. 


\begin{thebibliography}{9}
\bibitem{ci} 
H. W. Gould, {\it Combinatorial Identities}, Revised Edition,
Morgantown, WV, 1972.

\bibitem{df} 
H. W. Gould and J. Quaintance,  Double fun with double
factorials, preprint, April 2009.

\bibitem{OEIS} 
N. J. Sloane, {\it Online Encyclopedia of Integer Sequences}, \\
\href{http://www.research.att.com/njas/sequence}{\tt http://www.research.att.com/njas/sequences/}.

\bibitem{jq1} 
J. Quaintance, Combinatoric enumeration of two-dimensional proper
arrays, {\it Discrete Math.} {\bf 307} (2007), 1844--1864.

\bibitem{jq2}  
J. Quaintance, Letter representations of  $m \times  n \times p$
proper arrays, {\it Australas.\ J.\ Combin.} {\bf 38} (2007),
289--308.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A15, 05A19, 33C45.

\noindent \emph{Keywords: } permutations, combinations, colored
multisets, Hermite polynomials.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A047974}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 22 2009;
revised versions received  July 3 2009; November 9 2009; December 21 2009; February 18 2010.
Published in {\it Journal of Integer Sequences}, February 18 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}