\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \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{amsmath,amssymb,amsthm} \usepackage{amsfonts,latexsym} \usepackage{epsf} \usepackage{hyperref} \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}}} %\topmargin 0 pt \textheight 46\baselineskip \advance\textheight by %\topskip \setlength{\parindent}{0pt} \setlength{\parskip}{5pt plus %2pt minus 1pt} \setlength{\textwidth}{155mm} %\setlength{\oddsidemargin}{5.6mm} %\setlength{\evensidemargin}{5.6mm} %\usepackage{epic} %\usepackage{eepic} %\usepackage[bolddef,boldvec]{niklas} \theoremstyle{remark} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{remark}[theorem]{Remark} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{definition}{Definition}[section] \newtheorem{example}{Example}[section] \newtheorem{corollary}[theorem]{Corollary} \newtheorem{problem}[theorem]{Problem} \newcommand{\fix} {\ensuremath{\mathrm{fix}}} \newcommand{\expn}{\mathrm{exp}_{n}} %%\textwidth 146 mm %%\textheight 230 mm %%\oddsidemargin 7mm \evensidemargin -1mm \topmargin -4mm \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Counting Peaks and Valleys in a \\ \vskip .1in Partition of a Set} \vskip 1cm \large Toufik Mansour\\ Department of Mathematics\\ University of Haifa\\ 31905 Haifa \\ Israel\\ \href{mailto:toufik@math.haifa.ac.il}{\tt toufik@math.haifa.ac.il}\\ \ \\ Mark Shattuck\\ Department of Mathematics\\ University of Tennessee\\ Knoxville, TN 37996\\ USA \\ \href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu}\\ \end{center} \vskip .1 in \begin{abstract} A \emph{partition} $\pi$ of the set $[n]=\{1,2,\ldots,n\}$ is a collection $\{B_1,B_2,\ldots ,B_k\}$ of nonempty disjoint subsets of $[n]$ (called \emph{blocks}) whose union equals $[n]$. In this paper, we find an explicit formula for the generating function for the number of partitions of $[n]$ with exactly $k$ blocks according to the number of peaks (valleys) in terms of Chebyshev polynomials of the second kind. Furthermore, we calculate explicit formulas for the total number of peaks and valleys in all the partitions of $[n]$ with exactly $k$ blocks, providing both algebraic and combinatorial proofs. \end{abstract} %----------------------------------------------------------- \section{Introduction} A \emph{partition} $\Pi $ of the set $[n]=\{1,2,\ldots ,n\}$ is a collection $\{B_{1},B_{2},\ldots ,B_{k}\}$ of nonempty disjoint subsets of $[n]$, called \emph{blocks}, whose union equals $[n]$. We assume that blocks are listed in increasing order of their minimal elements, that is, $\min B_{1}<\min B_{2}<\cdots <\min B_{k}$. The set of all partitions of $[n]$ with $k$ blocks is denoted by $P(n,k)$. The cardinality of $P(n,k)$ is the well-known Stirling number of the second kind \cite{S1}, which is usually denoted by $S_{n,k}$. Any partition $\Pi $ can be written in the \emph{canonical sequential form} $\pi_1\pi_2\cdots\pi_n$, where $i\in B_{\pi_i}$ for all $i$ (see, e.g., \cite{K1}). Throughout, we will identify each partition with its canonical sequential form. For example, if $\Pi =\{1,4\},\{2,5,7\},\{3\},\{6\}$ is a partition of $[7]$, then its canonical sequential form is $\pi=1231242$ and in such a case we write $\Pi=\pi$. Several authors have studied different subword patterns on the set of partitions of $[n]$. For example, Mansour and Munagi \cite{MM} studied the number of partitions of $[n]$ according to the number levels, rises, and descents. Recall that a {\em level} (respectively, {\em rise}, {\em descent}) of a word $\pi=\pi_1\pi_2\cdots\pi_n$ is an index $i$ such that $\pi_i=\pi_{i+1}$ (respectively, $\pi_i<\pi_{i+1}$, $\pi_i>\pi_{i+1}$). A general question concerns counting the elements in a subset of $P(n,k)$ which have no occurrences of a particular pattern. On this subject, the reader is referred to the works of Sagan \cite{SA}, Mansour and Severini \cite{MS}, Chen\emph{\ et al.} \cite{C2}, and Jel\'inek and Mansour \cite{JM}, as well as to the references therein. Let $[k]^n$ denote the set of all words of length $n$ over the alphabet $[k]$. Given $\pi=\pi_1\pi_2\cdots\pi_n \in [k]^n$, a {\em peak} (respectively, {\em valley}) is an entry $\pi_j$, $1\leq j\leq n-2$, of $\pi$ such that $\pi_{j}<\pi_{j+1}>\pi_{j+2}$ (respectively, $\pi_{j}>\pi_{j+1}<\pi_{j+2}$); that is, a peak is a rise followed immediately by a descent and a valley is a descent followed immediately by a rise. In this case, we say that a peak or valley \emph{occurs at j} in $\pi$. We denote the number of peaks (respectively, valleys) in $\pi$ by $peak(\pi)$ (respectively, $valley(\pi)$). That there are $2^{n-1}$ permutations of $[n]$ without peaks (valleys) was shown \cite{Ki1} and later extended \cite{Ki2} by Kitaev. Comparable results on words are given by Heubach and Mansour \cite{HM1}, where they find an explicit formula for the generating function for the number of elements of $[k]^n$ according to the number of peaks (valleys) (see \cite{HMbook} for further results). See also the paper by Mansour \cite{M} for analogous results on Dyck paths. The aim of this paper is to find an explicit formula for the generating function for the number of partitions of $[n]$ with exactly $k$ blocks, expressed canonically, according to the number of peaks (valleys), where $k$ is fixed. The case of peaks (respectively, valleys) is treated in Section 2 (respectively, Section 3). Our main approach is to first compute the generating functions for the number of peaks (or valleys) for words over $[k]$ of length $n$ and then relate this to the corresponding generating functions for partitions of $[n]$ with exactly $k$ blocks via the restricted growth function of the partition. All the explicit solutions obtained in Sections 2 and 3 involve Chebyshev polynomials of the second kind, see \cite{Ri}. We also derive explicit formulas for the total number of peaks and valleys in all the partitions of $[n]$ with exactly $k$ blocks, providing both algebraic and combinatorial proofs. \section{Counting peaks} Let $W_k(x,q)$ be the generating function for the number of words of length $n$ over the alphabet $[k]$ according to the number of peaks, that is, $$W_k(x,q)=\sum_{n\geq0}\left(x^n\sum_{\pi\in[k]^n}q^{peak(\pi)}\right).$$ \begin{lemma}\label{lem1} The generating function $W_k(x,q)$ satisfies the recurrence relation $$W_k(x,q)=\frac{x(q-1)+(1-x(q-1))W_{k-1}(x,q)}{1-x(1-q)(1-x)-x(x+q(1-x))W_{k-1}(x,q)},$$ with the initial condition $W_0(x,q)=1$. \end{lemma} \begin{proof} Let us write an equation for $W_k(x,q)$. Since each word in $[k]^n$ may or may not contain the letter $k$, we have $$W_k(x,q)=W_{k-1}(x,q)+W_k^*(x,q),$$ where $W_k^*(x,q)$ is the generating function for the number of words $\pi$ of length $n$ over the alphabet $[k]$ according to the number of peaks such that $\pi$ contains the letter $k$. Such words $\pi$ may be decomposed as either $k$, $\pi'k$, $k\pi''$, $\pi'k\pi'''$, or $\pi'kk\pi''''$, where $\pi'$ is a nonempty word over the alphabet $[k-1]$, $\pi''$ is a nonempty word over the alphabet $[k]$, $\pi'''$ is a nonempty word over the alphabet $[k]$ which starts with a letter $aFrom the fact that each partition $\pi$ of $[n]$ with exactly $k$ blocks may be expressed uniquely as $\pi=1\pi^{(1)}2\pi^{(2)}\cdots k\pi^{(k)}$ such that $\pi^{(j)}$ is a word over the alphabet $[j]$, it follows that the generating function $VP_k(x,q)$ is given by \begin{equation}\label{eqb40} VP_k(x,q)=x^kV_k(x,q)\prod_{j=1}^{k-1}W'_j(x,q), \end{equation} where $V_k(x,q)$ is the generating function for the number of words $\pi$ over the alphabet $[k]$ according to the number of valleys in $k\pi$. \begin{lemma}\label{lemb4} For all $k\geq1$, $$V_k(x,q)=\prod_{j=1}^k\frac{1}{1-xW''_j(x,q)}.$$ \end{lemma} \begin{proof} Since each word $k\pi$, where $\pi$ is a word over the alphabet $[k]$, can be written either as $k\pi$, where $\pi$ is a word over the alphabet $[k-1]$, or as $k\pi'k\pi''$, where $\pi'$ is a word over the alphabet $[k-1]$ and $\pi''$ is a word over the alphabet $[k]$, we get \begin{equation}\label{eqb41} V_k(x,q)=V'_k(x,q)+xW''_k(x,q)V_k(x,q), \end{equation} where $V'_k(x,q)$ is the generating function for the number of words $\pi$ over the alphabet $[k-1]$ according to the number of valleys in $k\pi$. Similarly, each word $k\pi$, where $\pi$ is a word over the alphabet $[k-1]$, can be written either as $k\pi$, where $\pi$ is a word over the alphabet $[k-2]$, or as $k\pi'(k-1)\pi''$, where $\pi'$ is a word over the alphabet $[k-2]$ and $\pi''$ is a word over the alphabet $[k-1]$. Also, the number of valleys in $k\pi$ ($k\pi(k-1)$) equals the number of valleys in $(k-1)\pi$ ($(k-1)\pi(k-1)$) for any word $\pi$ over the alphabet $[k-2]$. Therefore, \begin{equation}\label{eqb42} V'_k(x,q)=V'_{k-1}(x,q)+xW''_{k-1}(x,q)V_{k-1}(x,q). \end{equation} Hence, by \eqref{eqb41} and \eqref{eqb42}, we get $V_k(x,q)-V_{k-1}(x,q)=xW''_k(x,q)V_k(x,q)$ for all $k\geq1$. Applying this recurrence relation $k$ times, we have $V_k(x,q)=\prod_{j=1}^k\frac{1}{1-xW''_j(x,q)}$, as claimed. \end{proof} Now we can state the main result of this section. \begin{theorem}\label{th_val_part} The generating function $VP_k(x,q)$ for the number of partitions of $[n]$ with exactly $k$ blocks is given by $$VP_k(x,q)=\frac{x^k}{(1-x)U_{k-1}(t)-U_{k-2}(t)}\prod_{j=1}^{k-1}\frac{U_{j-1}(t)-(1-x(q-1))U_{j-2}(t)}{(1-x)U_{j-1}(t)-U_{j-2}(t)},$$ where $t=1+\frac{x^2}{2}(1-q)$ and $U_m$ is the $m$-th Chebyshev polynomial of the second kind. \end{theorem} \begin{proof} Lemma~\ref{lemb4} and \eqref{eqb40} yield $$VP_k(x,q)=x^k\prod_{j=1}^k\frac{1}{1-xW''_j(x,q)}\prod_{j=1}^{k-1}W'_j(x,q).$$ Thus, by Lemmas \ref{lemb2} and \ref{lemb3}, we have \begin{align*} VP_k(x,q) &=\frac{x^k(A_{k+1}-(1-x^2(q-1))A_k)}{A_{k+1}-A_k}\cdot\\ &\qquad\qquad\cdot\prod_{j=1}^{k-1}\left(\frac{x(q-1)A_j}{A_{j+1}-A_j}\cdot\frac{A_{j+1}-(1-x^2(q-1))A_j}{A_{j+2}-(1-x^2(q-1))A_{j+1}}\right)\\ &=\frac{x^k(A_2-(1-x^2(q-1))A_1}{A_{k+1}-A_k}\prod_{j=1}^{k-1}\frac{x(q-1)A_j}{A_{j+1}-A_j}, \end{align*} where $A_k=(1+x(1-x)(q-1))U_{k-2}(t)-U_{k-3}(t)$. Using the initial conditions $A_1=1$, $A_2=1+x(1-x)(q-1)$ and the fact that $$A_{j+1}-A_j=x(q-1)((1-x)U_{j-1}(t)-U_{j-2}(t)),$$ we get \begin{align*} &VP_k(x,q)=\frac{x^{k+1}(q-1)}{A_{k+1}-A_k}\prod_{j=1}^{k-1}\frac{x(q-1)A_j}{A_{j+1}-A_j}\\ &\quad=\frac{x^k}{(1-x)U_{k-1}(t)-U_{k-2}(t)}\prod_{j=1}^{k-1}\frac{(1+x(1-x)(q-1))U_{j-2}(t)-U_{j-3}(t)}{(1-x)U_{j-1}(t)-U_{j-2}(t)}, \end{align*} which, by the recurrence $U_m(t)=2tU_{m-1}(t)-U_{m-2}(t)$, is equivalent to \begin{align*} VP_k(x,q)=\frac{x^k}{(1-x)U_{k-1}(t)-U_{k-2}(t)}\prod_{j=1}^{k-1}\frac{U_{j-1}(t)-(1-x(q-1))U_{j-2}(t)}{(1-x)U_{j-1}(t)-U_{j-2}(t)}, \end{align*} as claimed. \end{proof} \begin{table}[htp] \begin{center} \begin{tabular}{l||llllllllllll} $k\backslash n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline\hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 2 & 0 & 1 & 3 & 6 & 11 & 20 & 36 & 64 & 113 & 199 & 350 & 615 \\ \hline 3 & 0 & 0 & 1 & 5 & 16 & 45 & 121 & 315 & 799 & 1992 & 4913 & 12029 \\ \hline 4 & 0 & 0 & 0 & 1 & 7 & 31 & 119 & 430 & 1484 & 4935 & 15984 & 50838 \\ \hline 5 & 0 & 0 & 0 & 0 & 1 & 9 & 51 & 249 & 1136 & 4914 & 20343 & 81510 \\ \hline \end{tabular} \caption{The number of partitions of $[n]$ with exactly $k$ blocks without valleys, for $n=1,2,\ldots,12$ and $k=1,2,\ldots,5$}\label{tabvalley} \end{center} \end{table} The generating function for the number of partitions of $[n]$ without valleys is given by \begin{align*} &1+\sum_{k\geq1}VP_k(x,0)\\ &\quad=\sum_{k\geq0}\left(\frac{x^k}{(1-x)U_{k-1}(t')-U_{k-2}(t')}\prod_{j=1}^{k-1}\frac{U_{j-1}(t')-(1+x)U_{j-2}(t')}{(1-x)U_{j-1}(t')-U_{j-2}(t')}\right), \end{align*} where $t'=1+\frac{x^2}{2}$ and $U_m$ is the $m$-th Chebyshev polynomial of the second kind. Table~\ref{tabvalley} presents the number of partitions of $[n]$ with exactly $k$ blocks without valleys. Theorem~\ref{th_val_part}, together with the fact $U_j(1)=j+1$, yields \begin{align*} VP_k(x,1)&=\frac{x^k}{(1-x)U_{k-1}(1)-U_{k-2}(1)}\prod_{j=1}^{k-1}\frac{U_{j-1}(1)-U_{j-2}(1)}{(1-x)U_{j-1}(1)-U_{j-2}(1)}\\ &=\frac{x^k}{\prod_{j=1}^k(1-jx)}, \end{align*} which is the generating function for the number of partitions of $[n]$ with exactly $k$ blocks; see, e.g., \cite{S1}. Also, Theorem~\ref{th_val_part} gives \begin{align*} &\frac{\frac{d}{dq}VP_k(x,q)\mid_{q=1}}{VP_k(x,1)}\\ &=\sum_{j=1}^{k-1} \frac{\lim_{q\rightarrow1}\frac{d}{dq}\frac{U_{j-1}(t)-(1-x(q-1))U_{j-2}(t)}{(1-x)U_{j-1}(t)-U_{j-2}(t)}}{\frac{1}{1-jx}}\\ &\qquad\qquad\qquad\qquad-\frac{(1-x)U'_{k-1}(1)-U'_{k-2}(1)}{1-kx}\\ &=\sum_{j=1}^{k-1}\frac{(U'_{j-1}(1)+xU_{j-2}(1)-U'_{j-2}(1))(1-jx)-((1-x)U'_{j-1}(1)-U'_{j-2}(1))}{1-jx}\\ &\qquad\qquad\qquad\qquad-\frac{(1-x)U'_{k-1}(1)-U'_{k-2}(1)}{1-kx}, \end{align*} which, by the fact that $U'_j(1):=\frac{d}{dq}U_j(t)\mid_{q=1}=-x^2\binom{j+2}{3}$, implies that the generating function for the number of valleys in all the partitions of $[n]$ with exactly $k$ blocks is given by \begin{align*} &\frac{d}{dq}VP_k(x,q)\mid_{q=1}\\ &\qquad=\frac{x^k}{\prod_{j=1}^k(1-jx)}\left(\sum_{j=1}^{k-1}\left(x(j-1)-x^2\binom{j}{2}\right)+\sum_{j=1}^{k}\frac{x^2\binom{j}{2}-x^3\binom{j+1}{3}}{1-jx}\right)\\ &\qquad=\frac{x^k}{\prod_{j=1}^k(1-jx)}\left(x\binom{k-1}{2} -x^2\binom{k}{3}+ \sum_{j=1}^{k}\frac{x^2\binom{j}{2}-x^3\binom{j+1}{3}}{1-jx}\right). \end{align*} This yields the following explicit formula. \begin{corollary}\label{cor3} The number of valleys in all the partitions of $[n]$ with exactly $k$ blocks is given by $$\binom{k-1}{2}S_{n-1,k}-\binom{k}{3}S_{n-2,k}+\sum_{j=2}^{k}\left(\binom{j}{2}f'_{n,j}-\binom{j+1}{3}f_{n,j}\right),$$ where $f_{n,j}=\sum_{i=3}^{n-k}j^{i-3}S_{n-i,k}$, $f'_{n,j}=\sum_{i=2}^{n-k}j^{i-2}S_{n-i,k}$, and $S_{i,j}$ is the Stirling number of the second kind. \end{corollary} \section{Combinatorial proofs} In this section, we provide direct combinatorial proofs of Corollaries \ref{cor1}, \ref{cor3}, and \ref{cor2}. We start with Corollary \ref{cor1}. \vskip .15in \noindent \textbf{Proof of Corollary \ref{cor1}.} \begin{proof} To show that there are $(n-2)k^{n-3}\left(2\binom{k}{3}+\binom{k}{2}\right)$ total peaks (valleys), it is enough to show for each $i$, $1 \leqslant i \leqslant n-2$, that there are a total of $k^{n-3}\left(2\binom{k}{3}+\binom{k}{2}\right)$ peaks at $i$ within all the words $w_1 w_2 \cdots w_n$ in $[k]^n$. There are $2\binom{k}{3}k^{n-3}$ such peaks at $i$ for which $w_i \neq w_{i+2}$ within all the members of $[k]^n$. To see this, note that for any three distinct numbers $a\pi_{i+1}$). We will call a rise or a descent at $i$ \emph{non-trivial} if neither $i$ nor $i+1$ are the smallest elements of their respective blocks. The following lemma provides an explicit formula for the total number of non-trivial rises in all of the members of $P(n,k)$. \begin{lemma}\label{lem10} The number of non-trivial rises (descents) in all of the partitions of $[n]$ with exactly $k$ blocks is given by $$\sum_{j=2}^{k}\binom{j}{2}f'_{n,j},$$ where $f'_{n,j}=\sum_{i=2}^{n-k}j^{i-2}S_{n-i,k}$. \end{lemma} \begin{proof} Given $i$ and $j$, where $2 \leqslant i \leqslant n-k$ and $2 \leqslant j \leqslant k$, consider all the members of $P(n,k)$ which may be decomposed uniquely as % \begin{equation}\label{eqb50} \pi = \pi' j \alpha \beta, \end{equation} % where $\pi'$ is a partition with $j-1$ blocks, $\alpha$ is a word of length $i$ in the alphabet $[j]$ whose last two letters form a rise, and $\beta$ is possibly empty. For example, if $i = 5$, $j = 3$, and $\pi = 122323113342 \in P(12,4)$, then $\pi' = 122$, $\alpha = 23113$, and $\beta = 342$. The total number of non-trivial rises can then be obtained by finding the number of partitions which may be expressed as in \eqref{eqb50} for each $i$ and $j$ and then summing over all possible values of $i$ and $j$. And there are $\binom{j}{2} j^{i-2} S_{n-i,k}$ members of $P(n,k)$ which may be expressed as in \eqref{eqb50} since there are $j^{i-2}$ choices for the first $i-2$ letters of $\alpha$, $\binom{j}{2}$ choices for the final two letters in $\alpha$ (as the last letter must exceed its predecessor), and $S_{n-i,k}$ choices for the remaining letters $\pi' j \beta$ which necessarily constitute a partition of an $(n-i)$-set into $k$ blocks. \end{proof} If $\pi$ is a partition of $[n]$ and $i\in[n]$, then we will say that $i$ is \emph{minimal} if $i$ is the smallest element of a block within $\pi$, i.e., if the $i^{th}$ slot of the canonical representation of $\pi$ corresponds to the left-most occurrence of a letter. We now provide direct combinatorial proofs of Corollaries \ref{cor3} and \ref{cor2}. \vskip .15in \noindent \textbf{Proof of Corollary \ref{cor3}.} \begin{proof} By Lemma~\ref{lem10}, the first sum $\sum_{j=2}^{k}\binom{j}{2}f'_{n,j}$ counts the total number of non-trivial rises within all of the members of $P(n,k)$. From these, we subtract all non-trivial rises at $r$, $r\geq2$, where $r-1$ either goes in the same block as $r$ ($\sum_{j=2}^{k}\binom{j}{2}f_{n,j}$ total such rises) or goes in a block to the left of $r$ ($\sum_{j=2}^{k}\binom{j}{3}f_{n,j}$ total such rises). Thus, the second sum $\sum_{j=2}^{k}\binom{j+1}{3}f_{n,j}$ counts all non-trivial rises at $r$ in which $r-1$ fails to appear in a block to the right of $r$, upon noting $\binom{j}{2}+\binom{j}{3}=\binom{j+1}{3}$. Therefore, the difference between the two sums counts all valleys at $m$ in which $m+2$ is not minimal. We'll call valleys at $m$ where $m+2$ is minimal \emph{trivial}. So to complete the proof, we must show that the total number of trivial valleys at $m$, $m\geq1$, is given by $\binom{k-1}{2}S_{n-1,k}-\binom{k}{3}S_{n-2,k}$, which we rewrite as $2\binom{k}{3}S_{n-2,k} + \binom{k-1}{2}S_{n-2,k-1}$ using the fact that $S_{n-1,k}=kS_{n-2,k}+S_{n-2,k-1}$. First, there are $\binom{k}{3}S_{n-2,k}$ trivial valleys at $m$, where $m$ is not minimal. To see this, pick three numbers $a