\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} & = \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} & = \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) & = \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) & = \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) & = \frac{G_{k}(s-t,t) + G_{k}(s+t,t)}{2s} , \\ G^{\pm}_{k+1}(s,t) & = \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) & = \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) & = \prod_{\substack{i = -k \\ i \equiv k \ ({\rm mod}\ 2)}}^{k} (s - i \cdot t)^{-1} , \label{equation_G} \\ G^{\pm}_{k}(s,t) & = (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} & = \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} & = (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} & = \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} & = \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} & = \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} & = \begin{cases} h_{\frac{n-k}{2}}(2^{2}, 4^{2}, \ldots, k^{2}), & \:\:\:\: \text{$k$ even;} \\ h_{\frac{n-k}{2}}(1^{2}, 3^{2}, \ldots, k^{2}), & \:\:\:\: \text{$k$ odd,} \end{cases}\\ U_{n,k} & = (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}