
\documentclass[10pt]{article}

\usepackage[dvips]{epsfig}
\usepackage{latexsym}
\usepackage{psfig}
\usepackage{amssymb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{indentfirst}

\newtheorem{definition}{Definition}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{theorem}{Theorem}[section]
\setlength{\parindent}{20pt}
\newcommand{\qed}{\hfill\square\medskip}

\sloppy

\begin{document}

\date{}
\newtheorem{definizione}{Definition}
\newtheorem{osservazione}{Osservazioni}
\newtheorem{proprieta}{Propriet\`a}
\newtheorem{teorema}{Theorem}
\newtheorem{proposizione}{Proposition}
\newtheorem{esempio}{Example}
\newtheorem{lemma}{Lemma}
\newcommand{\proof}{\noindent{\bf Proof.\ }}
\newtheorem{remark}{Remark}
\newtheorem{nota}{Note}
\newtheorem{corollario}{Corollary}

\author{A. Frosini $^*$
\and  S. Rinaldi \thanks{Universit\`a di Siena, Dipartimento di Scienze Matematiche e Informatiche, Pian dei
Mantellini, 44, 53100, Siena, Italy, {\tt [frosini, rinaldi]@unisi.it}.}}

\title{On the sequence A079500 and its combinatorial~interpretations}

\maketitle

\begin{abstract}
In this paper we present some combinatorial structures enumerated by the sequence A079500 in the Sloane
Encyclopedia of Integer Sequences, and determine simple bijections among these structures. Then we investigate
the nature of the generating function of the sequence, and prove that is not differentiably finite.
\end{abstract}

\section{The sequence A079500}

The purpose of the paper is to collect and exploit several
combinatorial properties of the sequence:

$$1,1,2,3,5,8,14,24,43, 77, 140, 256, 472,874,1628,3045,5719, 10780,20388, \ldots $$

The sequence, which we will refer to as $(f_n)_{n\geq 0}$
(sequence A079500 in \cite{sloane}), is defined by the generating
function:

\begin{equation} f(x) = \sum _{n\geq 0} f_n \, x^n= (1-x) \sum _{i\geq 0} \frac{x^i}{1-2x+x^{i+1}}.
\end{equation}

\noindent In \cite{K} R. Kemp proved that $f_n$ is the number of {\em balanced ordered trees} having $n+1$ nodes.
Then in \cite{KR} A. Knopfmacher and N. Robbins proved that $f_n$ is the number of {\em compositions} of the
integer $n$ for which {\em the largest summand occurs in the first position}, and that, as $n \to \infty$

$$ f_n \sim \frac{2^{n}}{n{\mbox{log}2}}(1+\delta(\mbox{log}_2n)), $$

\noindent  where $\delta(x)$ is a continuous periodic function of period $1$, mean zero, and small amplitude of
which the authors determined the Fourier expansion; in the same paper they proved the nice property that the
coefficient $f_n$ is odd if and only if $n=m^2-1$, or $n=m^2$, with $m\geq 1$.

\medskip


In 2001 Marc Le Brun defined the ``numbral  arithmetic" for binary sequences by replacing addition with binary
bitwise inclusive-OR, and multiplication by shift-$\&$-OR (to the authors' knowledge the only references on
numbral arithmetic can be found on the Sloane database \cite{sloane}. For the basic definitions, see sequence
A048888; for further properties see also sequences A57892, A67139, A67150, A67399, A67398). He conjectured that
$\left ( f_n \right )_{n\geq 1}$ counts the number of divisors of the binary expansion of $2^n-1$. The conjecture
was confirmed by Richard Schroeppel in the same year.

Later, the sequence $\left ( f_n \right )_{n\geq 1}$ comes to our attention in the context of the enumeration of
{\em exact polyominoes}, i.e., polyominoes that tile the plane by translation \cite{Gi}. In particular, in
\cite{BFRV} it is proved that $f_n$ is the number of {\em pseudo-square parallelogram polyominoes with flat
bottom} having semi-perimeter equal to $n+1$.

\medskip

Our aim in this paper is to give combinatorial evidence of these facts by showing bijections between the four
classes enumerated by the sequence A079500.

In the last section we study the sequence by an analytical point of view, and investigate the nature of its
generating function $f(x)$, proving that it is not {\em differentiably finite} (or {\em D-finite}) \cite{stan}.

The generating functions of the most common solved models in
mathematical physics are differentiably finite, and such functions
have a rather simple behavior (for instance, the coefficients can
be computed quickly in a simple way, they have a nice asymptotic
expansion, they can be handled using computer algebra). On the
contrary, models leading to non D-finite functions are usually
considered ``unsolvable" (see \cite{Guttmann,R}).

Recently many authors have applied different techniques to prove
the non D-finiteness of models arising from physics or statistics
\cite{BMP,BMR,R}. Guttmann~\cite{Guttmann} developed a numerical
method for testing the ``solvability" of lattice models based on
the study of the singularities of their {\em anisotropic
generating functions}. In many cases the tests allow to state that
the examined model has not a D-finite generating function
\cite{R}.



\subsection{Four classes enumerated by A079500}

In this section we define the four classes of combinatorial
objects that we are going to consider in the paper, and then we
prove, using bijective arguments, that they are enumerated by the
sequence A079500.

\subsubsection{Pseudo-square parallelogram polyominoes}

In the plane  $\Bbb Z \times \Bbb Z$ a {\em cell} is a unit
square, and a {\em polyomino} is a finite connected union of cells
having no cut point. Polyominoes are defined up to translations. A
{\em column} ({\em row}) of a polyomino is the intersection
between the polyomino and an infinite strip of cells whose centers
lie on a vertical (horizontal) line. In a polyomino the {\em
perimeter} is the length of its boundary and the {\em area} is the
number of its cells. For the main definitions and results
concerning polyominoes we refer to \cite{stan}.

A particular subclass of the class of convex polyominoes consists
of  the {\em parallelogram} polyominoes, defined by two lattice
paths that use  north (vertical) and east (horizontal) unitary
steps, and intersect only at their origin and extremity. These
paths are commonly called the {\em upper} and the {\em lower
path}. Without loss of generality we assume that the upper and
lower path of the polyomino start in $(0,0)$. Figure \ref{par1}
depicts a parallelogram polyomino having area 14 and
semi-perimeter 10. Note that for parallelogram polyominoes the
semi-perimeter is equal to the sum of the numbers of its rows and
columns.

\begin{figure}[htb]
\begin{center}
\epsfig{figure=par1.eps} \caption{A parallelogram polyomino, its
upper and lower paths.} \label{par1}
\end{center}
\end{figure}

The boundary of a parallelogram polyomino is conveniently
represented by a {\em boundary word} defined on the alphabet $\{
0,1 \}$, where $0$ and $1$ stand for the horizontal and vertical
step, respectively. The coding follows the boundary of the
polyomino starting from $(0,0)$ in a clockwise orientation. For
instance, the polyomino in Figure~\ref{par1} is represented by the
word $11011010001011100010.$

If $X=u_1\ldots u_k$ is a binary word, we indicate by $\overline{X}$ the mirror image of $X$, i.e., the word
$u_k\ldots u_1$, and  the length of $X$ is $|X|=k.$ Moreover $\left | Y \right | _0$, (resp. $\left | Y \right |
_1$)  indicates the number of occurrences of $0$s (resp. $1$s) in $Y$.\\

Beauquier and Nivat \cite{Gi} introduced the class of {\em pseudo-square} polyominoes, and proved that each
polyomino of this class may be used to tile the plane by translation. Indeed, let $A$ and $B$ be two discrete
points on the boundary of a polyomino $P$. Then  $[A,B]$ and $\overline{[A,B]}$ denote respectively the paths
from A to B on  the boundary of $P$ traversed in a clockwise and counterclockwise way. The  point $A'$ is the
opposite of $A$ on the boundary of $P$ and satisfies $|[A,A']|=|[A',A]|$. A polyomino $P$ is said to be {\em
pseudo-square} if there are four points A,B,A',B' on its boundary such that $B \in [A,A']$,
$[A,B]=\overline{[B',A']}$, and $[B,A']=\overline{[A,B']}$ (see Figure \ref{contile}).

\begin{figure}[h]
\begin{center}
\epsfig{figure=contile.eps} \caption{A pseudo-square polyomino,
its decomposition and a  tiling of the plane determined by the
polyomino.\label{contile}}
\end{center}
\end{figure}

Here we consider the class ${\mathcal {PSP}}$ of parallelogram
polyominoes which are also pseudo-squares (briefly, {\em
psp}-polyominoes) \cite{BFRV}.

\begin{proposition}\label{prop}
If $X\, Y\, \overline{X}\, \overline{Y}$ is a decomposition of the
boundary word of a $psp$-polyomino then:

\item[i)] $XY$ encodes its upper path, and $YX$ its lower path; \item[ii)] $X=1X'1$, $Y=0Y'0$, for some $X',Y'\in
\{0,1\}$; \item[iii)] the decomposition $X\, Y\, \overline{X}\, \overline{Y}$ is unique.
\end{proposition}

\begin{figure}[htb]
\begin{center}
\epsfig{figure=qpex.eps} \caption{A {\em psp}-polyomino, and its
unique decomposition.\label{pqex}}
\end{center}
\end{figure}

\noindent For instance, the polyomino in Figure~\ref{pqex} can be
decomposed as $111101\cdot 0100 \cdot 101111 \cdot 0010$, where
$X=111101$, $Y=0100$.

We call {\em psp}-polyominoes with {\em flat bottom} those {\em
psp}-polyominoes such that the word $Y$ (called the {\em bottom})
is made only of $0$'s (see Figure~\ref{planarbasis}). We denote by
${\mathcal {PSP}}^{-}$ the class of such polyominoes, and by
${\mathcal {PSP}}^{-}_{n,k}$ those having bottom of length $k\geq
1$, and semiperimeter $n+1$. The enumeration problem for the class
${\mathcal {PSP}}^{-}$ is solved in \cite{BFRV}, and here we
recall the useful characterization which leads to such a result:

\begin{proposition}\label{propx}
The word $U \, = \, 1 \, X' \, 1 \, 0^k$, with $k\geq 1$, and
$|U|=n+1$, represents the upper path of a polyomino in ${\mathcal
{PSP}}^{-}_{n,k}$ if and only if $X'$ does not contain any factor
$0^j$, with $j\geq k$.
\end{proposition}

\begin{example}\label{ex1}
{\em The word $110010001110100110001$ represents the upper path of a polyomino in ${\mathcal {PSP}}^{-}_{24,4}$,
as shown in Figure~\ref{planarbasis} (a), while the word $101100000101$ does not encode a polyomino in ${\mathcal
{PSP}}^{-}_{15,4}$ since it contains the factor $00000$ (as shown in Figure~\ref{planarbasis} (b)).

\begin{figure}[htb]
\begin{center}
\epsfig{figure=planarbasis.eps,width=3.5in,clip=}\caption{Examples
of a polyomino in ${\mathcal {PSP}}^{-}_{24,4}$
 (a), and a polygon which is not a polyomino, (b)\label{planarbasis}}
\end{center}
\end{figure}
}
\end{example}

\subsubsection{Balanced ordered trees}

For the basic definitions of the ordered trees we refer to
\cite{stan}. An ordered tree is said to be {\em balanced} if all
its leaves are at the same level. Let ${\cal B}_n$ be the class of
{\em balanced ordered trees} having $n+1$ nodes. In \cite{K} R.
Kemp proves that $\left | {\cal B}_n \right | = f_n$,~$n\geq 0$.

\begin{figure}[htb]
\begin{center}
\epsfig{figure=tre_ps.eps,width=4.5in,clip=} \caption{The eight
balanced ordered trees having $6$ nodes. \label{tre_ps}}
\end{center}
\end{figure}

\subsubsection{Compositions with the largest part in the first position}

For any $n \geq 1$, $k \geq 1$ let ${\cal C}_{n,k}$ be the set of compositions of $n$ having the largest part $k$
in the first position, i.e.,

$$ k+a_1+\ldots + a_h=n, $$

\noindent with $k\geq a_1, \ldots ,a_h \geq 1$, and $h\geq 0$. For
instance:

$$ {\cal C}_{5,2} \; = \; \bigl\{ \; 2+1+1+1, \; 2+2+1, \; 2+1+2 \; \bigr\} .$$

Moreover let ${\cal C}_n= \bigcup _{k=1}^{n} {\cal C}_{n,k}$ be
the set of compositions of $n$ having the largest part in the
first position. For instance:

{\small

$$ {\cal C}_5 = \bigl\{ \, 1+1+1+1+1, 2+1+1+1, 2+2+1, 2+1+2, 3+2, 3+1+1, 4+1, 5 \, \bigl\}.$$

}

\noindent By convention we set $\left | {\cal C}_0 \right |=\left
| {\cal C}_1 \right |=1$. In \cite{KR} A. Knopfmacher and N.
Robbins prove that for any $n\geq 0$, $\left | {\cal C}_n \right |
= f_n$.

\subsubsection{Divisors of $2^n-1$ in numbral arithmetic}

Let $n$ be an integer number, and let $[n]$ be its binary representation. The {\em numbral arithmetic} relies on
the replacing of the standard addition for binary sequences with binary bitwise inclusive-OR. As a consequence,
the multiplication uses the shift-$\&$-OR instead of the standard shift-$\&$-add. As an example, it holds
$$
\begin{array}{lll}
&[3] + [9] &= 1\,1 + 1\,0\,0\,1 = 1\,0\,1\,1 = [11] \\ \\
&[3] \,* \,[9] &= 1\,1
* 1\,0\,0\,1 = 1\,1*1 + 1\,1\,0*0+ 1\,1\,0\,0*0+1\,1\,0\,0\,0*1= \\ \\
& &=1\,1+0\,0\,0+0\,0\,0\,0 +1\,1\,0\,0\,0= 1\,1\,0\,1\,1=[27].
\end{array}
$$

Clearly, the defined addition and multiplication are still
commutative.

We say that $[d]$ {\em divides} $[n]$ if there exists $[e]$ such that $[d] * [e] = [n]$. One can apply the given
definitions to compute the six divisors of $[14]$, i.e., $[1]$, $[2]$, $[3]$, $[6]$, $[7]$, and $[14]$, in order
to immediately relying that the element $[e]$ whose product with $[d]$ is $[n]$ is, in general, not unique.

Let us define $\mathcal{D}_{n}$ to be the set of the divisors of $[2^n-1]$ (i.e., the binary sequence $1^n$), and
$\mathcal{D}_{n,k}$ the divisors of $[2^n-1]$ having length $k$. We will show that, for each $n>0$, the
cardinality of the set $\mathcal{D}_{n}$ is $f_{n}$, by bijectively prove that
$|\mathcal{D}_{n,k}|=|\mathcal{PSP}^-_{n,n-k+1}|$. In the following table the divisors of $[2^n-1]$, for
$n=1,\dots,4$, are computed.

\bigskip

\hspace{-1cm}\begin{tabular}{c|cccc}
{\em n} & $[2^n-1]$ &divisors of $[2^n-1]$&$[\frac{4^n-1}{3}]$ & divisors of $[\frac{4^n-1}{3}]$ \\
\\
  \hline
\\
  1 &1  &\{1\} & 1 & \{1\} \\
\\
  \hline
\\
  2 &1\, 1 &$\left\{\,1 \,,\, 1\,1 \right\}$&1\, 0\, 1  &$\left\{\,1 \,,\, 1\,0\,1 \right\}$ \\
\\
  \hline
\\
  3 & 1\, 1\, 1 &\{\, 1 \,,\, 1\,1 \,,\, 1\,1\,1 \} & 1\,0\, 1\,0\, 1 & \{\, 1 \,,\,
  1\,0\,1 \,,\, 1\, 0\, 1\,0\,1 \} \\
\\
    \hline
\\
  4 & 1\, 1\, 1\, 1 &$\left\{\begin{array}{c}
  1 \,,\, 1\,1 \,,\, 1\,1\,1\\
  1\,0\, 1 \,,\, 1\,1\,1\,1
  \end{array} \right\}$ & 1\,0\, 1\,0\, 1\, 0\,1 & $\left\{\begin{array}{c}
  1 \,,\, 1\,0\, 1 \,,\, 1\,0\, 1\, 0\, 1\\
  1\,0\, 0\,0\, 1 \,,\, 1\, 0 \,1\, 0 \, 0\, 1\,0\, 1
  \end{array} \right\}$\\
\end{tabular}

\bigskip

For the same values of $n$, there are also shown the numbers
$[\frac{4^n-1}{3}]$ (sequence A002450 in \cite{sloane}) and their
correspondent divisors. This sequence has two interesting
combinatorial interpretations: for $n>0$, it counts both the
degree $(n-1)$ numbral power of $5$, and the partial sums of the
first $(n-1)$ powers of $4$, and it is also strictly connected
with the sequence A079500, as stated in the following:

\begin{proposition}
The binary sequence $x_1\,x_2\,\dots \, x_k$ is a divisor of
$[2^n-1]$ if and only if the binary sequence $x_1\,0\,x_2\, 0 \,
\dots \, 0\, x_k$ is a divisor of $[\frac{4^n-1}{3}]$.
\end{proposition}


\subsection{Bijective results}

At the very beginning we easily prove that the number of $psp$-polyominoes having semiperimeter $n+1$ and flat
bottom, say ${\mathcal {PSP}}^{-}_{n}$, is $f_n$. By Proposition~\ref{propx} it follows that, for any fixed
$k\geq 1$, the generating function of the $psp$-polyominoes having flat bottom of length $k$ is
\begin{equation} f_k(x)=\frac{x^{k}}{\ 1-x-x^2-x^3-\ldots
-x^{k}},\label{ricorda}
\end{equation}
hence the generating function of ${\mathcal {PSP}}^-$ is given by the sum
\begin{equation} 1 \, + \, \frac{1}{x^2} \sum _{k\geq 1} f_k(x)= (1-x)
\sum_{i\geq 0} \frac{x^i}{1-2x+x^{i+1}}, \label{sw}
\end{equation}

\noindent i.e., the generating function of A079500.

\begin{figure}[htb]
\begin{center}
\epsfig{figure=ps.eps,width=5in,clip=} \caption{The eight {\em
psp}-polyominoes with flat bottom having semi-perimeter equal to
$6$. \label{ps}}
\end{center}
\end{figure}

\subsubsection{A bijection between ${\cal B}_n$ and ${\mathcal {PSP}}^-_{n}$}

We prove bijectively that $\left | {\cal B}_n \right |= \left | {\mathcal {PSP}}^-_{n} \right |$. We do this by
establishing a bijection

$$ \Theta : {\cal B}_{n,k}  \rightarrowtail {\mathcal {PSP}}^{-}_{n,k}.$$

where ${\cal B}_{n,k}$ denotes the set of trees in ${\cal B}_n$ having height equal to $k$, thus proving that
this class is counted by $f_k(x)$, i.e., the generating function in~(\ref{ricorda}), for any $k\geq 1$.

Let us start by observing that, for any $k \geq 1$, each polyomino
in ${\mathcal {PSP}}^{-}_{n,k}$ has all the rows of length $k$.
Let $T \in {\cal B}_{n,k}$, and let $e_1, \ldots ,e_h$, $h \geq 1$
be the leaves of $T$, from left to right, and for any $i=1, \ldots
,h-1$ let $n_i$ be the level of node in $T$ which is father of the
leaves $e_i$ and $e_{i+1}$, and has minimal level (clearly, $0
\leq n_i \leq k-1$). Now $\Theta (T)$ is defined as a polyomino
with $h$ rows, each one with exactly $k$ cells, and such that for
any $i=1, \ldots ,h-1$ the $i+1$ row is placed just above the
$i$th row, and moved on the right by $k-n_i-1$ cells (see
Figure~\ref{trebal}).

\medskip

\begin{figure}[htb]
\begin{center}
\epsfig{figure=trebal.eps,width=4.5in,clip=} \caption{The
bijection between trees in ${\cal B}_{n,k}$, (a), and polyominoes
in ${\mathcal {PSP}}^{-}_{n,k}$,~(b). \label{trebal}}
\end{center}
\end{figure}

\medskip

The reader can easily check that $\Theta (T)\in{\mathcal
{PSP}}^{-}_{n,k}$, and that $\Theta$ is a bijective function;
moreover from the definition of $\Theta$ it follows  that the
number of rows of $\Theta (T)$ is equal to the number of leaves of
$T$ (see Figure~\ref{balan}).

\medskip

\begin{figure}[htb]
\begin{center}
\epsfig{figure=balan.eps,width=3in,clip=} \caption{A balanced tree
of height $3$ and the corresponding polyomino with bottom of
length $3$. \label{balan}}
\end{center}
\end{figure}

\subsubsection{A bijection between ${\mathcal {PSP}}_{n}^-$ and ${\cal C}_n$}

In this paragraph we will describe a bijection between ${\mathcal {PSP}}^{-}_{n,k}$ and ${\cal C}_{n,k}$, for any
$k\geq 1$

$$ \Delta : {\mathcal {PSP}}^{-}_{n,k}  \rightarrowtail {\cal C}_{n,k} .$$

Let us consider a polyomino $P$ in ${\mathcal {PSP}}^{-}_{n,k}$, and let the word encoding its upper path be

$$ 1 \; 0^{e_1} \; 1 \; 0^{e_2} \; \ldots \; 1 \; 0^{e_h} \; 1 \; 0^k, $$

\noindent with $ e_1 + \ldots + e_h + (h+1) +k =n+1$ and, by Proposition~\ref{propx}, $e_i < k$, for $i=1, \ldots
,h$. Let us define

$$ \Delta (P)= k + ({e_1}+1) + \ldots + ({e_h}+1). $$

Clearly $\Delta (P)$ is a composition of $k + {e_1} + \ldots +
{e_h} +h=n$ having $k$ as leading summand, thus $ \Delta (P) \in
{\cal C}_{n,k}$. Moreover, if the polyomino $P$ has $h$ rows,
$h\geq 1$, then the corresponding composition $\Delta (P)$ has $h$
parts.

For instance, the polyomino in Figure~\ref{balan} (with semi-perimeter $13$, bottom of length $3$, and $6$ rows)
is represented by the word $1010110011000$, i.e., $10^110^110^010^210^010^3, $ and is mapped through $\Delta$ in
the composition $3+2+2+1+3+1$ of $12$, with greatest summand $3$ and having $6$ parts. It is easy to check that
$\Delta$ is a bijection.

\bigskip

The table below shows the correspondences between several
parameters in polyominoes of ${\mathcal {PSP}}^-$, balanced
ordered trees, and compositions with the largest summand in the
first position.

\bigskip



\hspace{-.9cm}
\begin{tabular}{c|c|c|c}
&&\\
  ${\mathcal {PSP}}^-$ &semi-perimeter + 1 &length of the bottom &number of rows \\
  &&\\
  \hline
&&\\
  ${\cal B}$ &number of nodes +1  &height of the tree &number of leaves \\
&&\\
  \hline
&&\\
  ${\cal C}$ &sum of the terms &leading summand &number of summands \\
  &&\\
\end{tabular}

\bigskip


\subsubsection{A bijection between ${\cal D}_{n}$ and ${\mathcal {PSP}}_{n}^-$ }

We achieve $|{\cal D}_{n}|=|{\mathcal {PSP}}_{n}^-|$ by defining a bijection $\Omega$ between ${\cal D}_{n,k}$
and ${\mathcal {PSP}}_{n,n-k+1}^-$. The following characterization of the elements of ${\cal D}_{n}$ is needed.

\begin{lemma}\label{lem1}
For each $n,d > 0$, it holds that $[d]$ is a divisor of $[2^n-1]$
if and only if it ends with the digit $1$, and it does not contain
any subsequence of 0s having length greater than $n-k$, with $k$
being the length of $[d]$.
\end{lemma}

\begin{proof}
($\Rightarrow$) Let $[d]=d_1\,d_2 \, \dots \, d_k$,
$[e]=e_1\,e_2\, \dots \, e_{n-k+1}$, and $[d]\,*\,
[e]=[2^n-1]=1^n$ (where the power notation stands for repetition).
By definition, it holds that
$$
\begin{array}{l}
[d]\,*\, [e] = d_1 \, \dots \, d_{k-1}\, 0 \, *\, e_{n-k+1} \,+\,
\dots \, + \, d_1 \, \dots \, d_{k-1}\, 0 \, 0^{n-k}\,*\, e_{1} =
p_1 \, \dots \, p_{n}.
\end{array}
$$
We proceed by contradiction and we assume that $d_k=0$ or that
there exists in $[d]$ a sequence of 0s having length $n-k+1$.

In the first case, it turns out that the digit $p_{n}$ has value 0 since it is the sum (i.e., the inclusive-OR)
of $n-k+1$ digits of value 0, and this is not possible.

In the second case, we assume that $[d]=1\, d_2 \, \dots \,
d_{k-1}\, 1$ contains the sequence of 0s $d_h\,\dots \,
d_{h+n-k}$. By definition, the digit $p_{n-h}$ of the product
$[d]\,*\, [e]$ has value $0$, since it is the sum of $n-k+1$ bits
having value 0. Again this is not possible by the hypothesis
$[d]\, * \, [e]=1^n$.

($\Leftarrow$) Let us consider the binary sequence
$[e]=1^{n-k+1}$. Since $[d]=1\, d_2 \, \dots \, d_{k-1} \, 1$ does
not contain any sequence of 0s having length greater than $n-k$,
then each digit $p_1\, \dots \, p_{n}$ of the product
$[d]\,*\,[e]$ is the sum of $n-k+1$ digits at least one of them
having value $1$, so it has value $1$. The thesis $[d]\, * \,
[e]=1^n$ is achieved. $\qed$
\end{proof}

We define the bijection $$\Omega: {\cal D}_{n,k}\rightarrowtail
{\mathcal {PSP}}_{n,n-k+1}^-$$ as follows: to each divisor $[d]=1
\, d_2 \, \dots \, d_{k-1} \, 1$ of $[2^n-1]$ we associate a
$psp$-polyomino whose upper path is represented by $1 \, d_2 \,
\dots \, d_{k-1} \, 1 \, 0^{n-k+1}$.

By Lemma~\ref{lem1}, each divisor of $[2^n-1]$ has no subsequences
of 0s of length greater than $n-k$, so, by
Proposition~\ref{propx}, it encodes an upper path of a
$psp$-polyomino having the bottom of length greater than $n-k+1$.
The minimal possible semi-perimeter for such polyominoes is $n+1$,
as desired. On the contrary, the word coding the upper path of a
polyomino in ${\mathcal {PSP}}_{n,n-k+1}^-$ belongs to ${\cal
D}_{n,k}$, since it is a binary sequence of the type $w_1\,
0^{n-k+1}$, with $w_1$ starting and ending with the digit 1, and
containing no sequences of 0s of length greater than $n-k$.

Figure~\ref{corr} shows the correspondence between the eight
divisors of $[2^5-1]$ and the eight $psp$-polyominoes in
${\mathcal {PSP}}_{5}^-$.

\medskip

\begin{figure}[htb]
\begin{center}
\epsfig{figure=ps3.eps,width=5in,clip=} \caption{Each upper path of an element in ${\mathcal {PSP}}_{5}^-$ is
associated with the correspondent divisor of $[2^n-1]$ in ${\mathcal {D}}_{5}$. \label{corr}}
\end{center}
\end{figure}


%The table below shows the correspondences between several
%parameters in polyominoes of ${\mathcal {PSP}}^-$, balanced
%ordered trees, compositions with the largest summand in the first
%position, and divisors of the sequences $1^n$.
%
%\bigskip
%
%
%
%\hspace{-.9cm}
%\begin{tabular}{c|c|c|c}
%  ${\mathcal {PSP}}^-$ &semi-perimeter + 1 &length of the bottom &number of rows \\
%  \hline
%  ${\cal B}$ &number of nodes +1  &height of the tree &number of leaves \\
%  \hline
%  ${\cal C}$ &sum of the terms &leading summand &number of summands \\
%  \hline
%  ${\cal D}$ &power of 2 -1 &length of a divisor -1&number of 1s in a divisor \\
%\end{tabular}



\subsection{Nature of the generating function}

Finally, for the sake of completeness, we would like to spend a few words on investigating the nature of the
generating function $f(x)$ of the sequence A079500.

Let us start by recalling that a formal power series $u(x)$ with coefficients in $\mathbb C$ is said to be {\em
differentiably finite} (briefly, {\em D-finite}) if it satisfies a (non-trivial) polynomial equation

$$ q_m(x) u^{(m)}+q_{m-1}(x) u^{(m-1)}+ \ldots +q_1(x) u' +q_0(x)u = q(x), $$

\noindent with $q_0(x), \ldots ,q_m(x) \in {\mathbb C} [x]$, and $q_m(x) \neq 0$ (\cite{stan}, Ch. 6).

Every algebraic series is D-finite, while the converse does not hold. For example, the generating function $u(x)$
of the sequence ${2n \choose n}^2$ is D-finite, since it satisfies the linear differential equation

$$ 4u(x)+(32x-1)u'(x)+x(16x-1)u''(x)=0, $$

\noindent while $u(x)$ is not algebraic, as proved for the first
time in \cite{F}.

\medskip

Our aim in this section is to prove that the generating function
of the sequence A079500,

$$ f(x) = (1-x) \sum _{i\geq 0} \frac{x^i}{1-2x+x^{i+1}} $$

\noindent is not differentiably finite.

\medskip

In order to do this we can use the very simple argument, arising
from the classical theory of linear differential equation, that a
D-finite power series of a single variable has only a finite
number of singularities. Thus we can reach our goal by proving
that $f(x)$ has infinitely many poles. For instance, the function
$1 / \cos (x)$ is not D-finite, since it has an infinite number of
singularities.

\medskip

We point out that this ``criterion" was applied by Flajolet in \cite{F} to prove that the language

$$ \left \{ \, a^n b v_1 a^n v_2 \, : \, n\geq 1, v_1, v_2 \in \{ a,b \}^* \, \right \} $$

\noindent is a context-free inherently ambiguous language.

\medskip

We reach our goal by adapting Flajolet's proof to our case. For each $i\geq 1$, let $P_i=1-2x+x^{i+1}$. For
$|x|<1$, it is easy to check that each $P_i$ has a real zero $\rho _i$ such that $\frac{1}{2} < \rho_i < 1$. By
the Principle of the Argument and by the related Rouch\'e's Theorem we are able to state that for a sufficiently
small $x$, say $|x|<\frac{3}{4}$, $\rho_i$ is the unique zero of $P_i$. Thus we have:

\begin{enumerate}
\item if $i>j$ then $\rho_i < \rho_j$; \item $\lim _{i\to \infty}  \rho_i = \frac{1}{2}$.
\end{enumerate}

Hence, for any $x\neq \rho_i, \frac{1}{2}$, and $|x|<\frac{3}{4}$ the series $\sum _{i \geq 0} \frac{1}{P_i}$ is
convergent. As a conclusion, $f(x)$ is analytic in $|x|<\frac{3}{4}$ except for finitely many poles $\rho_i$
which accumulate in $\frac{1}{2}$, thus it is not D-finite.

It is interesting to observe that, while parallelogram polyominoes are one of easiest (and most frequently
treated in literature) classes of polyominoes, and have an algebraic generating function according to the
semi-perimeter, {\em psp}-polyominoes with a flat bottom (which are a rather simple type of parallelogram
polyominoes) are not {\em D-solvable}.

\medskip

\paragraph{On the nature of a class of languages.} The result
in the present section suggests some further considerations
regarding the class ${\cal PSP^-}$ of {\em psp}-polyominoes with
flat bottom.

By Proposition~\ref{propx} we have that the class of the polyominoes having bottom of length $k\geq 1$ can be
suitably encoded by means of the regular language $\ell _k$ defined by the unambiguous regular expression

$$ 1 \, \bigl( \, 1 \cup 01 \cup 001 \cup \ldots \cup 0^{k-1}1 \, \bigr)^* \, 0^k, $$

and that consequently the class ${\cal PSP^-}$ can be encoded by
means of the language $\ell = \bigcup_{k\geq 1} \ell _k$.

A classical result by Chomsky and Sch\"uetzenberger~\cite{CS} states that the generating function of an
unambiguous context-free language is algebraic. But, as we have proved in the present section, the generating
function of $\ell$ (i.e., $x^2 f(x)$) is not algebraic (actually, not even $D$-finite), thus $\ell$ is an
{inherently ambiguous} language.

\begin{thebibliography}{13}

\bibitem[BN]{Gi}
D. Beauquier, M. Nivat, On Translating one Polyomino to Tile the Plane, {\it Discrete Comput. Geom. } {\bf 6}
(1991) 575--592.

\bibitem[BMP]{BMP}
M. Bousquet-M\'elou, Marko Petkovsek, \newblock{\rm Walks confined in a quadrant are not always D-finite},
\newblock{\it Theoret. Comput. Sci.} {\bf 307} (2003) 257-276.

\bibitem[BMR]{BMR}
M. Bousquet-M\'elou, A. Rechnitzer, \newblock{\rm The site-perimeter of bargraphs}, \newblock{\it Advances in
Applied Mathematics}, {\bf 31} (2003) 86-112.

\bibitem[BFRV]{BFRV}
S. Brlek, A. Frosini, S. Rinaldi, L. Vuillon, \newblock{\rm Tilings by translation: enumeration by a rational
language approach,} {\it Electronic Journal of Combinatorics} {\bf 13} (1) (2006) R15.

\bibitem[CS]{CS}
N. Chomsky, M. P. Sch\"utzenberger,
\newblock The algebraic theory of context-free languages,
\newblock In {\em  P. Braffort and D. Hirschberg (Eds.), Computer Programming and
Formal Systems}, (1963) 118-161 North-Holland, Amsterdam.

\bibitem[K]{K}
R. Kemp, \newblock{\rm Balanced ordered trees,} \newblock{\it Random Structures and Alg.} {\bf 5} (1994) pp.
99-121.

\bibitem[KR]{KR}
A. Knopfmacher, N. Robbins, \newblock{\rm Compositions with parts constrained by the leading summand,} {\it Ars
Combinatorica}, {\bf 76} (2005), 287–295.

\bibitem[F]{F}
P. Flajolet, \newblock{\rm Analytic models and ambiguity of context-free languages}, \newblock{\it Theoret.
Comput. Sci.} {\bf 49} (1987) 283--309.

\bibitem[G]{Guttmann}
A. J. Guttmann, {\rm Indicators of solvability for lattice models}, {\it Discrete Mathematics} {\bf 217} (2000)
167--189.

\bibitem[R]{R}
A. Rechnitzer, \newblock{\rm Haruspicy and anisotropic generating functions}, \newblock{\it Advances in Applied
Mathematics}, {\bf 30} (2003) 228-257.

\bibitem[Sl]{sloane}
N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at {\small $\langle$
http://www.research.att.com/$\sim$njas/sequences/$\rangle$}.

\bibitem[S]{stan}
R. P. Stanley,
\newblock {\it Enumerative Combinatorics, } \newblock {\rm Vol.2, Cambridge University Press,} Cambridge (1999).

\end{thebibliography}


\end{document}
