%Version 2 of the paper - responding to the referee's report and
% adding an improved formula for $P(n,\hat{2})$ as well as
% the generating function. Modified the proof of Theorem 10
% accordingly, and added comment on the fact that the 
% sequence $P(n,\hat{2})$ is listed in Sloane's 
% Encyclopedia of Integer Sequences.


\documentclass[12pt,reqno]{article}



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

\usepackage{color}
\usepackage{fullpage}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage[all]{xy}
\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}}}



\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\def\qed{\hfill$\Box$\bigskip}
\def\proof{\noindent{\bf Proof:} }

\begin{document}

\makeatletter

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


\begin{center}
\vskip 1cm {\LARGE\bf Integer Sequences Related to Compositions without 2's}
\vskip 1cm
\large
Phyllis Chinn\\
Department of Mathematics\\
Humboldt State University\\
Arcata, CA  95521\\
USA\\
\href{mailto:phyllis@math.humboldt.edu}{\tt phyllis@math.humboldt.edu}
\ \ \\
\vskip 0.5cm

Silvia Heubach\\ 
Department of Mathematics \\
California State University, Los Angeles\\ 
Los Angeles, CA 90032\\
USA\\
\href{mailto:sheubac@calstatela.edu}{\tt sheubac@calstatela.edu}
\end{center}

\vskip 0.5cm

\begin{abstract}
A composition of a positive integer $n$ consists of an ordered sequence of positive integers whose sum is $n$.  We investigate compositions in which the summand 2 is not allowed, and count the total number of such compositions and the number of occurrences of the summand $i$ in all such compositions. Furthermore, we explore patterns in the values for  $C_{j}(n,\hat{2})$, the number of compositions of $n$ without 2's having $j$ summands, and show connections to several known sequences, for example the $n$-dimensional partitions of 4 and 5. 
\end{abstract} 

\vspace{.3in}


\section{Introduction}

Adding whole numbers seems like one of the most basic ideas in all of mathematics, but many unanswered questions remain within this area of combinatorial number theory.  A broad class of questions relate to compositions and partitions. A {\it composition} of $n$ is an ordered collection of one or more positive integers for which the sum is $n$.  The number of summands is called the number of {\it parts} of the composition. A {\it palindromic composition} or {\it palindrome} is one for which the sequence is the same from left to right as from right to left. A {\it partition} of $n$ is an unordered collection of one or more positive integers whose sum is $n$.

Compositions may also be viewed as {\it tilings} of a 1-by-$n$ board with 1-by-$k$ tiles,
$1\leq k\leq n$.  Figure~\ref{comps3} shows the compositions of 3 together with corresponding tilings of the 1-by-3 board using 1-by-1, 1-by-2 and 1-by-3 tiles.\

\begin{figure}[hbt]
\begin{center}
\[
\begin{array}{rcrc}
1+1+1&\hspace{.3in}\framebox(10,10)\ \framebox(10,10)\ \framebox(10,10)\ &\hspace{.7in}1+2&\hspace{.3in}\framebox(10,10)\ \framebox(20,10)\ \\
2+1&\hspace{.3in}\framebox(20,10)\ \framebox(10,10)\ &\hspace{.7in}3&\hspace{.3in}\framebox(30,10)\                                          
\end{array}
\]
\caption{The compositions of 3 and their corresponding tilings}
\label{comps3}
\end{center}
\end{figure}

In this view, a palindromic composition corresponds to a symmetric
tiling, e.g., the tilings corresponding to 1+1+1 and 3 in
Figure~\ref{comps3}.  One reason to adopt the tiling viewpoint for
compositions is that some counting questions about compositions arise
more naturally in the context of tilings.  More examples of the
interrelation between compositions and tilings can be found
in~\cite{4,5,6,7,9}.

In~\cite{9}, Grimaldi explores the question of how many compositions of
$n$ exist when no 1's are allowed in the composition.  In this paper we
explore a related question, namely, how many compositions of $n$ exist
when no 2's are allowed in the composition.  We also look at how many
of these compositions are palindromes.

We count the total number of compositions and explore patterns involving the number of compositions with a fixed number of parts and the total number of occurrences of each positive integer among all the compositions of $n$ without occurrences of 2. In the viewpoint of tilings, these questions correspond to counting the total number of tilings, the number of tilings with a fixed number of tiles and the number of times a tile of a particular size occurs among all the tilings of the 1-by-$n$ board that do not contain any 1-by-2 tiles. Next, we count the number of palindromes of $n$ without any occurrence of 2, which correspond to symmetric tilings with no 1-by-2 tiles. Finally, we give a table of values for the number of partitions of $n$ that do not contain any occurrence of 2. We use the following notation:
\[ \begin{array}{rcl}
C(n,\hat{2})&=&\makebox{the number of compositions of $n$ with no 2's}\\
C_{j}(n,\hat{2})&=&\makebox{the number of compositions of $n$ with no 2's having exactly}\\
&& \makebox{$j$ parts}\\
x(n,i,\hat{2})&=&\makebox{the number of occurrences of $i$ among all compositions of}\\
&& \makebox{$n$ with no 2's}\\
P(n,\hat{2})&=&\makebox{the number of palindromes of $n$ with no 2's}\\
\pi(n,\hat{2})&=&\makebox{the number of partitions of $n$ with no 2's}.\\
\end{array} \]
Because we consider only compositions and palindromes of $n$ with no 2's in this paper, we sometimes leave out the qualifier ``with no occurrence of 2's".

\section{The number of compositions without 2's}

We start by counting the total number of compositions.

\begin{theorem} \label{Cn} The number of compositions without occurrence of 2's is given by
  
\[C(n,\hat{2})=2\cdot C(n-1,\hat{2})-C(n-2,\hat{2})+C(n-3,\hat{2})\]

\noindent with initial conditions $C(0,\hat{2})=C(1,\hat{2})=C(2,\hat{2})=1$, and generating function

\[G_{C}(z)=\sum_{n=0}^{\infty}C(n,\hat{2})z^{n}=\frac{1-z}{1-2z+z^{2}-z^{3}}\ .\]

\end{theorem}

\noindent \bf Proof.  \rm The compositions of $n$ without 2's can be
generated recursively from those of $n-1$  by either appending a 1 or
by increasing the last summand by 1.  However, this process does not
generate those compositions ending in 3, which we generate separately
by appending a 3 to the compositions of $n-3$. Furthermore, we must
delete the compositions of $n-1$  that end in 1, since increasing the
terminal 1 would produce a composition of $n$ that ends in 2.  The
number of such compositions corresponds to the number of compositions
of $n-2$. The generating function $G_{C}(z)$ is computed by multiplying
each term in the recurrence relation by  $z^{n}$, and summing over
$n\geq3$. Expressing the resulting series in terms of $G_{C}(z)$ and
solving for $G_{C}(z)$ gives the result. \hfill\rule{2mm}{2mm}\\

The following table gives some values of $C(n,\hat{2})$:\\

\begin{table}[hbt]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$n$&0&1&2&3&4&5&6&7&8&9&10&11&12\\ \hline
$C(n,\hat{2})$&1&1&1&2&4&7&12&21&37&65&114&200&351\\ \hline
\end{tabular}
\end{center}
\caption{The number of compositions with no occurrence of 2}
\label{numcomps}
\end{table}


The sequence $C(n,\hat{2})$  appears as A005251 in Sloane's On-Line Encyclopedia of Integer Sequences~\cite{10}, with representation $a(n)=a(n-1)+a(n-2)+a(n-4)$. Two alternative formulas are given for this sequence:
\begin{eqnarray}
\label{snu1} 
a(n)&=&2 \cdot a(n-1)-a(n-2)+a(n-3)
\end{eqnarray}
\noindent and
\begin{eqnarray}
\label{snu2}
a(n)&=&\sum_{j<n}a(j)-a(n-2).
\end{eqnarray}

\noindent Eq.~(\ref{snu1}) is identical to the expression for
$C(n,\hat{2})$ in Theorem 1, while Eq.~(\ref{snu2}) indicates a second
way to create all the compositions with no 2's, namely, to append the
summand $j$ to a composition of $n-j$, except when $j = 2$. Comparison
of the initial conditions ($a(0)=0,\ a(1)=a(2)=a(3)=1$) shows that
$C(n,\hat{2})=a(n+1)$.

One interpretation of sequence A005251 is the number of binary
sequences without isolated 1's~\cite{2}.  There is a nice combinatorial
explanation for the equality of the two different counts, namely, the
number of compositions of $n$ without 2's and the number of binary
sequences of $n$-1 without isolated 1's. Think of the composition as a
tiling of the 1-by-$n$ board. Associate a binary sequence of length
$n$-1 with the interior places where a tile can start or end. If the
binary sequence has a 0 in position $k$, then a tile ends or starts at
position $k$, whereas a 1 indicates that the tile ``continues".  With
this interpretation, isolated 1's, which appear as $\ldots 010\ldots $
correspond to a 1-by-2 tile, as illustrated in Figure~\ref{bin}.\\



\begin{figure}[hbt]
\begin{center}
\framebox(15,15)\ \framebox(15,15)\ \rule[-.5pt]{30pt}{16.5pt}\framebox(15,15)\ \framebox(45,15)\ \framebox(15,15)\ \framebox(15,15)\ \\
 \makebox[15pt]{0}\makebox[15pt]{\bf 0}\makebox[15pt]{\bf 1}\makebox[15pt]{\bf 0}\makebox[15pt]{0}\makebox[15pt]{1}\makebox[15pt]{1}\makebox[15pt]{0}\makebox[15pt]{0} 
\caption{Correspondence of binary sequences and compositions}
\label{bin}
\end{center}
\end{figure}


\section{The number of occurrences of the summand $i$ in all compositions with no 2's} 

Table~\ref{occur} gives values of $x(n,i,\hat{2})$ for $1 \leq n \leq 10$ and $1 \leq i \leq 10$.  We note that the entries in the columns appear to repeat.  Theorem 2 shows that this repetition indeed continues.

\begin{table}[hbt]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}\hline
&	$i =1$&	2&	3&	4&	5&	6&	7&	8&	9&	10\\ \hline
$n =1$&	1&	& & & & & & & & \\ \hline								
2&	2&	0& & & & & & & & \\ \hline								
3&	3&	0&	1& & & & & & &\\ \hline							
4&	6&	0&	2&	1& & & & & &\\ \hline						
5&	13&	0&	3&	2&	1& & & & &\\ \hline					
6&	26&	0&	6&	3&	2&	1& & & &\\ \hline				
7&	50&	0&	13&	6&	3&	2&	1& & &\\ \hline			
8&	96&	0&	26&	13&	6&	3&	2&	1& &\\ \hline		
9&	184&	0&	50&	26&	13&	6&	3&	2&	1& \\ \hline	
10&	350&	0&	96&	50&	26&	13&	6&	3&	2&	1\\ \hline

\end{tabular}
\end{center}
\caption{The number of occurrences of $i$ among all compositions of $n$}
\label{occur}
\end{table}

\begin{theorem} \label{col rep} \hspace{.1in} $x(n,i,\hat{2})=x(n+j,i+j,\hat{2})$ for all $i \neq 2$, $i+j \neq 2$.
\end{theorem}

\noindent \bf Proof.  \rm Consider any occurrence of the summand $i$ among the compositions of $n$ without 2's.  There is a corresponding occurrence of $i+j$ in a composition of $n+j$ in which the summand $i$ has been replaced by $i+j$ and all other summands are the same, as long as $i+j \neq 2$.  This correspondence is actually one-to-one since any occurrence of $i+j$ among the compositions of $n+j$ corresponds to an occurrence of $i$ among the compositions of $n$ obtained by replacing $i+j$ by $i$, subject to the condition that $i \neq 2$. \hfill \rule{2mm}{2mm}\\

As a result of Theorem 2, we only need to generate the first column of Table~\ref{occur}, namely the number of occurrences of 1 among all the compositions of $n$ without 2's, a sequence not previously listed in Sloane's On-Line Encyclopedia of Integer Sequences~\cite{10}. We will give three different ways to generate this sequence. 

\begin{theorem}  The number of occurrences of 1 among all compositions of $n$ without 2's is given by 
\begin{eqnarray}
\label{xn1}
x(n,1,\hat{2})&=&2\cdot x(n-1,1,\hat{2})-x(n-2,1,\hat{2})+x(n-3,1,\hat{2}) \nonumber \\
&&+C(n-1,\hat{2})-C(n-2,\hat{2})
\end{eqnarray}
\noindent with initial conditions $x(n,1,\hat{2})=n$  for $n=1,2,3$, or by
\begin{eqnarray}
\label{xn2}
x(n,1,\hat{2})=n \cdot C(n,\hat{2})-\sum_{i=1}^{n-2}(n-i+1) \cdot x(i,1,\hat{2}).
\end{eqnarray}
The generating function $G_x(z)=\sum_{n=1}^{\infty}x(n,1,\hat{2})z^{n}$ is given by
\begin{eqnarray}
\label{xn3}
G_x(z)=\frac{z(1-z)^2}{(1-2z+z^{2}-z^{3})^2}=z G_C(z)^2,
\end{eqnarray}
thus, $x(n,1,\hat{2})=\sum_{i=0}^{n-1}C(i,\hat{2})C(n-1-i,\hat{2})$.
\end{theorem}

\vspace{.1in}



\noindent \bf Proof.  \rm Eq.~(\ref{xn1}) is based on the creation of the compositions of $n$ from those of $n-1$  by either adding a 1 or by increasing the rightmost summand by 1. When adding a 1, we get all the ``old" 1's, and for each composition an additional 1, altogether   $x(n-1,1,\hat{2})+C(n-2,\hat{2})$ 1's. When increasing the rightmost summand by 1, again we get all the ``old" 1's (of which there are $x(n-1,1,\hat{2})$ ), except that we need to make adjustments for those compositions of $n-1$ with terminal summand 1, since they would result in a forbidden 2, and the otherwise missing compositions of $n$ that end in 3. The latter have $x(n-3,1,\hat{2})$  1's, which need to be added to the total count, while the 1's in the compositions of $n-1$ with a terminal 1 need to be subtracted. To determine how many of these 1's there are, we look at the composition of $n-1$ as consisting of a composition of $n-2$ and the terminal 1, i.e., we distinguish between ``interior" 1's (those to the left of the terminal 1) and the terminal 1. The interior 1's correspond to all the 1's in the compositions of $n-2$. In addition, there is one terminal 1 for each composition of $n-2$. Thus, we subtract a total of $x(n-2,1,\hat{2})+C(n-2,\hat{2})$ 1's from the total count.  Simplification gives the stated result. 

The derivation of Eq.~(\ref{xn2}) is based on a geometric argument involving all tilings of a 1-by-$n$  board. The total area of all these tilings, given by $n \cdot C(n,\hat{2})$, has to equal the sum of the areas covered by 1-by-1, 1-by-2,\ldots, and 1-by-$n$ tiles. The area covered by 1-by-$k$  tiles is given by $k \cdot x(n,k,\hat{2})$, and thus, $n \cdot C(n,\hat{2})=\sum_{k=1}^{n}k \cdot x(n,k,\hat{2})$. Since $x(n,2,\hat{2})=0$, we can rewrite this equation as
\begin{eqnarray}
\label{snu3}
x(n,1,\hat{2})&=&n \cdot C(n,\hat{2})-\sum_{k=3}^{n}k \cdot x(n,k,\hat{2}).
\end{eqnarray}
\noindent Note that Eq.~(\ref{snu3}) relates the first entry in any row of Table~\ref{occur} to all the other entries in the same row, which in turn show up in column 1 in ``reverse" order: the rightmost non-zero element in any row equals the first element in column 1, the second element from the right in  any row equals the second element in column 1, etc. We can formalize this association using the formula given in Theorem~\ref{col rep} (for $i=1$): $x(m,1,\hat{2})=x(m+j,j+1,\hat{2})$. We now choose $m$ and $j$ so that we get the terms that appear on the right-hand side of Eq.~(\ref{snu3}). This requires that $k=j+1$  and $n=m+j$ , so using $m=n-k+1$  results in $x(n-k+1,1,\hat{2})=x(n,k,\hat{2})$. Substituting this equality into Eq.~(\ref{snu3}) and reindexing gives the second recurrence relation for $x(n,1,\hat{2})$.
Finally, the generating function $G_x(z)$ is computed as in the proof of Theorem~\ref{Cn}, except that we now sum over $n \ge 4$ and express the resulting series in terms of $G_x(z)$ and $G_C(z)$. Note that the last equality in Eq.~(\ref{xn3}) indicates that the terms for the sequence $\{x(n,1,\hat{2})\}$ are a convolution of those of the sequence $\{C(n,\hat{2})\}$ , with the index shifted by 1. The formula for $x(n,1,\hat{2})$ in terms of the $C(i,\hat{2})$ follows immediately from this observation.
\hfill\rule{2mm}{2mm}

     
              
                                                                                             
\section{The number of compositions without 2's having a given number of parts}

Another question one can ask about compositions is how many of them have a given numbers of parts, i.e., a given number of summands.  Table~\ref{parts} gives the number of compositions of $n$ without 2's that have $j$ parts.

\begin{table}[hbt]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
&	$j =1$&	2&	3&	4&	5&	6&	7&	8&	9&	10& 11\\ \hline
$n =1$&	1&	& & & & & & & & & \\ \hline	
2&0&1& & & & & & & & & \\ \hline
3&1&0&1& & & & & & & & \\ \hline
4&1&2&0&1& & & & & & & \\ \hline
5&1&2&3&0&1& & & & & & \\ \hline
6&1&3&3&4&0&1& & & & & \\ \hline
7&1&4&6&4&5&0&1& & & & \\ \hline
8&1&5&9&10&5&6&0&1& & &  \\ \hline
9&1&6&13&16&15&6&7&0&1& &  \\ \hline
10&1&7&18&26&25&21&7&8&0&1& \\ \hline
11&1&8&24&40&45&36&28&8&9&0&1\\ \hline
12&1&9&31&59&75&71&49&36&9&10&0\\ \hline
13&1&10&39&84&120&126&105&64&45&10&11 \\ \hline
14&1&11&48&116&185&216&196&148&81&55&11 \\ \hline
15&1&12&58&156&276&356&357&288&201&100&66 \\ \hline
16&1&13&69&205&400&567&623&554&405&265&121\\ \hline
17&1&14&81&264&565&876&1050&1016&819&550&341 \\ \hline


\end{tabular}

\end{center}
\caption{The number of compositions of $n$ with $j$ parts}
\label{parts}
\end{table}

The values in Table~\ref{parts} are generated using the recursion given in Theorem~\ref{cjn}, which relates the entries in the $j^{th}$  column to those in the $(j-1)^{st}$ column.  

\begin{theorem} \label{cjn} \hspace{.1in} $C_{j}(n,\hat{2})=\sum_{k=1}^{n-1}C_{j-1}(n-k,\hat{2})-C_{j-1}(n-2,\hat{2})$.


\end{theorem}

\noindent \bf Proof.  \rm For any composition of $n-k$  having $j-1$  parts, we can form a composition of $n$ having $j$ parts by adding the summand $k$  to the end of the smaller composition, except for $k=2$.  This increases the number of parts by one as required. \hfill\rule{2mm}{2mm}\\                            

We will now look at the patterns in the columns and diagonals of Table~\ref{parts}. The patterns in the left two columns clearly continue, since they correspond, respectively, to the single composition with one part, namely $n$, and the $n-3$ ways (for $n > 4$) to add two numbers (without using a 2) to get $n$. None of the remaining columns in Table~\ref{parts} show any obvious pattern and they do not (yet) occur in~\cite{10}.


Unlike the columns, the diagonals contain a rich set of patterns and show many connections to known integer sequences. For the entry in row $n$  and column $j$  in the $k^{\rm th}$ diagonal, we have $n-j=k-1$, and thus the entries in the $k^{\rm th}$ diagonal are given by $C_{j}(n,\hat{2})=C_{j}(j+k-1,\hat{2})$. We will look at the possible compositions of $n$ having $j$ parts by creating a composition of $n=j+k-1$  as follows: we start with $j$ 1's (as there are to be $j$ parts), and then distribute the difference $n-j=k-1$  across these $j$ parts, adding to the 1's that are already there, as illustrated in the following example.  Consider the compositions of $n=4$  having $j=2$  parts which can be generated as follows: first create two 1's, resulting in the composition 1+1. Then distribute the difference $n-j=2$ , i.e., consider all the partitions of 2, namely $\{2\}$ and $\{1, 1\}$. Using the first partition leads to 3+1 (the first 1 is increased by 2) or 1+3 (the second 1 is increased by 2), and the second partition creates 2+2 (both 1's are increased by 1). The latter composition is not allowed as it contains 2's, so we have to disregard all the partitions of $n-j$ that contain a 1.

Now we can look at the diagonals in general, using this method to create and count the compositions of $n$ having a given number of parts. 

\begin{theorem} 

1.\ \ $C_{j}(j,\hat{2})=1$    (first diagonal)\\
2.\ \ $C_{j}(j+1,\hat{2})=0$    (second diagonal)\\
3.\ \ $C_{j}(j+2,\hat{2})=C_{j}(j+3,\hat{2})=j$    (third and fourth diagonals).

\end{theorem}

\noindent \bf Proof.  \rm The first diagonal corresponds to the compositions of all 1's, the only way to have $n$ parts in a composition of $n$. For the second diagonal, $k = 2$ and thus $n-j=1$. The only partition of 1 is itself, but this partition has to be excluded, so there are no compositions of $n$ (without 2's) having $n-1$ parts. On the third diagonal, $k=3$ and $n-j=2$. This is exactly the example described above (for $j=2$). Thus, the only partition for distributing the difference between $n$ and $j$ is the single 2. Since there are $j$ parts, there are exactly $j$ possible compositions (with a single 3 and $j-1$ 1's). For the fourth diagonal, a similar argument applies, as the only partition of 3 without 1's is the single 3, so there are again $j$ possible compositions (with a single 4 and $j-1$ 1's).\hfill\rule{2mm}{2mm}\\

The next few diagonals contain more interesting sequences.

\begin{theorem}  
1.\ \ $C_{j}(j+4,\hat{2})=j(j+1)/2$, i.e., the triangle numbers occur in the fifth diagonal. \\
2.\ \ $C_{j}(j+5,\hat{2})=j^{2}$, i.e., the square numbers occur in the sixth diagonal.
\end{theorem}

\noindent \bf Proof.  \rm For $k = 5$, we need to distribute $n-j=4$. The partitions of 4 that do not contain a 1 are $\{4\}$ and $\{2, 2\}$. There are $j$ ways to place the additional 4 and $j(j-1)/2$ ways to allocate the two 2's. Thus, $C_{j}(j+4,\hat{2})=j+j(j-1)/2=j(j+1)/2$.   For $k = 6$, we need to distribute $n-j=5$. The partitions of 5 that do not contain a 1 are $\{5\}$ and $\{3,2\}$, and there are $j$ possibilities for the first partition and $j(j-1)$  for the second. Altogether,  we have $C_{j}(j+5,\hat{2})=j+j(j-1)=j^{2}$.   \hfill\rule{2mm}{2mm}                                                                     

\begin{theorem}

The seventh diagonal contains the $n$-dimensional partitions of 4. 

\end{theorem}

\noindent \bf Proof.  \rm For $k=7$ , we need to distribute $n-j=6$.
The partitions of 6 that do not contain a 1 are $\{6\}$, $\{4, 2\}$,
$\{3, 3\}$ and $\{2, 2, 2\}$. There are $j$ compositions for the first
partition, $j(j-1)$   for the second, $j(j-1)/2$  for the third, and
$j(j-1)(j-2)/6$  for the fourth. Adding these terms and simplifying
shows that \[C_{j}(j+6,\hat{2})=j(j^{2}+6j-1)/6.\] \noindent The
sequence $C_{j}(j+6,\hat{2})$  appears as A008778 in Sloane's On-Line
Encyclopedia of Integer Sequences~\cite{10}. A008778 is defined by
\[a(n)=(n+1)(n^{2}+8n+6)/6\] and counts the $n$-dimensional partitions
of 4 (for a definition see~\cite{1}, p. 179).  We need to show the
equivalence of the sequences $a(n)$  and $C_{j}(j+6,\hat{2})$  for a
suitable value of $n$. The formulas for these two sequences suggest
that $C_{j}(j+6,\hat{2})=a(j-1)$, which can be confirmed by basic
algebraic manipulations.\hfill\rule{2mm}{2mm}

\begin{theorem}

The eighth diagonal contains the pentagonal pyramidal numbers.

\end{theorem}

\noindent \bf Proof.  \rm For $k=8$, we need to distribute $n-j=7$. The
partitions of 7 that do not contain a 1 are $\{7\}$, $\{5, 2\}$, $\{4,
3\}$ and $\{3, 2, 2\}$. These correspond, respectively, to the
following number of compositions: $j,\ j(j-1),\ j(j-1)$, and
$j(j-1)(j-2)/2$.  Adding these terms and simplifying shows that
\[C_{j}(j+7,\hat{2})=j^{2}(j+1)/2.\]   \noindent The sequence
$C_{j}(j+7,\hat{2})$  appears as A002411 in Sloane's On-Line
Encyclopedia of Integer Sequences~\cite{10}. A002411 is defined by
$$a(n)=n^{2}(n+1)/2$$  \noindent and counts the pentagonal pyramidal
numbers (for a definition see~\cite{3}, pp. 193-195). Clearly,
$C_{j}(j+7,\hat{2})=a(j)$.\hfill\rule{2mm}{2mm}

\begin{theorem}

The ninth diagonal contains the $n$-dimensional partitions of 5.

\end{theorem}

\noindent \bf Proof.  \rm For $k=9$, we need to distribute $n-j=8$. The
partitions of 8 that do not contain a 1 are $\{8\}$, $\{6, 2\}$, $\{5,
3\}$, $\{4, 4\}$, $\{4, 2, 2\}$, $\{3, 3, 2\}$ and $\{2, 2, 2, 2\}$ and
together generate a total of \[ j+2j(j-1)+{j \choose 2}+2j{j-1 \choose
2}+{j \choose 4}=j+5{j \choose 2}+6{j \choose 3}+{j \choose 4}\]
compositions.  $C_{j}(j+8,\hat{2})$  appears as A008779 in Sloane's
On-Line Encyclopedia of Integer Sequences~\cite{10}. A008779 is defined
by \[a(n)=1+6n+11{n \choose 2}+7{n \choose 3}+{n \choose 4}\]  and
counts the $n$-dimensional partitions of 5 (for a definition
see~\cite{1}, p. 179).  We need to show the equivalence of the
sequences $a(n)$  and $C_{j}(j+8,\hat{2})$  for a suitable value of
$n$. Replacing $j$ by $j+1$  in the expression derived above for
$C_{j}(j+8,\hat{2})$  and simplifying shows that
$C_{j+1}((j+1)+8,\hat{2})=a(j)$, i.e., $C_{j}(j+8,\hat{2})=a(j-1)$,
similar to the case $k=7$.\hfill\rule{2mm}{2mm}\\

\noindent \bf Remark.  \rm The $n$-dimensional partitions of 4 and 5
are not the only ones contained in the diagonals of Table~\ref{parts}.
Further study shows that the $n$-dimensional partitions of 2 and 3 also
occur on the diagonals. In~\cite{1}, formulas for the $n$-dimensional
partitions of $k$ are given for $k\leq 6$. The $n$-dimensional
partitions of 2 are given as $a(n)=n+1$, which is the sequence in the
$3^{\rm rd}$ diagonal: $C_{j}(j+2,\hat{2})=a(j-1)$. The $n$-dimensional
partitions of 3 are given as $a(n)=1+2n+n(n-1)/2$ , and simple
algebraic manipulation shows that this sequence appears on the $5^{\rm
th}$ diagonal:  $C_{j}(j+4,\hat{2})=a(j-1)$.  A pattern emerges: for
odd $k$, the $k^{\rm th}$ diagonal contains the $n$-dimensional
partitions of $(k+1)/2$. This conjecture was very exciting because no
generating function exists for this family; if a nice connection could
be established, then one could compute the $n$-dimensional partitions
in a simple way, using Theorem~\ref{cjn}. However, the pattern
does not continue: the sequence for the $n$-dimensional partitions of
6, namely, $\{11, 48, 140, 326, 657, 1197,\ldots\}$, which should have
appeared in the $11^{\rm th}$ d iagonal, does not show up. Nor does
this sequence appear in the $13^{\rm th}$ diagonal, the only one that
has 11 as the second element.


\section{The number of palindromes with no 2's}

As a last exploration, let us consider the number of palindromes of $n$  with no 2's.  Table~\ref{pals} lists the actual palindromes for the first few values of $n$.
\begin{table}[hbt]
\begin{center}
%\small
\[ \begin{array}{|c|c|c|c|c|c|}\hline
n&1&2&3&4&5\\ \hline
\makebox{Palindromes}&1&1+1&1+1+1&1+1+1+1&1+1+1+1+1\\ 
\makebox{of $n$}&&&3&4&1+3+1\\ 
\makebox{with no 2's}&&&&&5\\  \hline
\end{array}
\]
\normalsize
\end{center}
\caption{Palindromes of $n$ with no 2's}
\label{pals}
\end{table}


In the following theorem, we give recursive formulas and the generating function for $P(n,\hat{2})$.
\begin{theorem}
\label{palnums}
The number of palindromes of $n$ without 2's is given by
$$P(n,\hat{2})=\left \{\begin{array}{ll}
C(k+1,\hat{2}), & \mbox{ for } n=2k, k\geq 0;\\
C(k+1,\hat{2})+C(k-1,\hat{2}),& \mbox{ for } n=2k+1,k\geq 0,
\end{array}\right. $$
\noindent with generating function $G_{P}(z)=\sum_{n=0}^{\infty}P(n,\hat{2})z^{n}={\mbox{{\small $1+z$}} 
\over \mbox{{\small $1-z^{2}-z^{3}$}}}$.
\end{theorem}

\noindent \bf Proof.  \rm In general, for odd  $n$, begin with any odd number $1\leq m\leq n$  as a middle entry and fill in the left side of the palindrome of $n$ with any composition of $(n-m)/2=j$  that has no 2's and complete the right side of the palindrome of $n$ with the composition of $j$  in opposite order.  The total number of such palindromes is given by  $P(2k+1,\hat{2})=\sum_{j=0}^{k}C(j,\hat{2})=C(k+1,\hat{2})+C(k-1,\hat{2})$.  For even $n$, we must omit the palindromes that are formed with a 2 in the middle, but do allow an even split, i.e., no middle term.  Thus, $P(2k,\hat{2})=C(k,\hat{2})+\sum_{j=0}^{k-2}C(j,\hat{2})=C(k+1,\hat{2})$, where the last equality follows from Eq.~(\ref{snu2}). Note that we define $P(0,\hat{2}) = 1$ similar to the definition for $C(0,\hat{2})$.

To derive the generating function, we separate $G_{P}(z)$ into odd and even terms, substitute the relevant formulas, factor out appropriate powers of $z$ and express the resulting series in terms of the generating function  $G_C(z^2)$:
\begin{eqnarray*}
G_{P}(z)&=&\sum_{k=0}^{\infty}P(2k+1,\hat{2})z^{2k+1} + \sum_{k=0}^{\infty}P(2k,\hat{2})z^{2k}\\
&=& \frac{1 }{z}\sum_{k=0}^{\infty}C(k+1,\hat{2})(z^{2})^{k+1}+z^3 \sum_{k=0}^{\infty}C(k-1,\hat{2})(z^{2})^{k-1}+\\
&&\frac{1 }{z^2}\sum_{k=0}^{\infty}C(k+1,\hat{2})(z^{2})^{k+1}\\
&=&G_C(z^2) \left(\frac{z+z^5+1}{z^2}\right )-\frac{1}{z}-\frac{1}{z^2}.
\end{eqnarray*}
Substituting the formula for $G_C(z^2)$ and simplifying gives the desired result. \hfill\rule{2mm}{2mm}\\


Table~\ref{numpals} gives the number of palindromes of $n$ without 2's for $0 \leq n \leq 16$.

\begin{table}[hbt]
\begin{center}
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline
P(n,\hat{2})&1&1&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65\\ \hline
\end{array}
\]
\end{center}
\caption{The number of palindromes of $n$ without 2's}
\label{numpals}
\end{table}

The sequence $P(2k+1,\hat{2})$ appears as A005314 in~\cite{10} as one
of the sequences used to define Toeplitz matrices whose inverses
contain large entries (for a definition see~\cite{8}, p. 130).
A005314's definition, $a(n)=2a(n-1)-a(n-2)+a(n-3)$   is identical to
Equation~\ref{snu2}, which counts the number of compositions. There is
an easy combinatorial explanation for this fact, namely an alternative
method to create palindromes. Rather than using compositions, we
proceed in a manner similar to the way we created compositions
recursively: Append ``1+'' and ``+1'' to the left and right end of a
palindrome of (odd) $n$, respectively, or increase the two end summands
by 1. If the palindrome consists of a single summand, increase the
summand by 2 instead. Delete the palindromes that would result in a
forbidden 2, and create those that have end summands 3 by adding a 3 to
both ends of a palindrome of $n-6$. Thus, the total number of
palindromes for odd $n$ is given by
is given by
$P(2k+1,\hat{2})=2P(2(k-1)+1,\hat{2})-P(2(k-2)+1,\hat{2})+P(2(k-3)+1,\hat{2})$.
Comparison of the
initial terms ($a(0)=0,\ a(1)=1,\ a(2)=2$) shows that
$P(2k+1,\hat{2})=a(k+1)$.

The complete sequence $P(n,\hat{2})$ appears in \cite{10} as shifted
sequence A000931, the Padovan sequence, with $a(n)=P(n-5,\hat{2})$, and
as A078027, with $a(n)=P(n-7,\hat{2})$. Using the generating function
derived in Theorem~\ref{palnums} and standard methods to compute the
generating function of a shifted sequence (see for example \cite{W},
Rule 1, p. 34), it can be established that the sequences are
identical.

\section{Extensions and open problems}

We have not counted the number of occurrences of the integer $i$  in
all palindromes of $n$, nor the number of palindromes of $n$ with $j$
parts. Previous experience~\cite{6} predicts that the formulas tend to
be more complicated for palindromes, as it is necessary to distinguish
between odd and even $n$, as seen also in Theorem 10 for the total
number of palindromes of $n$.

Another problem is to ask similar questions for partitions of $n$
without 2's. In the proofs of Theorems 5 through 9 we used partitions
in order to count the compositions without 2's. Table~\ref{numparts}
gives the number of partitions of $n$ with no 2's, computed using {\it
Mathematica}. No easy recursion exists to create the partitions of
$n+1$  from those of $n$. Again the corresponding sequence is not yet
listed in~\cite{10}.

\begin{table}[hbt]
\begin{center}
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
 n&	1&	2&	3&	4&	5&	6&	7&	8&	9&	10&	11&	12& 13 & 14\\ \hline
 \pi(n) &	1&	1&	2&	3&	4&	6&	8&	11&	15&	20&	26&	35& 45 & 58\\ \hline
\end{array}
\]
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline
n&	15&	16&	17&	18&	19&	20&	21&	22&	23&	24\\ \hline
\pi(n)&	75&	96&	121&	154&	193&	242&	302&	375&	463&	573\\ \hline

\end{array}
\]
\end{center}
\caption{The number of partitions of $n$ without 2's}
\label{numparts}
\end{table}



\section{Acknowledgements}
The authors would like to thank the anonymous referee for his thorough reading of the manuscript.

\begin{thebibliography}{99}

\bibitem{1}G. E. Andrews, {\it The Theory of Partitions}, Cambridge University Press, 1984.

\bibitem{2}R. Austin and R. K. Guy, Binary sequences without isolated ones, {\it Fibonacci Quart.}, {\bf 16} (1978) 84--86.

\bibitem{3}A. H. Beiler, {\it Recreations in the Theory of Numbers}, Dover Publications, New York, 1964.

\bibitem{4}R. C. Brigham, R. M. Caron, P. Z. Chinn and R. P. Grimaldi, A tiling scheme for the Fibonacci Numbers,  {\it J. Recreational Mathematics}, Volume 28, Number 1 (1996-7)
10--16.

\bibitem{5}P. Z. Chinn, G. Colyer, M. Flashman and E. Migliore,
Cuisenaire rods go to college, {\it PRIMUS}, Vol. II, Number 2 (1992)
118--130.

\bibitem{6}P. Z. Chinn, R. P. Grimaldi and S. Heubach, The frequency of
summands of a particular size in palindromic compositions, to appear in
{\it Ars Combin}.

\bibitem{7}P. Z. Chinn and E. O. Hare, Tiling with Cuisenaire rods, G.
E. Bergum et al. (eds.), {\it Applications of Fibonacci Numbers},
Kluwer Academic Publishers, {\bf 6} (1996) 165--171.

\bibitem{8}R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices,
{\it Linear Algebra Appl.}, {\bf 62} (1984) 113--137.

\bibitem{9}R. P. Grimaldi, Compositions without the summand 1, {\it
Congr. Numer.} {\bf 152} (2001) 33--43.

\bibitem{10}N. J. A. Sloane, editor (2002), {\it The On-Line
Encyclopedia of Integer Sequences},
http://www.research.att.com/~njas/sequences/

\bibitem{W} H.~S.~Wilf, {\em Generatingfunctionology}, $2^{nd}$
edition, Academic Press, 1994.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
05A99 .\ \

\noindent \emph{Keywords:  }
Compositions, palindromes, n-dimensional partitions, pentagonal pyramidal numbers, square numbers, triangle numbers, tilings.\\


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A005251},
\seqnum{A008778},
\seqnum{A002411},
\seqnum{A008779},
\seqnum{A005314},
\seqnum{A000931}, and
\seqnum{A078027}
.)



\vspace*{+.1in}
\noindent
Received January 24, 2003;
revised version received  July 2, 2003.
Published in {\it Journal of Integer Sequences} July 8, 2003.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterlo
o.ca/JIS/}.

\vskip .1in

\end{document}
