<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

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

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\RG}{RG}
\newcommand{\ORG}{RG^{\text{\rm odd}}}
\newcommand{\ERG}{RG^{\text{\rm even}}}

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


\begin{center}
\vskip 1cm{\LARGE\bf
A Restricted Growth Word Approach to Partitions with Odd/Even Size Blocks \\
\vskip .1in } \vskip 1cm \large
Richard Ehrenborg, Dustin Hedmark, and Cyrus Hettle \\
Department of Mathematics \\
University of Kentucky \\
Lexington, KY 40506-0027 \\
USA \\
\href{mailto:richard.ehrenborg@uky.edu}{\tt richard.ehrenborg@uky.edu} \\
\href{mailto:dustin.hedmarky@uky.edu}{\tt dustin.hedmark@uky.edu} \\
\href{mailto:cyrus.h@uky.edu}{\tt cyrus.h@uky.edu} \\
\end{center}

\vskip .2 in


\begin{abstract} 
We use restricted growth words and multivariate generating functionology
to obtain the ordinary generating
function for the number of partitions of an $n$-set into $k$~blocks
of odd (respectively, even) cardinality.
\end{abstract}



\section{Introduction}
The Stirling numbers of the second kind $S(n,k)$
enumerate the partitions of
the set $[n] = \{1,2, \ldots, n\}$ into $k$ blocks.
They satisfy the ordinary generating function identity
\begin{equation}
\sum_{n \geq k} S(n,k) \cdot t^{n-k}
   =
\frac{1}
{(1-t) \cdot (1 - 2 t) \cdots (1 - k t)} .
\label{equation_ordinary_generating_function}
\end{equation}
Recall that the complete symmetric function
$h_{m}(x_{1}, x_{2}, \ldots, x_{k})$
satisfies the generating function identity
$$  
\sum_{m \geq 0} 
h_{m}(x_{1}, x_{2}, \ldots, x_{k}) \cdot t^{m}
   =
\frac{1}
{(1-x_{1}t) \cdot (1 - x_{2} t) \cdots (1 - x_{k} t)} .
$$
The expression
$S(n,k) = h_{n-k}(1, 2, \ldots, k)$
for the Stirling numbers of the second kind follows directly.
For a reference on Stirling numbers,
see~\cite[Section~1.9]{Stanley_EC_1}.

Let $T_{n,k}$ and $U_{n,k}$
denote the number of set partitions
of the set $[n]$ into $k$ blocks where
each block has odd  (respectively, even) cardinality.
These numbers have been
well-studied in the literature.
The classical approach is via their
exponential generating functions
$\sinh(t)^{k}/k!$ and $(\cosh(t)-1)^{k}/k!$ or via a more bijective
route; see~\cite{Carlitz,Renyi} and \cite{Bruno_Rota_Torney}, respectively.
We study the ordinary generating functions
of these numbers using restricted growth words
and multivariate generating functions.

In this paper we use
the natural bijection between partitions
and restricted growth words.
Our first step is to
generalize~\eqref{equation_ordinary_generating_function}
to a multivariate generating function.
Next, by picking up
the terms where all the powers are
even/odd, we obtain expressions
for the ordinary generating function of
partitions with each block size being odd
(respectively, even).
By viewing these expressions as sums over walks on
the integers,
we give explicit product expressions for them.
Here we use homogeneous bivariate generating functions,
making the proofs
of the essential identities straightforward.
We end with a few open questions.


\section{Restricted growth words}

A {\em restricted growth word}, 
which we abbreviate as $\RG$-word,
is a word $u = u_{1} u_{2} \cdots u_{n}$
with the entries in the positive integers
such that $u_{j} \leq \max(0, u_{1}, u_{2}, \ldots, u_{j-1}) + 1$
for all $1 \leq j \leq n$. Let $\RG(n,k)$ denote
the set of all $\RG$-words of length~$n$ with
largest entry~$k$. The set $\RG(n,k)$ is in bijection
with the set partitions of the set $\{1,2, \ldots, n\}$
into $k$ blocks. Namely, given an $\RG$-word 
$u_{1} u_{2} \cdots u_{n}$,
construct a partition by letting elements $i$ and $j$
be in the same block if $u_{i} = u_{j}$.
Hence the cardinality of
$\RG(n,k)$ is given by
the Stirling number of the second kind $S(n,k)$.
The notion of $RG$-words was introduced
by Milne;
see~\cite{Milne_restricted,Milne_q_analog,Milne_restricted_rank_row}.
More recently, they appear in the 
papers~\cite{Cai_Ehrenborg_Readdy,Cai_Readdy}.




For an $\RG$-word $u = u_{1} u_{2} \cdots u_{n}$ in $\RG(n,k)$,
let $x_{u}$ be the monomial $x_{1}^{c_{1}}\cdots x_{k}^{c_{k}}$, where for all~$i$, $c_{i}$ is one less than the number
of times the letter $i$ appears in $u$.
Note that the monomial~$x_{u}$
has total degree $n-k$.
We begin by generalizing
equation~\eqref{equation_ordinary_generating_function}
to a multivariate version.
\begin{theorem}
For a non-negative integer $k$ the sum of the monomial of an $\RG$-word
over all $\RG$-words with largest entry $k$ is given by
$$
\sum_{n \geq k}\, \sum_{u \in \RG(n,k)} x_{u} 
   =
\frac{1}
{(1-x_{1}) \cdot (1-x_{1}-x_{2}) \cdots (1-x_{1}-x_{2}- \cdots - x_{k})} .
$$
\label{theorem_one}
\end{theorem}
\begin{proof}
Every $\RG$-word $u$ has a unique factorization
$u = 1 \cdot w_{1} \cdot 2 \cdot w_{2} \cdots k \cdot w_{k}$,
where $w_{i}$ is a word with entries $1$ through $i$.
For any word $w$, let $x(w)$ be the monomial
where the power of $x_{i}$ is the number of times
$i$ appears in $w$. Note that
$x_{u}$ is given by the product
$x(w_{1}) \cdot x(w_{2}) \cdots x(w_{k})$.
The result now follows by
the sum
\[
\sum_{w_{i}} x(w_{i})
=
\frac{1}{1-x_{1}-x_{2}- \cdots - x_{i}} , 
\]
where $w_{i}$ ranges over all words with entries
$1$ through $i$.
\end{proof}
Note that by setting $x_{i} = q^{i-1} \cdot t$ we obtain
a $q$-analogue of
equation~\eqref{equation_ordinary_generating_function}
which is 
due to Gould~\cite{Gould};
see also \cite[Thm.~4.1]{Cai_Ehrenborg_Readdy}.

Let $\ORG(n,k)$ denote the set of $\RG$-words $u$
in which each letter occurs an odd number of times
and let $\ERG(n,k)$ denote the set of $\RG$-words $u$
in where each letter occurs an even number of times.
By the bijection between $\RG$-words and partitions
we have that
$|\ORG(n,k)| = T_{n,k}$
and
$|\ERG(n,k)| = U_{n,k}$.

\begin{theorem}
The multivariate generating functions for 
$\ORG(n,k)$ and $\ERG(n,k)$
are given by
\begin{align}
\sum_{n \geq k}\, \sum_{u \in \ORG(n,k)} x_{u} 
&amp; =
\frac{1}{2^{k}}
\cdot
\sum_{\vec{c}}
F(c_{1} x_{1}, c_{2} x_{2}, \ldots, c_{k} x_{k}) , 
\label{equation_ORG} \\
\sum_{n \geq k}\, \sum_{u \in \ERG(n,k)} x_{u} 
&amp; =
\frac{1}{2^{k}}
\cdot
\sum_{\vec{c}}
c_{1} \cdot c_{2} \cdots c_{k} \cdot
F(c_{1} x_{1}, c_{2} x_{2}, \ldots, c_{k} x_{k}),
\label{equation_ERG}
\end{align}
where the sums
are over all vectors
$\vec{c} = (c_{1}, c_{2}, \ldots, c_{k}) \in \{-1,1\}^{k}$
and
$F(x_{1}, x_{2}, \ldots, x_{k})$
is the generating function in
Theorem~\ref{theorem_one}.
\label{theorem_two}
\end{theorem}
\begin{proof}
This result follows from the fact that the $\RG$-words
in $\ORG(n,k)$ have monomials with all even powers,
and the words in $\ERG(n,k)$ have monomials with all odd powers.
All monomials containing odd powers are eliminated in the first sum and all monomials containing even powers are eliminated in the second sum. 
\end{proof}

\section{Generating functions}

Let $W_{k}(a)$ be the set of all walks 
of length $k$ starting at $a$ taking
steps either $-1$ or $1$.
That is,
$W_{k}(a) = 
\{(a_{0},a_{1}, \ldots, a_{k}) \in \mathbb{Z}^{k+1}
\: : \:
a_{0} = a, \: a_{i} - a_{i-1} \in \{-1,1\}\}$.
Define the rational generating functions $G_{k}(s,t)$
and $G^{\pm}_{k}(s,t)$
over the set of walks starting at $0$
of length~$k$
by the sums
\begin{align*}
G_{k}(s,t) 
&amp; =
\frac{1}{2^{k}}
\cdot
\sum_{\vec{a} \in W_{k}(0)}
\frac{1}
{(s - a_{0} t) \cdot (s - a_{1} t) \cdots (s - a_{k} t)}  , \\
G^{\pm}_{k}(s,t) 
&amp; =
\frac{1}{2^{k}}
\cdot
\sum_{\vec{a} \in W_{k}(0)}
\frac{(-1)^{(k-a_{k})/2}}
{(s - a_{0} t) \cdot (s - a_{1} t) \cdots (s - a_{k} t)}  .
\end{align*}
\begin{proposition}
The generating functions $G_{k}(s,t)$ and $G^{\pm}_{k}(s,t)$
satisfy the recursions
\begin{align*}
G_{k+1}(s,t)
&amp; =
\frac{G_{k}(s-t,t) + G_{k}(s+t,t)}{2s} ,
\\
G^{\pm}_{k+1}(s,t)
&amp; =
\frac{G^{\pm}_{k}(s-t,t) - G^{\pm}_{k}(s+t,t)}{2s} ,
\end{align*}
with the initial condition $G_{0}(s,t) = G^{\pm}_{0}(s,t) = 1/s$.
\end{proposition}
\begin{proof}
Observe that the substitution $s \longmapsto s - j \cdot t$ translates
the sequence $(a_{0}, a_{1}, \ldots, a_{k})$ $j$ steps up, that is,
\begin{align*}
G_{k}(s - j \cdot t,t) 
&amp; =
\frac{1}{2^{k}}
\cdot
\sum_{\vec{a} \in W_{k}(j)}
\frac{1}
{(s - a_{0} t) \cdot (s - a_{1} t) \cdots (s - a_{k} t)}  \ .
\end{align*}
By taking the average of
$G_{k}(s - t,t)$ and $G_{k}(s + t,t)$,
we obtain the average over all walks
beginning at $\pm 1$.
Divide by $s$, since each term of $G_{k+1}(s,t)$ contains a factor of $1/s$,
and use that
the set $W_{k+1}(0)$ is given by
the Cartesian product
$\{(0)\} \times (W_{k}(1) \cup W_{k}(-1))$.
The first recursion follows.
The same proof applies to $G^{\pm}_{k}(s,t)$ by considering
the difference 
$G^{\pm}_{k}(s - t,t) - G^{\pm}_{k}(s + t,t)$.
\end{proof}

\begin{proposition}
The generating functions
$G_{k}(s,t)$
and
$G^{\pm}_{k}(s,t)$
are given by the products
\begin{align}
G_{k}(s,t)
&amp; =
\prod_{\substack{i = -k \\ i \equiv k \ ({\rm mod}\ 2)}}^{k}
(s - i \cdot t)^{-1}  , 
\label{equation_G} \\
G^{\pm}_{k}(s,t)
&amp; =
(2k-1)!! \cdot t^{k} \cdot
\prod_{i = -k}^{k}
(s - i \cdot t)^{-1}  .
\label{equation_G_pm}
\end{align}
\label{proposition_four}
\end{proposition}
\begin{proof}
Let $g_{k}(s,t)$ be the right-hand side of equation~\eqref{equation_G}.
We would like to prove
that $G_{k}(s,t)$ and $g_{k}(s,t)$ are equal.
Observe first that
$G_{0}(s,t) = 1/s = g_{0}(s,t)$.
Next observe that
$$
\frac{1}{(s - (k+1) t)}
+
\frac{1}{(s + (k+1) t)}
=
\frac{2 s}{(s - (k+1) t) (s + (k+1) t)} .
$$
Multiply both sides by $g_{k-1}(s,t)$, yielding
$g_{k}(s-t,t) + g_{k}(s+t,t) = 2 \cdot s \cdot g_{k+1}(s,t)$.
This shows that $g_{k}(s,t)$ satisfies the same
recurrence relations as
$G_{k}(s,t)$.

Let $g^{\pm}_{k}(s,t)$ be the right-hand side
of equation~\eqref{equation_G_pm}. We have that
$G^{\pm}_{0}(s,t) = 1/s = g^{\pm}_{0}(s,t)$.
Now consider the difference
$$
\frac{1}{(s - (k+1) t) (s - k t)}
-
\frac{1}{(s + (k+1) t) (s + k t)}
=
\frac{2 s \cdot (2 k + 1) t}
{(s - (k+1) t) (s - k t) (s + k t) (s + (k+1) t)} .
$$
Multiply both sides by
$(2k-1)!! \cdot t^{k} \cdot
\prod_{i = -k+1}^{k-1} (s - i \cdot t)^{-1}$.
This yields the recursion
$$g^{\pm}_{k}(s-t,t) - g^{\pm}_{k}(s+t,t) =
2 \cdot s \cdot g^{\pm}_{k+1}(s,t) .$$
\end{proof}


Combining these results yields the following generating functions.
\begin{theorem}
For a non-negative integer $k$ the ordinary generating
function for the number of $\RG$-words where
each entry occurs an odd or
 even number of times is
$G_{k}(1,t)$ or $G_{k}^{\pm}(1,t)$, respectively,
that is,
\begin{align*}
\sum_{n \geq k} T_{n,k} \cdot t^{n-k}  
&amp; =
\prod_{\substack{i = -k \\ i \equiv k \ ({\rm mod}\ 2)}}^{k}
(1 - i \cdot t)^{-1} , \\
\sum_{n\geq k} U_{n,k} \cdot t^{n-k}  
&amp; =
(2k-1)!! \cdot t^{k} \cdot
\prod_{i = -k}^{k}
(1 - i \cdot t)^{-1}  \ .
\end{align*}
\label{theorem_generating_function_for_T_and_U}
\end{theorem}
\begin{proof}
In Theorem~\ref{theorem_two}, set
$x_{1} = \cdots = x_{k} = t$.
Note that the monomial $x_{u}$ becomes $t^{n-k}$
and the left-hand side
of~\eqref{equation_ORG}
and~\eqref{equation_ERG}
becomes the generating
function for the cardinality of $\ORG(n,k)$,
(respectively, $\ERG(n,k)$).
Next, under this substitution
the term on the right-hand side
corresponding to the
$\{-1,1\}$-vector $\vec{c}$
becomes the term corresponding to
the walk $\vec{a}$ satisfying $a_{i} - a_{i-1} = c_{i}$
in the function $G_{k}(1,t)$
(respectively, $G^{\pm}_{k}(1,t)$).
In the signed case we use that
the sign $c_{1} \cdots c_{k}$ is given by
$(-1)^{(k-a_{k})/2}$.
Finally, the result follows by
Proposition~\ref{proposition_four}.
\end{proof}

When $k$ is even the generating function for $T_{n,k}$ is given by
\begin{align*}
\sum_{n \geq k} T_{n,k} \cdot t^{n-k}  
&amp; = 
\frac{1}
{
(1 - 2^{2} \cdot t^{2})
\cdot
(1 - 4^{2} \cdot t^{2})
\cdots
(1 - k^{2} \cdot t^{2})
}  . \\
\intertext{Similarly, for $k$ odd we have}
\sum_{n \geq k} T_{n,k} \cdot t^{n-k}  
&amp; = 
\frac{1}
{
(1 - 1^{2} \cdot t^{2})
\cdot
(1 - 3^{2} \cdot t^{2})
\cdots
(1 - k^{2} \cdot t^{2})
}  . \\
\intertext{The generating function for $U_{n,k}$ is given by}
\sum_{n \geq k} U_{n,k} \cdot t^{n-k}  
&amp; = 
\frac{(2k-1)!! \cdot t^{k}}
{
(1 - 1^{2} \cdot t^{2})
\cdot
(1 - 2^{2} \cdot t^{2})
\cdots
(1 - k^{2} \cdot t^{2})
} .
\end{align*}
We now obtain the following expressions in terms of the complete symmetric function.
\begin{corollary}
The number of $\RG$-words with odd (respectively, even) number of each entry
is given by
\begin{align*}
T_{n,k}
&amp; = \begin{cases}
h_{\frac{n-k}{2}}(2^{2}, 4^{2}, \ldots, k^{2}),   &amp; \:\:\:\: \text{$k$ even;} \\
h_{\frac{n-k}{2}}(1^{2}, 3^{2}, \ldots, k^{2}),   &amp; \:\:\:\: \text{$k$ odd,}
\end{cases}\\
U_{n,k}
&amp; =
(2k-1)!!
\cdot
h_{\frac{n}{2}-k}(1^{2}, 2^{2}, \ldots, k^{2})   .
\end{align*}
\label{corollary_h}
\end{corollary}
Using the recurrence
$h_{m}(x_{1},\ldots,x_{k})
=
x_{k} \cdot h_{m-1}(x_{1},\ldots,x_{k})
+
h_{m}(x_{1},\ldots,x_{k-1})$,
this corollary yields the classical recurrences for $T_{n,k}$ and $U_{n,k}$.



\section{Concluding remarks}


Is there a bijective proof of Corollary~\ref{corollary_h}?
Is there a multivariate refinement of
Theorem~\ref{theorem_generating_function_for_T_and_U}?
For instance, is there a $q$-analogue of this theorem?

For more on the poset and topological structure
of partitions with all blocks odd/even,
see~\cite{Calderbank_Hanlon_Robinson,
Stanley_exponential_structures,Wachs}.



\section{Acknowledgments}

The authors thank G\'abor Hetyei for his help with
finding and reading reference~\cite{Renyi}.
The authors also thank Andrew Klapper, Margaret Readdy,
and the referee
for their comments on an earlier draft.
This work was supported by a grant from the Simons Foundation
(\#429370, Richard~Ehrenborg).





\newcommand{\journal}[6]{#1, #2, {\it #3} {\bf #4} (#5), #6.}
\newcommand{\book}[4]{#1, {\it #2,} #3, #4.}
\newcommand{\collection}[6]{#1,  #2, #3, in {\it #4}, #5, #6.}
\newcommand{\preprint}[3]{{#1,} #2, preprint #3.}



\begin{thebibliography}{99}

\bibitem{Bruno_Rota_Torney}
\journal{W.\ Bruno, G.-C.\ Rota, and D.\ C.\ Torney}
            {Probability set functions}
            {Ann.\ Comb.}
            {3}{1999}{13--25}

\bibitem{Cai_Ehrenborg_Readdy}
\preprint{Y.\ Cai, R.\ Ehrenborg, and M.\ Readdy}
             {$q$-Stirling identities revisited}
             {2016}

\bibitem{Cai_Readdy}
\journal{Y.\ Cai and M.\ Readdy}
            {$q$-Stirling numbers: a new view}
            {Adv.\ in Appl.\ Math.}
            {86}{2017}{50--80}

\bibitem{Calderbank_Hanlon_Robinson}
\journal{A.\ R.\ Calderbank, P.\ Hanlon, and R.\ W.\ Robinson}
        {Partitions into even and odd block size and
         some unusual characters of the symmetric groups}
        {Proc.\ London Math.\ Soc.\ (3)}
        {53}{1986}{288--320}

\bibitem{Carlitz}
\journal{L.\ Carlitz}
            {Set partitions}
            {Fibonacci Quart.}
            {14}{1976}{327--342}

\bibitem{Gould}
\journal{H.\ W.\ Gould}
        {The $q$-Stirling numbers of the first and second kinds}
        {Duke Math.\ J.}
        {28}{1961}{281--289}

\bibitem{Milne_restricted}
\journal{S.\ Milne}
        {Restricted growth functions
         and incidence relations of the lattice of partitions
         of an $n$-set}
        {Adv.\ Math.}
        {26}{1977}{290--305}

\bibitem{Milne_q_analog}
\journal{S.\ Milne}
        {A $q$-analog of restricted growth functions, Dobinski's equality, and Charlier polynomials}
        {Trans.\ Amer.\ Math.\ Soc.}
        {245}{1978}{89--118}

\bibitem{Milne_restricted_rank_row}
\journal{S.\ Milne}
        {Restricted growth functions, rank row matchings
         of partition lattices, and $q$-Stirling numbers}
        {Adv.\ in Math}
        {43}{1982}{173--196}

\bibitem{Renyi}
\journal{A.\ R\'enyi}
            {\'Uj m\'odszerek \'es eredm\'enyek a kombinatorikus anal\'{\i}zisben, I.}
            {Magyar Tudom\'anyos Akad\'emia III.
            Oszt\'aly K\"ozlem\'enyei}
            {16}{1966}{77--105} Available at \\
	    \url{http://real-j.mtak.hu/499/1/MATFIZ_16.pdf}.

\bibitem{Stanley_exponential_structures}
\journal{R.\ P.\ Stanley}
            {Exponential structures}
            {Studies Appl. Math}
            {59}{1978}{73--82}

\bibitem{Stanley_EC_1}
R. P. Stanley,
\newblock {\it Enumerative Combinatorics}, Vol.~1, second edition.
\newblock Cambridge University Press, 2012.

\bibitem{Wachs}
\journal{M.\ L.\ Wachs}
        {A basis for the homology of the $d$-divisible partition lattice}
        {Adv.\ Math.}
        {117}{1996}{294--318}

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A18;
Secondary 05A15.

\noindent \emph{Keywords:} set partition, restricted growth word, 
multivariate generating function.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A136630}
and
\seqnum{A156289}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 9 2016;
revised version received April 29 2017.
Published in {\it Journal of Integer Sequences}, April 30 2017.

\bigskip
\hrule
\bigskip

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

\end{document}

</pre></body></html>