\documentclass[10pt]{article}
\textwidth= 5.00in
\textheight= 7.4in
\topmargin = 30pt
\evensidemargin=0pt
\oddsidemargin=55pt
\headsep=17pt
\parskip=.5pt
\parindent=12pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
\usepackage{amsmath,amsthm,amssymb,latexsym,hyperref,url,graphicx}
%%\usepackage{amssymb,latexsym,amsmath,epsfig,amsthm} %% Add other packages as necessary
\makeatletter
\renewcommand\section{\@startsection {section}{1}{\z@}
{-30pt \@plus -1ex \@minus -.2ex}
{2.3ex \@plus.2ex}
{\normalfont\normalsize\bfseries\boldmath}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}
{-3.25ex\@plus -1ex \@minus -.2ex}
{1.5ex \@plus .2ex}
{\normalfont\normalsize\bfseries\boldmath}}
\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. }
\makeatother
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\begin{document}
\begin{center}
\uppercase{\bf Systematic Counting of Restricted Partitions}
\vskip 20pt
{\bf Mingjia Yang}\\
{\smallit Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA}\\
{\tt my237@math.rutgers.edu}\\
\vskip 10pt
{\bf Doron Zeilberger}\\
{\smallit Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA}\\
{\tt doronzeil@gmail.com}\\
\end{center}
\vskip 20pt
\centerline{\smallit Received: , Revised: , Accepted: , Published: } % We will fill in the dates
\vskip 30pt
\centerline{\bf Abstract}
\noindent
We use `partial difference operator schemes', and dynamical programming to design algorithms
that systematically count sets of integer partitions avoiding {\it any} set of patterns (of a certain,
natural, kind). We describe two approaches, a `negative' (adapting the Goulden--Jackson algorithm for enumerating words),
and a `positive' approach, that turns out to be much more efficient. Nevertheless the negative
approach has theoretical interest.
\pagestyle{myheadings}
\markright{\smalltt INTEGERS: 20 (2020)\hfill}
\thispagestyle{empty}
\baselineskip=12.875pt
\vskip 30pt
{\bf{1.\quad Introduction}}~\\
One of the cornerstones of enumerative combinatorics (and number theory!) is the topic of (integer) {\it partitions}. Recall that
a partition of a non-negative integer $n$ is a list of integers $(\lambda_1, \dots, \lambda_k)$ such that
$\lambda_1 \geq \dots \geq \lambda_k \geq 1$ and $\lambda_1+ \dots + \lambda_k=n$.
As usuall, we will denote the number of integer partitions of $n$ by $p(n)$.
This is a very famous sequence, OEIS sequence A41.
While there is no easy, direct formula for $p(n)$, there is a nice generating function, that goes back to Leonhard Euler.
Denoting the number of integer partitions of $n$ by $p(n)$, Euler discovered that
$$
\sum_{n=0}^{\infty} p(n)\,q^n \, = \, \prod_{i=1}^{\infty} \, \frac{1}{1-q^i} \quad .
$$
The {\bf bible} of the theory of partitions is George Andrews' classic \cite{An}. We also strongly
recommend Drew Sills' fascinating monograph \cite{S}.
Suppose that you did not know about Euler's generating function,
and you were given the task of computing the first, say, $1000$ terms of the sequence $p(n)$, how would you proceed?
The most straightforward way would be to try and use {\it dynamical programming}. Note that partitions have the {\it hereditary} property.
If you chop-off the largest entry of the partition of $n$, $(\lambda_1, \dots, \lambda_k)$,
you would get a shorter partition, $(\lambda_2, \dots, \lambda_k)$, of $n-\lambda_1$.
Alas, because of the condition $\lambda_1 \geq \lambda_2$, we have to `remember' what $\lambda_1$ was, after kicking it out.
So we are {\bf forced} to consider a more general quantity, let's call it
$P(n,m)$, enumerating the set of partitions of $n$ whose largest part is {\bf exactly} $m$. Once we can compute this
more general quantity, the original object of interest, $p(n)$, is given by
$$
p(n) \, = \, \sum_{m=1}^{n} \, P(n,m) \quad .
$$
In order to compute $P(n,m)$ we have the obvious recurrence (alias partial {\bf difference equation})
$$
P(n,m) \, = \, \sum_{m'=1}^{m} P(n-m,m') \quad , \quad n \geq m \geq 1 ,
\eqno(FundamentalRecurrence)
$$
subject to the boundary conditions $P(m,m)=1$ and $P(n,m)=0$ if $n