\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsthm}

\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{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}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf On the Density of Languages \\
\vskip .1in
Representing Finite Set Partitions \footnote{Work partially funded by
Funda\c{c}\~ao para a Ci\^encia e Tecnologia (FCT) and Program POSI.}
}
\vskip 1cm
\large
Nelma Moreira and Rog\'erio Reis\\
DCC-FC \& LIACC \\
Universidade do Porto \\
R. do Campo Alegre 823 \\
4150 Porto \\
Portugal  \\
\href{mailto:nam@ncc.up.pt}{\tt nam@ncc.up.pt}\\
\href{mailto:rvr@ncc.up.pt}{\tt rvr@ncc.up.pt}\\
\end{center}

\vskip .2 in
\begin{abstract}
We present a family of regular languages representing
partitions of a set of $n$ elements in less or equal $c$ parts.  The
density of those languages is given by partial sums of Stirling
numbers of second kind for which we obtain explicit formulas.  We
also determine the limit frequency of those languages. This work was
motivated by computational representations of the configurations of
some numerical games.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

%\usepackage{epsfig}
%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{dsfont}
%\usepackage{listings}

%\newtheorem{theorem}{Theorem}
%\newtheorem{prop}{Proposition}
%\newtheorem{lemma}{Lemma}

\newenvironment{induction}[2]{
    \begin{description}
    \item[{\em Base.}] #1
    \item[{\em Induction.}] #2}
    {\end{description}}

\newcommand{\Nplus}[1]{\mathbb{N}_{#1}}


\section{The languages $L_c$}

Consider a game where natural numbers are to be placed, by increasing
order, in a fixed number of columns, subject to some specific
constraints. In these games column order is irrelevant. Numbering
the columns, game configurations can be seen as sequences of column
numbers where the successive integers are placed. For instance, the
string
$$11213$$
\noindent stands for a configuration where $1$, $2$, $4$ were placed
in the first column, $3$ was placed in the second and $5$ was placed
in the third.  Because column order is irrelevant, and to have a
unique representation for each configuration, it is not allowed to
place an integer in the $k$th column if the $(k-1)$th is still empty,
for any $k> 1$. Blanchard and al. \cite{blanchard04:_partit} and Reis
and al. \cite{reis04:_educat} used this kind of representation to
study the
possible configurations of sum-free games.


Given $c$ columns, let $\Nplus{c}=\{1,\ldots,c\}$. We are interested
in studying the set of game configurations as strings in
$(\Nplus{c})^{\star}$, i.e., in the set of finite sequences of elements of
$\Nplus{c}$. Game configurations can be characterised by the following language
$L_c\subset (\Nplus{c})^{\star}$:

\begin{eqnarray*}
L_c&=&\{a_1a_2\cdots a_k\in(\Nplus{c})^{\star}\mid \forall i\in\Nplus{k}, a_i\leq \max\{a_1,\ldots,a_{i-1}\}+1\}.
\end{eqnarray*}

\smallskip

For $c=4$, there are only $15$ strings in $L_4$ of length $4$, instead
of the total possible $256$ in $(\Nplus{4})^4$:
$$
\begin{tabular}{ccccc}
1111&
1112&
1121&
1122&
1123\\
1211&
1212&
1213&
1221&
1222\\
1223&
1231&
1232&
1233&
1234
\end{tabular}
$$


Given a finite
set $\Sigma$, a regular expression (r.e.) $\alpha$ over $\Sigma$
represents a (regular) language $L(\alpha)\subseteq \Sigma^\star$ and
is inductively defined by: $\emptyset$ is a r.e and
$L(\emptyset)=\emptyset$; $\epsilon$ (empty string) is a r.e and
$L(\epsilon)=\{\epsilon\}$; $a\in \Sigma$ is a r.e and $L(a)=\{a\}$;
if $\alpha_1$ and $\alpha_2$ are r.e., $\alpha_1 + \alpha_2$,
$\alpha_1 \alpha_2$ and $\alpha_1^\star$ are r.e., respectively with
$L(\alpha_1 + \alpha_2)=L(\alpha_1)\cup L(\alpha_2)$,
$L(\alpha_1\alpha_2)=L(\alpha_1)L(\alpha_2)$ and
$L({\alpha_1}^\star)=L(\alpha_1)^\star$~, where we assume the usual
precedence of the operators (see
\cite{hopcroft00:_introd_autom_theor_languag_comput}). 
A regular expression $\alpha$ is unambiguous if for each $w\in
L(\alpha)$ there is only one path through $\alpha$ that matches $w$.


\begin{theorem}
For all $c\geq 1$, $L_c$ is a regular language.  
\end{theorem}

\begin{proof}
  For $c=1$, we have $L_1=L(11^\star)$. We define by induction on $c$,
  a family of regular expressions:
  \begin{eqnarray}
    \alpha_1&=&11^\star,\\
\alpha_c&=&\alpha_{c-1}+\prod_{j=1}^{c}j(1+\cdots+j)^\star.
  \end{eqnarray}
It is trivial to see that
\begin{equation}\label{rc}
\alpha_c=\sum_{i=1}^{c}\prod_{j=1}^{i}j(1+\cdots+j)^\star.
\end{equation}
\noindent For instance, $\alpha_4$ is
{\small
$$11^\star+11^\star 2(1+2)^\star+11^\star 2(1+2)^\star
3(1+2+3)^\star+
11^\star 2(1+2)^\star 3(1+2+3)^\star4(1+2+3+4)^\star.$$
}
\noindent It is also obvious that  $L(\alpha_{c-1})\subseteq L(\alpha_c)$, for
$c>1$. For any $c\geq 1$, we prove that
$$L_c=L(\alpha_c).$$
\begin{description}
\item[$L_c\supseteq L(\alpha_c)$:]
If $x\in L(\alpha_c)$ it is obvious that $x\in L_c$.

\item[$L_c\subseteq L(\alpha_c)$:]
By induction on the length of $x\in L_c$:
If $|x|=1$ then $x\in L(\alpha_1)\subseteq L(\alpha_c)$. Suppose that for any
string $x$ of length $\leq n$, $x\in  L(\alpha_c)$. Let $|x|=n+1$ and
$x=ya$, where $a\in \Nplus{c}$ and $y\in L(\alpha_c)$. 
%Obviously $x\in L(\alpha_c)$. 
Let $c^\prime=\max\{a_i\mid a_i\in y\}$. If $c^\prime=c$, obviously
  $x\in L(\alpha_c)$.
If $c^\prime< c$, then $y\in   L(\alpha_{c^\prime})$, and $x\in
   L(\alpha_{c^\prime+1})\subseteq  L(\alpha_{c})$.
\end{description}
\end{proof}

\section{Counting the strings of $L_c$}
\label{clc}
The density of a language L over a finite set $\Sigma$, $\rho_{L}(n)$, is the
number of strings of length $n$ that are in $L$, i.e.,

 $$\rho_{L}(n)=|L\cap \Sigma^{n} |.$$

In particular, the density of $L_c$ is 

 $$\rho_{L_c}(n)=|L_c\cap \Nplus{c}^{n} |.$$
 
 Using generating functions we can determine a closed form for
 $\rho_{L_c}(n)$. Recall that, a (ordinary) generating function for a sequence
 $\{a_n\}$ is a formal series~(see~\cite{graham94:_concr_mathem})
 $$G(z)=\sum_{i=0}^{\infty} a_nz^n.$$
 If $A(z)$ and $B(z)$ are generating functions for the density functions
 of the languages represented by unambiguous regular expressions 
 $A$ and $B$, and $A+B$, $AB$ and $A^\star$ are also unambiguous r.e.,
 we have that $A(z)+B(z)$, $A(z)B(z)$ and {$\displaystyle
   \frac{1}{1-A(z)}$}, are the generating functions for the density
 functions of the corresponding languages
 (see~\cite{sedgewick96:_analy_algor}, page 378).
 
 As $\alpha_c$ are unambiguous regular expressions, from (\ref{rc}), we
 obtain the following  generating function for $\{\rho_{L_c}(n)\}$:

\begin{equation*}
  T_c(z)=\sum_{i=1}^{c}{\prod_{j=1}^{i}{\frac{z}{(1-jz)}}}=\sum_{i=1}^{c}{\frac{z^i}
{\prod_{j=1}^{i}{(1-jz)}}}.
\end{equation*}

Notice that $$S_i(z)=\frac{z^i} {\prod_{j=1}^{i}{(1-jz)}}$$
are the
generating functions for the Stirling numbers of second kind 
$$S(n,i)=\frac{1}{i!}\sum_{j=0}^{i-1}(-1)^j\binom{i}{j}(i-j)^n,$$
which are, for each $n$, the number of ways of partitioning a set of $n$ elements into $i$
nonempty sets (see~\cite{graham94:_concr_mathem} and \seqnum{A008277}).

Then, a closed form for the
density of $L_c$,
$\rho_{L_c}(n)$, is given by

\begin{equation}
  \label{eq:rlc}
  \rho_{L_c}(n)=\sum_{i=1}^{c}{S(n,i)},
\end{equation}

i.e., a partial sum of Stirling numbers of second kind.

In Table~\ref{tab:dc} we present the values of $\rho_{L_c}(n)$, for
$c=1..8$ and $n=1..13$. For some sequences, we also indicate the
corresponding number in Sloane's On-Line Encyclopedia of Integer
Sequences~\cite{sloane03:_encyc_integ_sequen}. The closed forms were
calculated using the Maple  computer algebra system~\cite{heck03:_introd_maple}.

From expression~(\ref{eq:rlc}), it is also easy to see that
\begin{theorem}
$$\lim_{c\rightarrow\infty} \rho_{L_c}(n)=B_n,$$
where $B_n$ are the
Bell numbers, i.e., for each $n$, the number of ways a set of $n$
elements can be partitioned into nonempty subsets.
\end{theorem}
\begin{proof}
  Bell numbers, $B_n$,  can be defined by the sum
$$B_n=\sum_{i=1}^{n}S(n,i).$$

And, as $S(n,i)=0$ for $i > n$, we have
\begin{eqnarray*}
\lim_{c\rightarrow\infty}\rho_{L_c}(n)&
=&\sum_{i=1}^{n}{S(n,i)}+\lim_{c\rightarrow\infty}\sum_{i=n+1}^{c}{S(n,i)}\;=\;B_n.
\end{eqnarray*}
\end{proof}

In Table~\ref{tab:dc}, for each  $c\geq 1$, the subsequence for $n\leq
c$ coincides with the first $c$ elements of $B_n$
(\seqnum{A000110}).
 

\begin{table}[htbp]
  \centering
{\small $$
 \begin{array}[c]{|l|l|c|}\hline
$c$&{\displaystyle \rho_{L_c}(n)}&\text{OEIS}
\\\hline&&
\\1&1&\\&&\\
&1, \,1, \,1, \,1, \,1, \,1, \,1,
\,1,\,1,\,1,\,1,\,1,\,1,\,1,\ldots&\\\hline&&\\
2&{\displaystyle\frac{1}{2}\, 2^{n}}&\\&&\\
&1,\,2,\,4,\,8,\,16,\,32,\,64,\,128,\,256,\,512,\,1024,\,2048,\,4096,\,8192,\ldots&\\\hline&&\\
3&{\displaystyle \frac{1}{6}\,3^n\, +\, \frac{1}{2}}&\\&&\\
&1, \,2, 
\,5, \,14, \,41, \,122, \,365, \,1094, \,3281, 
\,9842, \,29525, \,88574, \,265721,\ldots&\seqnum{A007051}\\\hline&&\\
4&{\displaystyle \frac{1}{24}\,{4^n}\, +\, \frac{1}{4}\, 2^n +
  \frac{1}{3}}&\\&&\\
&1, \,2, \,5, \,15, \,51, \,187, \,715, \,2795,\,11051, 
\,43947, \,175275, \,700075, \,2798251,\ldots&\seqnum{A007581}
\\\hline&&\\
5&{\displaystyle \frac {1}{120}  }\,5^{n} +
{\displaystyle \frac {1}{12}} \,3^{n} + {\displaystyle 
\frac {1}{6}} \,2^{n} +  {\displaystyle  \frac {3}{8}}
&\\&&\\
&1, \,2, \,5, \,15, \,52, \,202, \,855, \,3845,  \,18002,\,86472, \,422005, \,2079475, \,10306752, \ldots&\seqnum{A056272}\\\hline&&\\
6&{\displaystyle \frac {1}{720}} \,6^{n} + 
{\displaystyle \frac {1}{48}} \,4^{n} + 
  {\displaystyle \frac {1}{18}} \,3^{n}+
 {\displaystyle \frac {3}{16}} \,2^{n} +
{\displaystyle \frac {11
}{30}}&
\\&&
\\
 &1, \,2, \,5, \,15, \,52, \,203, \,876,
\,4111,\,20648, 
\,109299, \,601492, \,3403127, \,19628064,\ldots&\seqnum{A056273}
\\\hline&&\\
7&{\displaystyle \frac {1}{5040}} \,7^{n} + {\displaystyle 
\frac {1}{240}} \,5^{n} +  {\displaystyle \frac {1}{72}} \,4^{n}+
 {\displaystyle \frac {1
}{16}} \,3^{n} +
{\displaystyle \frac {11}{60}} \,2^{n} +
 {\displaystyle \frac {53}{144}}  
&
\\&&\\
&1, \,2, \,5, \,15, \,52, \,203, \,877, \,4139, \,21110, 
\,115179, \,665479, \,4030523, \,25343488,\ldots &\seqnum{A099262}
\\\hline&&\\
8& {\displaystyle \frac {1}{40320}} \,8^{n} + {\displaystyle 
\frac {1}{1440}} \,6^{n} + {\displaystyle \frac {1}{360}} \,5^{n}
 + {\displaystyle \frac {1}{64}} \,4^{n}
 + {\displaystyle \frac {11}{180}} \,3^{n}
 + {\displaystyle \frac {53}{
288}} \,2^{n} +
{\displaystyle \frac {103}{280}} 
&\\&&\\
&1, \,2, \,5, \,15, \,52, \,203, \,877, \,4140, \,21146, 
\,115929, \,677359, \,4189550, \,27243100,\ldots&\seqnum{A099263}\\\hline
\end{array}
$$ }
\caption{Density functions of $L_c$, for $c=1..8$.}\label{tab:dc}
  \end{table}
 
%\section{Explicit closed formulas for partial sums of $S(n,i)$}

\medskip

Moreover, we can express~$\rho_{L_c}(n)$, and then the partial sums of
Stirling numbers of second kind, as a generic
linear combination of $n$th powers of $k$, for $k\in \Nplus{c}$. Let
$S^j(n,i)$ denote the $j$th term in the summation of a Stirling number
$S(n,i)$, i.e.,

$$S^j(n,i)=\frac{1}{i!}(-1)^j\binom{i}{j}(i-j)^n.$$

\begin{lemma} For all $n$ and $0 \le i\le n$,
  \begin{equation}
    \label{eq:s0s1}
    S^0(n,i)=-S^1(n,i+1).
  \end{equation}
\end{lemma}
\begin{proof}
  \begin{eqnarray*}
S^1(n,i+1)&=&\frac{1}{(i+1)!}(-1)\binom{i+1}{1}i^n
\;=\;(-1)\frac{1}{i!}i^n \;=\;-S^0(n,i).
  \end{eqnarray*}
\end{proof}

Applying~(\ref{eq:s0s1}) in the summation~(\ref{eq:rlc}) of
 $\rho_{L_c}(n)$, each term
$S(n,i)$ simplifies the subterm $S^1(n,i)$ with the subterm
 $S^0(n,i-1)$, for $i\geq 2$. We obtain
 \begin{eqnarray*}
  \rho_{L_1}(n)&=&S^0(n,1),\\
  \rho_{L_2}(n)&=&S^0(n,2),\\
  \rho_{L_c}(n)&=&S^0(n,c)+\sum_{i=3}^{c}
\sum_{j=2}^{i-1}S^j(n,i),
\hspace{1cm}\text{ for } c>2;\\
%  \rho_{L_c}(n)&=&S^0(n,c)+\sum_{j=2}^{c-1}
%\sum_{i=j+1}^{c}S^j(n,i)
%\hspace{1cm}\text{ for } c>2;\\
  &=&\frac{c^n}{c!}+\sum_{i=3}^{c}
\sum_{j=2}^{i-1}S^j(n,i), \hspace{1cm}\text{ for } c>2.\\
\label{eq:kn1}
\end{eqnarray*}
\noindent If the sums are rearranged such that $i=k+j$, we have
\begin{eqnarray}
 \rho_{L_c}(n)&=&\frac{c^n}{c!}+\sum_{k=1}^{c-2}\sum_{j=2}^{c-k}S^j(n,k+j),\label{eq:kn2}
\end{eqnarray}
where
\begin{eqnarray}
   S^j(n,k+j) &= &\frac{k^n}{(k+j)!}(-1)^j\binom{k+j}{j}\\
&=&\frac{k^n}{k!j!}(-1)^j. \label{eq:sjkj}
\end{eqnarray}

Replacing  (\ref{eq:sjkj}) into equation (\ref{eq:kn2}) we get
\begin{eqnarray}\label{eq:kn}
 \rho_{L_c}(n)&=&\frac{c^n}{c!}+
\sum_{k=1}^{c-2}\frac{k^n}{k!}\left(\sum_{j=2}^{c-k}\frac{(-1)^j}{j!}\right).
\end{eqnarray}

In equation~(\ref{eq:kn}), the coefficients of $k^n$, $1\leq k\leq c$, can be
calculated using the following recurrence relation:

\begin{eqnarray*}
  \label{eq:coe}
  \gamma_1^1&=& 1;\\
  \gamma_1^c&=&\gamma_1^{c-1} +\frac{(-1)^{c-1}}{(c-1)!}, \text{  for $c>1$};\\
  \gamma_k^c&=&\frac{\gamma_{k-1}^{c-1}}{k}, \text{ for  $c>1$ and $2\leq k\leq c$}.
\end{eqnarray*}

And, we have
\begin{theorem}
For all $c\geq 1$,
\begin{eqnarray}\label{eq:knan}
 \rho_{L_c}(n)&=&\sum_{k=1}^{c}\gamma_k^c k^n.
\end{eqnarray}
\end{theorem}

From the expression~(\ref{eq:knan}), the closed forms in
Table~\ref{tab:dc} are easily derived.


Finally, we can obtain the limit frequency of  $L_c$ in  $(\Nplus{c})^\star$.
Since $$\rho_{(\Nplus{c})^\star}(n)=c^n,$$

\noindent and
$\lim_{n\rightarrow\infty}\left({\frac{k}{c}}\right)^n=0$, for $1\le
k\le c-2$, we have
\begin{theorem}
For all $c\geq 1$,
\begin{equation*}
  \label{eq:lim}
  \lim_{n\rightarrow \infty}\frac{\rho_{L_c}(n)}{\rho_{(\Nplus{c})^\star}(n)} = \frac{1}{c!}.
\end{equation*}  
\end{theorem}


\section{A bijection between strings of $L_c$ and partitions of
  finite sets}


The connection between the density of $L_c$ and Stirling numbers of
second kind is not accidental. Each string of $L_c$ with length $n$
corresponds to a partition of $\Nplus{n}$ with no more than $c$
parts. This correspondence can be made explicit as follows.

Let $a_1a_2\cdots a_n$ be a string of $L_c$. This string corresponds
to the partition $\{A_j\}_{j\in \Nplus{c'}}$ of $\Nplus{n}$ with
$c'=\max\{a_1,\ldots,a_n\}$, such that for each $i\in \Nplus{n}$,
$i\in A_{a_i}$.  
For example, the string $1123$ corresponds to the partition
$\{\{1,2\},\{3\},\{4\}\}$ of $\Nplus{4}$ into $3$ parts.

This defines a bijection. That each string corresponds to a unique
partition is obvious. Given a partition $\{A_j\}_{j\in \Nplus{c'}}$ of
$\Nplus{n}$ with $c'\leq c$, we can construct the string $b_1\cdots
b_n$, such that for $i\in \Nplus{n}$, $b_i=j$ if $i \in A_{j}$. 
For the partition
$\{\{1,2\},\{3\},\{4\}\}$, we obtain $1123$.

\section{Counting  the  strings of  $L_{c}$ of length equal or less than a certain value}

Although strings of $L_c$ of arbitrary length represent game
configurations, for computational reasons\footnote{The data structures
used in the programs  are arrays of fixed length.} we consider all game configurations
with the same length, padding with zeros the positions of integers not
yet in one of the $c$ columns.  In this way, we obtain the languages
$L_c^0=L_c\{0^\star\}$. So, determining the number of strings of
length equal or less than $n$ that are in $L_c$ is tantamount to
determining the density of $L_c^0$, i.e.,
$$\rho_{L_c^0}(n)=|L_c^0\cap (\{0\}\cup \Nplus{c})^{n} |.$$
As seen in Section~\ref{clc}, and because
$L_c\{0^\star\}=L(\alpha_c0^\star)$, the generating function
$T^{\prime}_c(z)$ of $\rho_{L_c^0}(n)$ can be obtained as  the product
of a generating
function for $\rho_{L_c}(n)$, $T_c(z)$, by a generating function  for
$\rho_{\{0\}^\star}(n)$, e.g., 
$\displaystyle
\frac{1}{1-z}$. Thus, the generating function for $\{\rho_{L_c^0}(n)\}$ is
$$T^\prime_c(z)=T_c(z)\frac{1}{1-z}=\sum_{i=1}^{c}{\frac{z^i}
{(1-z)\prod_{j=1}^{i}{(1-jz)}}}$$
and a closed form for  $\rho_{L_c^0}(n)$ is (as expected)
\begin{equation}
  \rho_{L_c^0}(n)=\sum_{m=1}^{n}\sum_{i=1}^{c}{S(m,i)},
  \label{eq:rlz}
\end{equation}

\noindent where $m$ starts at $1$ because $S(m,i)=0$, for $i>m$.
\smallskip

Using expression~(\ref{eq:kn}) in~(\ref{eq:rlz}) we have
\begin{eqnarray*}
  \label{eq:rlz1}
 \rho_{L_1^0}(n)&=&n;\\
 \rho_{L_2^0}(n)&=&2^n -1;\\
  \rho_{L_c^0}(n)&=&\sum_{m=1}^{n}\left ( {\frac{c^m}{c!}+
\sum_{k=1}^{c-2}\frac{k^m}{k!}\sum_{j=2}^{c-k}\frac{(-1)^j}{j!}}\right),\hspace{1cm}
\text{ for } c> 2;\\
&=&\frac{c^{n+1}-c}{(c-1)c!}+n\sum_{j=2}^{c-1}\frac{(-1)^j}{j!}+\sum_{k=2}^{c-2}\frac{k^{n+1}
  -k}{(k-1)k!}\left(\sum_{j=2}^{c-k}\frac{(-1)^j}{j!}\right)\\
&=&\frac{c^{n}-1}{(c-1)(c-1)!}+n\sum_{j=2}^{c-1}\frac{(-1)^j}{j!}+\sum_{k=2}^{c-2}\frac{k^{n}
  -1}{(k-1)(k-1)!}\left(\sum_{j=2}^{c-k}\frac{(-1)^j}{j!}\right).
\end{eqnarray*}

If we use  the equation~(\ref{eq:knan}), we have
\begin{theorem}
For all $c\geq 1$,
  \begin{eqnarray*}\label{eq:k0nan}
  \rho_{L_c^0}(n)&=&
n\gamma_1^c+\sum_{k=2}^{c}\frac{\gamma_k^c(k^{n+1}-k)}{k-1}.
\end{eqnarray*}
\end{theorem}
\begin{proof}
\begin{eqnarray*}
  \rho_{L_c^0}(n)&=&
\sum_{m=1}^{n}\sum_{k=1}^{c}\gamma_k^ck^m\;=\;\sum_{k=1}^{c}\gamma_k^c\sum_{m=1}^{n}k^m\;=\;n\gamma_1^c+\sum_{k=2}^{c}\frac{\gamma_k^c(k^{n+1}-k)}{k-1}.
\end{eqnarray*}
  \end{proof}

  In the Table~\ref{tab:lcz} we present the values of
  $\rho_{L_c^0}(n)$, for $c=1..8$ and $n=1..13$. As before, 
  the limiting sequence as $c\rightarrow \infty$ is the sequence of partial sums
  of Bell numbers.

\begin{table}[htbp]
  \centering
{\small$$
\begin{array}{|l|l|c|}\hline
$c$&{\displaystyle \rho_{L_c^0}(n)}&\text{OEIS}
\\\hline&&\\
1&n&\\&&\\&1, \,2, \,3, \,4, \,5, \,6, \,7, \,8,\,9,\,10,\,11,\,12,\,13, \ldots&\\\hline&&\\
2&2^n - 1&\\&&\\&1, \,3, \,7, \,15, \,31, \,63, \,127, \,255,\,511,\,1023,\,2047,\,4095,\,8191,\ldots&\seqnum{A000225}
 \\\hline&&\\

3&{\displaystyle\frac{1}{4}\,3^n +\frac{1}{2}\,n - \frac{1}{4}
    }&\\&&\\&1, \,3, \,8, \,22, \,63, \,185, \,550, \,1644,\,4925, 
\,14767, \,44292, \,132866, \,398587,
    \ldots&\seqnum{A047926}
\\\hline&&\\
4&{\displaystyle  \frac{1}{18}\, 4^n +\frac{1}{2}\,
  2^n +   \frac{1}{3}\,n -\frac{5}{9}} &\\&&\\&1, \,3, \,8, \,23,
\,74, \,261, \,976, \,3771, \, 14822, \,58769, \,234044, \,934119,
\,3732370,\ldots&
\\\hline&&\\
5&{\displaystyle \frac{1}{96}\,5^n + \frac{1}{8}\, 3^n + \frac{1}{3}\,
    2^n + \frac{3}{8}\, n - \frac{15}{32}}&\\&&\\ &1, \,3, \,8, \,23,
  \,75, \,277, \,1132, \,4977, \,22979, \,109451, \,531456,
  \,2610931, \,12917683,\ldots&\seqnum{A099265}
\\\hline&&\\
6&{\displaystyle \frac {1}{600}} \,6^{n} 
+ {\displaystyle \frac {1}{36}} \,4^{n}
+ {\displaystyle \frac {1}{
12}} \,3^{n} 
+{\displaystyle \frac {3}{8}} \,2^{n}+ {\displaystyle 
\frac {11}{30}} \,n - {\displaystyle \frac {439}{900}}  
 &
\\&&\\&1, \,3, \,8,
    \,23, \,75, \,278, \,1154, \,5265, \,25913, \,135212,  \,736704,
    \,4139831, \,23767895,\ldots&\seqnum{A099266}
\\\hline&&\\
7&
{\displaystyle \frac {1}{4320}} \,7^{n} +
{\displaystyle \frac {1}{192}} \,5^{n}+
 {\displaystyle \frac {1}{54}} \,4^{n} + 
 {\displaystyle \frac {3
}{32}} \,3^{n} +
{\displaystyle \frac {11}{30}} \,2^{n} +
 {\displaystyle 
\frac {53}{144}} \,n - {\displaystyle \frac {31}{64}} 
&
\\&&\\&
1,\, 3,\, 8,\, 23,\, 75,\, 278,\, 1155,\, 5294,\, 26404,\, 141583,\, 807062,\, 4837585,\, 30181073,\ldots&
\\\hline&&\\
8&{\displaystyle \frac {1}{35280}} \,8^{n} +
  {\displaystyle \frac {1
}{1200}} \,6^{n}+
{\displaystyle \frac {1}{288}} \,5^{n} +
 {\displaystyle \frac {1}{48}} \,4^{n} + 
 {\displaystyle \frac {
11}{120}} \,3^{n}+
{\displaystyle \frac {53}{144}} \,2^{n} +
 {\displaystyle 
\frac {103}{280}} \,n - {\displaystyle \frac {57023}{117600}}  &

\\&&\\&
1, \,3, \,8, \,23, \,75, \,278, \,1155, \,5295, \,26441
, \,142370, \,819729, \,5009279, \,32252379, \ldots&
\\\hline
\end{array}
$$}
  \caption{Density functions of $L_c^0$, for $c=1..8$.}\label{tab:lcz}
\end{table}


Finally, we determine the limit frequency of  $L_c^0$ in  
$(\Nplus{c})^\star\{0\}^\star$. Notice that

$$\rho_{(\Nplus{c})^\star\{0\}^\star}(n)=\frac{c^{n+1} - 1}{c-1},
$$

\noindent as it is a sum of the first $n$ terms of a geometric progression
 of ratio $c$.


We have, 
\begin{theorem}
For all $c\geq 1$, 
  \begin{eqnarray*}
\lim_{n\rightarrow\infty}\frac{\rho_{L_c^0}(n)}{\rho_{(\Nplus{c})^\star\{0\}^\star}(n)}&=&\frac{1}{c!}.
\end{eqnarray*}
\end{theorem}
\begin{proof}
{\small
\begin{eqnarray*}
\lim_{n\rightarrow\infty}\frac{\rho_{L_c^0}(n)}{
  \rho_{(\Nplus{c})^\star\{0\}^\star}(n)}&=&
\lim_{n\rightarrow\infty}\left(\frac{(c^{n+1}-c)(c-1)}{(c-1)c!(c^{n+1}-1)}+\frac{n(c-1)}{c^{n+1}-1}\sum_{j=2}^{c-1}\frac{(-1)^j}{j!}\right)\\&&+\lim_{n\rightarrow\infty}\left(\sum_{k=2}^{c-2}\frac{(k^{n+1}
  -k)(c-1)}{(k-1)k!(c^{n+1}-1)}\left(\sum_{j=2}^{c-k}\frac{(-1)^j}{j!}\right)\right)
\\
&=&\frac{1}{c!}\left(\lim_{n\rightarrow\infty}\frac{1}{1-\frac{1}{c^{n+1}}}-\lim_{n\rightarrow\infty}\frac{c}{c^{n+1}-1}\right)
  \\
&&+
  \sum_{j=2}^{c-1}\frac{(-1)^j}{j!}\lim_{n\rightarrow\infty}\left(\frac{n(c-1)}{c^{n+1}-1}\right)\\
&&+ \sum_{k=2}^{c-2}
\frac{(c-1)}{(k-1)(k-1)!}\sum_{j=2}^{c-k}\frac{(-1)^j}{j!}\lim_{n\rightarrow\infty}\left(
\frac{(\frac{k}{c})^{n}}{c-\frac{1}{c^{n}}}-\frac{1}{c^{n+1}-1}\right)\\
&=&\frac{1}{c!}.
\end{eqnarray*}
}
\end{proof}
\section{Conclusion}

In this note we presented  a family of regular languages representing
finite set partitions and studied their densities.  Although it is
well-known that the number of partitions of a set of $n$ elements into
no more than $c$ nonempty sets is given by partial sums of Stirling
numbers of second kind, we determined explicit formulas for their
closed forms, as linear combinations of $k^n$, for $k\in \Nplus{c}$.
We also determined the limit frequency of those languages, which gives an
estimate of the space saved with those representations.
 


\subsection*{Acknowledgements}
\label{ack}

We thank Miguel Filgueiras and the referee for their comments in 
previous versions of the manuscript. We also thank J. Shallit for
pointing us a connection between the density of $L_c$ and  the  Bell numbers.
 
\begin{thebibliography}{HMU00}
\bibitem[BHR04]{blanchard04:_partit}
Peter Blanchard, Frank Harary, and Rog\'erio Reis,
\newblock Partitions into sum-free sets,
\newblock {\em Integers: Electronic Journal of
  Combinatorial Number Theory},  (to appear), 2004.

\bibitem[GKP94]{graham94:_concr_mathem}
Roland Graham, Donald Knuth, and Oren Patashnik.
\newblock {\em Concrete Mathematics}.
\newblock  Addison-Wesley, 1994.

\bibitem[Hec03]{heck03:_introd_maple}
Andri Heck.
\newblock {\em Introduction to Maple}.
\newblock Springer, 3rd edition, 2003.
\newblock \href{http://remote.science.uva.nl/%7Eheck/Maplebook/}{http://remote.science.uva.nl/\%7Eheck/Maplebook/}.

\bibitem[HMU00]{hopcroft00:_introd_autom_theor_languag_comput}
John~E. Hopcroft, Rajeev Motwani, and Jeffrey~D. Ullman.
\newblock {\em Introduction to Automata Theory, Languages and Computation}.
\newblock Addison-Wesley, 2nd edition, 2000.

\bibitem[RMP04]{reis04:_educat}
Rog\'erio Reis, Nelma Moreira, and Jo\~ao~Pedro Pedroso.
\newblock Educated brute-force to get h(4).
\newblock Technical Report DCC-2004-04, DCC-FC\& LIACC, Universidade do Porto,
  July 2004.

\bibitem[SF96]{sedgewick96:_analy_algor}
Robert Sedgewick and Philippe Flajolet.
\newblock {\em Analysis of Algorithms}.
\newblock  Addison-Wesley, 1996.

\bibitem[Slo03]{sloane03:_encyc_integ_sequen}
N.J.A. Sloane.
\newblock The {O}n-line {E}ncyclopedia of {I}nteger {S}equences, 2003.
\newblock \href{http://www.research.att.com/~njas/sequences}{http://www.research.att.com/$\sim$njas/sequences}.

\end{thebibliography}
%\bibliographystyle{alpha} \bibliography{../../Aulas/bibcc}




\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A18, 11B73, 68Q45.\ \

\noindent \emph{Keywords:} Partions of sets, Stirling numbers, regular
  languages, enumeration

\bigskip
\hrule
\bigskip


\noindent (Concerned with sequences
\seqnum{A000110} 
\seqnum{A000225}
\seqnum{A007051}
\seqnum{A007581}
\seqnum{A008277}
\seqnum{A047926}
\seqnum{A056272}
\seqnum{A056273}
\seqnum{A099262}
\seqnum{A099263}
\seqnum{A099265}
\seqnum{A099266}
.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 14 2004;
revised version received April 17 2005. 
Published in {\it Journal of Integer Sequences}, May 18 2005.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in


\end{document}