<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

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

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

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{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 
Combinatorial Interpretations of a \\
\vskip .1in
Generalization of the Genocchi Numbers
}
\vskip 1cm
{\large
Michael Domaratzki \\
Jodrey School of Computer Science\\
Acadia University \\
Wolfville, NS B4P 2R6 \\
Canada\\
\href{mailto:mike.domaratzki@acadiau.ca}{\tt mike.domaratzki@acadiau.ca} }\\
\end{center}

\vskip .2 in

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

\def \prend{\vrule depth-1pt height7pt width6pt}
\def \proof{\bigbreak\noindent{\bf Proof.\ \ }}
\def \endpf{{\ \ \prend \medbreak}}

\newtheorem{thm}{Theorem}[section]
%\newtheorem{lemma}[thm]{Lemma}
\newtheorem{exmp}[thm]{Example}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\renewcommand{\theequation}{\thesection.\arabic{equation}}
\renewcommand{\thefigure}{\thesection.\arabic{figure}}


\date{}
%\begin{document}

%\maketitle

\begin{abstract}
We consider a natural generalization of the well-studied Genocchi numbers 
first proposed by Han. This generalization proves 
useful in enumerating the class of deterministic finite automata (DFA) that accept a finite language, and in enumerating a generalization of
permutations counted by Dumont.

\end{abstract}

\section{Introduction and Motivation}

The study of Genocchi numbers and their combinatorial interpretations
has received much attention \cite{D72,D74,DF76,DR94,DV80,G70,RS73}. In
this paper, we consider combinatorial interpretations of a generalization
of the Genocchi
numbers due to Han \cite{H93}.

The Genocchi numbers $G_{2n}$ ($n \ge 1$) may be defined in terms of the generating function
\[ \frac{2t}{e^t + 1} = t + \sum_{n \ge 1} (-1)^n G_{2n} \frac{t^{2n}}{(2n)!}. \]
They may also be defined in the following way \cite{G70,C71,RS73}. Let 
the Gandhi polynomials $A(n,X)$ be polynomials in $X$ defined as follows: 
\begin{eqnarray*}
 A(n+1,X) &amp; = &amp; X^2 A(n,X+1) - (X-1)^2 A(n,X) \quad \forall n \ge 1,\\
 A(1,X)   &amp; = &amp; X^2 - (X-1)^2.
\end{eqnarray*}
Then $|G_{2n}| = A(n-1,1)$.  The first few values of 
$|G_{2n}|$ are 1,1,3,17,155 for $n=1,2,3,4,5$, respectively.

Our motivation comes from automata theory. We are interested in 
the number of finite languages recognized by deterministic finite
automata (DFAs) with $n$ states.  It is easy to see that if a DFA
$M = (Q, \Sigma, \delta, q_0, F)$ accepts a finite language 
(see Section~\ref{defback} for definitions), then there exists
an ordering of the elements of the set of states $Q$, say $Q = \{0,1,2,\dots,n\}$ with
$q_0 = 0$ such that $\delta(i,a) &gt; i$ for all $i \in Q - \{n\}$ and 
$a \in \Sigma$ and $\delta(n,a) = n$ for all $a \in \Sigma$. Thus, we 
study directed graphs with labeled edges on $n$ vertices that satisfy
these properties.

In this paper, we consider an extension of the Genocchi numbers due
to Han \cite{H93}, and show its relation to enumerating DFAs accepting
finite languages. 

\section{Definitions and Background}\label{defback}

We first recall some definitions from automata theory and
formal languages. For any terms not covered here, the reader may consult
Hopcroft and Ullman \cite{HU79} or Yu \cite{Y97}. 
Let $\Sigma$ denote a finite alphabet. Then $\Sigma^{*}$
is the set of all finite strings over $\Sigma$. The empty string is denoted by $\epsilon$.
A {\em language} $L$ over $\Sigma$ is a subset of $\Sigma^{*}$.
A {\em deterministic finite 
automaton} (DFA) is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$, where $Q$
is a finite set of states, $\Sigma$ is a finite alphabet of symbols, $q_0 \in Q$
is the initial state and $F \subseteq Q$ is a set of final states. The transition
function $\delta$ is a function $\delta : Q \times \Sigma \rightarrow Q$ that 
may be
extended to $Q \times \Sigma^{*} \rightarrow Q$ in the following manner: For
all states $q \in Q$, $\delta(q,\epsilon) = q$. Further, for
any $w  \in \Sigma^{*}$ and $a \in \Sigma$, 
$\delta(q,wa) = \delta(\delta(q,w),a)$ for all states $q \in Q$. 

A string $w \in \Sigma^{*}$ is accepted by $M$ if $\delta(q_0,w) \in F$.  The language
accepted by a DFA $M$ is the set of all strings accepted by $M$, denoted by $L(M)$:
\[ L(M) = \{ w \in \Sigma^{*} \ : \ \delta(q_0,w) \in F \}. \]
We say that a DFA $M$ accepts a language $L \subseteq \Sigma^{*}$ if $L = L(M)$.
In this paper, we are concerned primarily with finite languages, that is, those $L$
with $|L| &lt; \infty$.
We use the notation $[n]$ to denote the set $\{1,2,3,\dots,n\}$.

We now proceed with the generalization of the Genocchi numbers due to
Han \cite{H93}.  
We define them in terms of a natural generalization of the Gandhi polynomials:
\begin{defn}\label{defn_1_text}
Let $A_{n+1}^{(k)}(X)$ be the following Gandhi polynomials in $X$: 
\begin{equation}
\begin{split}
A_{n+1}^{(k)}(X) &amp; =  X^k A_{n}^{(k)}(X+1) - (X-1)^k A_{n}^{(k)}(X) \quad \forall n \ge 0\\
A_{0}^{(k)}(X)   &amp; =  1 . 
\end{split} \label{defn__1}
\end{equation}
Define the $k$-th generalized Genocchi numbers $\{ G_{2n}^{(k)} \}_{n \ge 1}$
by $G_{2n}^{(k)} = A^{(k)}_{n-1}(1)$.
\end{defn}
Figure~\ref{table__1} gives values of 
$G_{2n}^{(k)}$ for small values of $k$. The 
sequence $G_{2n}^{(2)}$ appears as A001469 in Sloane \cite{Sl01}.
The sequences $G_{2n}^{(3)}$, $G_{2n}^{(4)}$ and $G_{2n}^{(5)}$
appear in Sloane as 
A064624, A064625 and A065756, respectively.

Han \cite[Thm.\ 3]{H93} studied polynomials that are even more general than
those given in Definition~\ref{defn_1_text}, but the definition of $A^{(k)}_n$ 
will suffice in what follows. We now apply the results of Han to the specific
case of the polynomials $A^{(k)}_n$.

\begin{figure}[ht]
\begin{center}
\begin{tabular}{lrrrrrrr}\hline
$n$				&amp;	1	&amp; 	2	&amp;	3	&amp;	4	&amp;	5	&amp;	6		&amp; 	7 	 \\ \hline
$G_{2n}^{(2)}$	&amp;	1	&amp;	1	&amp;	3	&amp;	17	&amp; 155	&amp; 2073		&amp; 38227 \\ 
$G_{2n}^{(3)}$ 	&amp; 	1	&amp;	1	&amp;	7	&amp; 145	&amp;	6631&amp; 566641	&amp; 81184327 \\ 
$G_{2n}^{(4)}$  	&amp; 	1	&amp;	1	&amp;	15	&amp; 1025 	&amp; 209134&amp; 100482849 &amp; 97657699279 \\
$G_{2n}^{(5)}$ 	&amp;	1 	&amp;	1	&amp; 	31  &amp; 6721	&amp;	5850271&amp; 15060446401 &amp; 94396946822431 \\ \hline
\end{tabular}
\caption{Small values of $G_{2n}^{(k)}$.}
\label{table__1}
\end{center}
\end{figure}

\subsection{Properties of $G_{2n}^{(k)}$}

Following Dumont \cite{D72}, we first show some 
algebraic properties of $G_{2n}^{(k)}$.
First, we translate the polynomials $A^{(k)}_n$ as follows. Define the
polynomials $B_k(X,n)$ in $X$ as 
\begin{equation}
B_{k}(X,n) = X^k A^{(k)}_{n-1}(X+1) \label{translate}
\end{equation}
for any $n \ge 1$.
Then (\ref{defn__1}) becomes
\begin{equation}\label{defn__2}
\begin{split}
B_{k}(X,n) &amp;= X^k ( B_k(X+1,n-1) - B_k(X,n-1) ) \\
B_{k}(X,1) &amp;= X^k.
\end{split}
\end{equation}
We may compare this with the work of Dumont \cite[Eq.\ (3), p.\ 323]{D72}. 
Let 
\begin{equation}
B_{k}(X,n)  = \sum_{j=0}^{(k -1) n + 1} B_{n,j}^{(k)} X^j . \label{defn__3}
\end{equation}
It is easy to see that $B_k(X,n)$ is a polynomial of degree $(k - 1)n +1$
in $X$. 
Now equating coefficients in (\ref{defn__2}) gives the recurrence:
\begin{equation}
B_{n,j}^{(k)} = \sum_{\ell = j-k+1}^{(n-1)(k-1)+1} \binom{\ell}{j-k} B_{n-1,\ell}^{(k)} \label{defn__4}
\end{equation}
for $j \ge k$.
Iterating (\ref{defn__4}) gives us our most useful definition:
\begin{lemma}
For all $n \ge 2$, and $k \ge 2$,
\begin{equation}
B_{n,j}^{(k)} = \sum \binom{k}{j_1} \binom{2k-j_1}{j_2-j_1} \binom{3k-j_2}{j_3 - j_2}
\cdots \binom{k(n-1) - j_{n-2}}{j_{n-1} - j_{n-2}}, \label{defn__5}
\end{equation}
where the sum is taken over all integers $j_1,j_2,\dots,j_{n-1}$
satisfying $1 \le j_1 &lt; j_2 &lt; \cdots &lt; j_{n-2} &lt; j_{n-1} \le kn-j$
and $j_i \le ki$ for all $1 \le i \le n-2$. 
\end{lemma}
\proof
The proof is by induction on $n$.
To prove the base case, note that for all $k$,
\begin{eqnarray*}
B_k(X,2)&amp; =&amp; X^k (X+1)^k - X^{2k} \\
        &amp; =&amp; \sum_{\ell = 0}^{k-1} \binom{k}{\ell} X^{\ell+k},
\end{eqnarray*}
whence $ B_{2,j}^{(k)} = \binom{k}{k-j}.$
Thus, the condition holds for $n=2$. 
Let the formula hold for $n-1$ and for all $j$. Then we have
\begin{eqnarray*}
B_{n,j}^{(k)} &amp;=&amp; \sum_{\ell = j-k+1}^{n(k-1)} \binom{\ell}{j-k} B_{n-1,\ell}^{(k)} \\
&amp;=&amp; \sum_{\ell = j-k+1}^{n(k-1)} \binom{\ell}{ \ell - j + k} 
\sum \binom{k}{j_1} \binom{2k - j_1}{j_2 - j_1} \cdots \binom{k(n-2) - j_{n-3}}
{ j_{n-2} - j_{n-3} } .
\end{eqnarray*}
If we now choose $j_{n-1} = k(n-1) + k - j$ we will see that the conditions
on the $j_i$ are satisfied. This gives 
$B_{n,j}^{(k)} = \sum \binom{k}{j_1} \binom{2k-j_1}{j_2-j_1} \binom{3k-j_2}{j_3 - j_2}
\cdots \binom{k(n-1) - j_{n-2}}{j_{n-1} - j_{n-2}}.$
\endpf
We now note that $G_{2n}^{(k)}$ is given by $G_{2n}^{(k)} = B_{n,k}^{(k)}$,
which follows directly from the definition and the 
translation given by (\ref{translate}). Thus, we note the formula
\begin{equation}
G_{2n}^{(k)} = \sum_{\ell=1}^{(n-1)(k-1)+ 1} B_{n-1,\ell}^{(k)}. \label{linear} 
\end{equation}
This follows from (\ref{defn__4}).
Tables of $B_{n,j}^{(k)}$ are given in Appendix A.
It will be useful to rewrite (\ref{defn__5}) when $j=k$ to 
give an expression for $G_{2n}^{(k)}$ as follows:
\begin{eqnarray}
\lefteqn { \sum_{i_1 = 1}^{k} \binom{k}{i_1} 
			\sum_{i_2 = 1}^{2k - i_1} \binom{ 2k - i_1 }{i_2 } 
			\sum_{i_3 = 1}^{3k - (i_1 + i_2)} \binom{ 3k - (i_1 + i_2)}{i_3}
	\cdots}  \label{my_geno_rep}  \\
&amp;&amp; {} \cdots 
\sum_{i_{j} = 1}^{ kj - \sum_{\ell = 1}^{j-1} i_{\ell} } 
\binom{ kj - \sum_{\ell = 1}^{j-1} i_{\ell} } { i_j } 
\cdots
\sum_{i_{n-2} = 1}^{ k(n-2) - \sum_{\ell = 1}^{n-3} i_{\ell} } 
\binom{ k(n-2) - \sum_{\ell = 1}^{n-3} i_{\ell} } { i_{n-2} }. \nonumber
\end{eqnarray}
We obtain this through the change of of variables $i_{1} = j_1$ and 
$i_{\ell} = j_{\ell} - j_{\ell -1}$ for $ 2 \le \ell \le n-3$. 
Equation
(\ref{my_geno_rep}) will prove particularly useful for our enumeration of 
automata, which we investigate in Section~\ref{comb_interp}.

\subsection{Generalized Central Factorial Numbers}\label{gcfn_sect}

\begin{defn}\label{gcfn}
Define $T_{k}(n,i)$ for all $k \ge 2$, $n \ge 1$
and all integers $i$ as follows:
\begin{eqnarray*}
 T_k(1,1) &amp;=&amp; 1, \\ 
T_k(n,i) &amp;=&amp; 0 \quad \forall i \not\in [n], \\
T_k(n,i) &amp;=&amp; i^k T_k(n-1,i) + T_k(n-1,i-1) \quad \forall i \in [n].
\end{eqnarray*}
\end{defn}

When $k=2$, Definition~\ref{gcfn} gives the {\sl central factorial
numbers} (see Carlitz and Riordan \cite{CR63}) and used in the proof
of the equivalence of the Genocchi numbers and the Gandhi polynomials
by Carlitz \cite{C71} and Riordan and Stein \cite{RS73}.

By Han \cite[p.\ 7]{H93}, we can relate $T_k(n,i)$ with the generalized
Genocchi numbers,
which is of independent interest (compare with Riordan and Stein
\cite[Eq. (2), p. 382]{RS73}):
\begin{equation}
G_{2n+2}^{(k)} = \sum_{\ell=1}^{n} (-1)^{\ell+1} (\ell!)^k T_{k}(n,\ell). \label{gcfn__2}
\end{equation}

Figure~\ref{table__2} gives the value of $T_{3}(n,i)$ for $1 \le i \le n \le 7$.
\begin{figure}[ht]
\begin{center}
\begin{tabular}{rlllllll} 
\hline
$n \setminus i$ &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\ 
1			    &amp; 1 &amp; 	&amp; 	&amp; 	&amp; 	&amp;   \\
2				&amp; 1 &amp; 1 &amp;	&amp;	&amp;	&amp;	\\
3				&amp; 1 &amp; 9 &amp; 1 &amp;	&amp;	&amp;	\\
4				&amp; 1&amp; 73 &amp; 36&amp; 1 &amp; 	&amp; 	\\
5				&amp; 1&amp;585&amp;1045&amp;100&amp;1  &amp;   \\
6				&amp;1&amp;4681&amp;28800&amp;7445&amp;255&amp;1\\
7			&amp;1&amp;37449&amp;782281&amp;505280&amp;35570&amp;441&amp;1\\
\hline
\end{tabular}
\caption{Small values of $T_{3}(n,i)$}
\label{table__2}
\end{center}
\end{figure}
Note that expressions for $T_k(n,i)$ 
numbers are given by Comtet \cite{C72} and 
Bach \cite{B68} as generalizations of Stirling numbers. 

\section{Combinatorial Interpretations}\label{comb_interp}

In this section, we discuss some combinatorial interpretations
of the generalized
Genocchi numbers, as well as the generalization of the central factorial
numbers given in Section~\ref{gcfn_sect}. 
These interpretations includes a new graph theoretic combinatorial interpretation for the standard Genocchi numbers.

\subsection{Quasi-Permutations}

Consider the following definition \cite[p.~306]{D74}:

\begin{defn}
A set $P \subseteq [n] \times [n]$ is
a quasi-permutation of $[n]$ 
if there exists a permutation $p$ of
$[n]$ such that $P$ is a subset of the following
set
\[ \{ (i,p(i)) \ : \ i \in [n], p(i) &gt; i \}. \]
\end{defn}
Let $|P|$ denote the cardinality of $P$ as a set.
For any subset $P \subseteq [n] \times [ n ]$,
let $Y(P) = \{ i \ : \ \exists i' \textrm{ such that } (i',i) \in P \}$,
the projection of $P$ on the second component. 
  
We can generalize a theorem of Dumont \cite[Thm.\ 1, p.\ 309]{D74}
(which is itself inspired by a theorem of Foata and
Sch\"utzenberger \cite[Prop.\ 2.8., p. 38]{FS70}) 
concerning combinatorial interpretations of the central 
factorial numbers as follows: 

\begin{thm}\label{gcfn_thm_1}
The quantity $T_{k}(n,i)$ is equal to the number of $k$-tuples
of quasi-permutations of $[n]$ $(Q_1,Q_2,\dots,Q_k)$ 
such that 
\begin{itemize}
\item $|Q_j| = n-i$ for all $j$ with $1 \le j \le k$
\item for all $1 \le j,j' \le k$, $Y(Q_j) = Y(Q_{j'}).$
\end{itemize}
\end{thm}
\proof
The proof is a simple generalization of the proof of Dumont 
\cite[Thm.\ 1, p.\ 309]{D74}.  
\endpf
Note that a simple calculation will show that the result of Dumont 
concerning tuples of permutations \cite[Thm.\ 2, p.\ 310]{D74} does
not generalize to $k$-th generalized Genocchi numbers.

\subsection{Finite language DFAs over 2 letters}

We start by defining a set of directed graphs that will
be of interest:
\begin{defn}
Let $\mathcal{G}_{n,k}$ define the set of digraphs satisfying 
the following conditions: For all $G = (V,E) \in \mathcal{G}_{n,k}$,
\begin{enumerate}
\item[(a)] There are $n$ vertices, labeled with integers from the set $[n]$.
\item[(b)] The edges of $E$ are labeled with integers from the set
$[k]$.  Thus an edge of $E$ is given by an element
of $[n] \times [k] \times [n]$. 
\item[(c)] All the edges of $E$ are directed and satisfy the following:
if $e=(u,a,v) \in E$ and $u \ne n$ then $e$ is directed from
$u$ to $v$ and $u &lt; v$. If $u=n$ then necessarily $v=n$.
\item[(d)] $G$ is initially connected, that is, for each vertex $v$, there
exists a directed path from $1$ to $v$.
\item[(e)] For each vertex $v$ and each 
integer $i$ ($1 \le i \le k$), there exists an edge 
with source $v$ and label $i$.
\end{enumerate}
\end{defn}
Given (\ref{my_geno_rep}), we can prove the following:
\begin{thm}\label{dir_graphs__2}
For all $n \ge 1$, $|\mathcal{G}_{n,2}| = G_{2n}$.
\end{thm} 
\proof
The sum given in (\ref{my_geno_rep}) represents the number of ways of
connecting each of the vertices $2,\dots,n$ with a lower numbered vertex.
We can see this as follows. Consider vertex $2$. In order for vertex 
2 to be connected to vertex $1$, at least one of the 2 edges leaving
vertex 1 must enter vertex 2.  We let $i_1$ of them enter 2, and account
for all possible combinations. 

Now for vertex 3, at least 1 of the $4 - i_1$
edges leaving vertex 1 and 2 that have yet to be assigned must enter
vertex 3; let $i_2$ of them enter vertex 3.  

We continue this process
for the first $n-1$ vertices. The result is the sum (\ref{my_geno_rep}). The
vertex $n$ is initially connected since by definition all edges leaving
vertex $n-1$ must enter vertex $n$.
\endpf

We can also give a direct proof of Theorem~\ref{dir_graphs__2}.  
A {\em surjective step function (SSF) of size $2n$} is a 
function $f : [2n] \rightarrow [2n]$
such that $f(i) \ge i$, and
the image of $f$ is exactly $\{2,4,6,\dots,2n\}$.
The following is due to Dumont \cite{D74}:

\begin{thm}\label{d74_1} 
The number of surjective step  
functions of size $2n$ is $G_{2(n+1)}$.
\end{thm}

We show a bijection between all SSFs of size
$2(n-1)$ and $\mathcal{G}_{n,2}$. 
Let $f : [ 2n-2 ] \rightarrow [2n-2]$ 
be a surjective step function of size $2(n-1)$. Then define
the graph $G_f = (V_f,E_f)$ as follows: $V_f = [n]$,
and 
\begin{eqnarray*}
E_f  &amp; =  &amp; \{ (n,a,n) \ : \ a \in \{ 1,2 \} \}  \\
     &amp; \cup &amp; \{ (i,1, \frac{f(2i)}{2} + 1) \ : \ 1 \le i &lt; n \} \\
	 &amp; \cup &amp; \{ (i,2, \frac{f(2i-1)}{2} + 1) \ : \ 1 \le i &lt; n \}.
\end{eqnarray*}

Thus, we have a direct bijection demonstrating Theorem~\ref{dir_graphs__2}.
We now return to our motivation: DFAs that recognize finite languages. 
The following lemma \cite[Prop.\ 18]{DKS03} states that the underlying structure
of DFAs that accept finite languages corresponds exactly to $\mathcal{G}_{n,2}$:
\begin{lemma}
Let $M$ be a minimal $n$-state DFA with $L(M)$ finite. Then $M$ is 
isomorphic (up to renaming of the states) to a DFA $M' = (Q,\Sigma,\delta,q_0,
F)$ satisfying $Q = \{q_0,q_1,\dots,q_{n-1} \}$ and the following conditions:
\begin{enumerate}
\item[(a)] $\delta(q_{n-1},a) = q_{n-1}$ for all $a \in \Sigma$.
\item[(b)] If $n \ge 2$ then $\delta(q_{n-2},a) = q_{n-1}$ for all $a \in \Sigma$.
\item[(c)] $q_{n-1} \not\in F$.
\item[(d)] If $n \ge 2$, then $q_{n-2} \in F$.
\item[(e)] If $\delta(q_i,a) = q_j$ for $i &lt; n-1$ then $i &lt; j$.
\end{enumerate}
\end{lemma}
Thus, we may give an upper bound for the number of distinct DFAs 
on $n$ states accepting a finite language.
Adding final states in all possible ways (subject to $q_{n-1} \not\in F$ and
$q_{n-2} \in F$), we have the following 
corollary of Theorem~\ref{dir_graphs__2}: 
\begin{cor}
The number of finite languages over a two letter alphabet accepted by a 
DFA with $n$ states is at most $2^{n-2} G^{(2)}_{2n}$.
\end{cor}
Unfortunately, this bound is not tight. This is due to the fact that many
of the languages recognized by distinct labeled DFAs will be the same,
and what is needed is an unlabeled enumeration of DFAs.

\subsection{$k$-th Surjective step functions}

We may adapt the combinatorial interpretation of the Genocchi numbers
in terms of surjective step functions, due to Dumont \cite{D74},
to generalized Genocchi numbers: 

\begin{defn}
A $k$-th surjective step function ($k$-SSF) of size $kn$ 
is an increasing surjective function $f : [kn] 
\rightarrow \{k,2k,3k,\dots,kn \}$.
\end{defn}

The following is a corollary of Han \cite{H93}. 
\begin{thm}\label{kssf__1}
There are $G_{2(n+1)}^{(k)}$ $k$-SSFs of size $kn$.
\end{thm}

\subsection{Finite language DFAs over $k$ letters}

The argument of Theorem~\ref{dir_graphs__2} can be easily extended
to graphs over a $k$ letter alphabet. In fact, if we repeat the same
argument we get the following result:

\begin{thm}
$|\mathcal{G}_{n,k}| = G_{2n}^{(k)}$.
\end{thm}

This allows us to extend our upper bound to automata over
arbitrary sized alphabets:

\begin{cor}
The number of finite languages over a $k$ letter alphabet accepted by a 
DFA with $n$ states is at most $2^{n-2} G^{(k)}_{2n}$.
\end{cor}
 
We may also extend the isomorphism between $\mathcal{G}_{n,2}$ and 2-SSFs 
of size
$2(n-1)$ to $\mathcal{G}_{n,k}$ and k-SSFs of size $k(n-1)$. Let $f$
be a k-SSF of size $k(n-1)$. Then define $G_f = (V_f,E_f)$ as follows:
$V_f = [n]$, and
\begin{eqnarray*}
E_f  &amp; =  &amp; \{ (n,a,n) \ : \ 1 \le a \le k \}  \\
     &amp; \cup &amp; \{ (i,a, \frac{f(ki-a+1)}{k} + 1) \ : \ 1 \le i &lt; n, \, 1 \le a \le k \}. \\
\end{eqnarray*}

\subsection{Generalizations of Dumont Permutations}

Dumont has also given several interpretations of the usual Genocchi numbers
$G_{2n}^{(2)}$ in terms of permutations, including the
following theorem \cite[Thm. 5, p.\ 315]{D74}:

\begin{thm}\label{dumont__1}
Let $P_{2n}$ be the set of permutations $\pi$ of $[2n]$ such that 
$\pi(i) \ge i$ iff $\pi(i)$ is even. Then $|P_{2n}| = G_{2n+2}^{(2)}$.
\end{thm}

By a direct application of a result due to Dumont \cite[Thm.\ 4, p.\ 313]{D74} 
and Theorem~\ref{kssf__1}, we can
generalize Theorem~\ref{dumont__1} naturally:

\begin{thm}
Let $P_{kn}$ be the set of permutations $\pi$ of $[kn]$ such that
$\pi(i) \ge i$ iff $\pi(i) \equiv 0 \, (\textrm{mod } k)$. Then 
$|P_{kn}| = G_{2n+2}^{(k)}$.
\end{thm}

\begin{exmp}
Consider $k=3$, $n=2$. Thus, we are concerned with permutations $\pi$ of $[6]$
such that $\pi(i) \ge i$ if and only if $\pi(i) \equiv  0 \, (\textrm{mod } 3)$.
Then of the 720 permutations, we find that the following permutations satisfy our
conditions:
\begin{center}
\begin{tabular}{cccc}
$(1\, 3\, 2)(4\, 6\, 5)$ &amp; $(1\, 3\, 6\, 5\, 4\, 2)$ &amp; $(1\, 3)(2\, 6\, 5\, 4)$ &amp; $(1\, 3\, 2\, 6\, 5\, 4)$ \\
$(1\, 6\, 5\, 4\, 2)(3)$ &amp; $(1\, 6\, 5\, 4\, 2\, 3)$ &amp; $(1\, 6\, 5\, 4)(2\, 3)$ &amp;  \\
\end{tabular}
\end{center}
This agrees with $G_{2n+2}^{(3)} = 7$.
\end{exmp}

Dumont also gives the following corollary to Theorem~\ref{dumont__1}
\cite[Cor.\ 1,p.\ 316]{D74}:

\begin{thm}\label{dumont__2}
Let $P'_{2n}$ be the set of permutations $\pi$ of $[2n]$ such that 
$\pi(i) \ge i$ iff $i$ is odd. Then $|P'_{2n}| = G_{2n+2}^{(2)}$.
\end{thm}

However, the ability to conclude Theorem~\ref{dumont__2} from 
Theorem~\ref{dumont__1} does not naturally generalize to permutations 
of $[kn]$ for $k &gt; 2$. 

\section{Conclusions} 

In this paper, we have considered a new generalization of the Genocchi numbers.
This generalization has proved useful in our attempts to enumerate the 
number of finite languages recognized by DFAs with $n$ states. 

\section*{Acknowledgments}
Thanks to Jeff Shallit for his careful reading, excellent comments, 
motivation and
pointing me towards the Genocchi numbers. Thanks to Kai Salomaa for his
many careful readings and useful comments.  
Marni Mishna also read this paper and had many suggestions.

\begin{thebibliography}{10}

\bibitem{B68}
{\sc G.~Bach,}
\newblock {\"Uber eine Verallgemeinerung der Differenzengleichung der
  Stirlingschen Zahlen 2.Art und einige damit zusammenh\"agende Fragen}.
\newblock {\em J.~Reine Angew.~Math.\/} {\bf 223} (1968), 213--220.

\bibitem{C71}
{\sc L.~Carlitz,}
\newblock A conjecture concerning {Genocchi} numbers.
\newblock {\em K.~Norske Vidensk.~Selsk.~Sk.\/} {\bf 9} (1971), 1--4.

\bibitem{CR63}
{\sc L.~Carlitz, and J.~Riordan,}
\newblock The divided central differences of zero.
\newblock {\em Can.~J.~Math \/} {\bf 15} (1963), 94--100.

\bibitem{C72}
{\sc L.~Comtet,}
\newblock Nombres de {Stirling} {g\'en\'eraux} et fonctions sym{\'e}triques.
\newblock {\em C.R.~Acad.~Sc.~Paris S{\'e}r.~A.\/} {\bf 275} (1972), 747--750.

\bibitem{DKS03}
{\sc M.~Domaratzki, D.~Kisman, and J.~Shallit,}
\newblock On the number of distinct languages accepted by finite automata with
  {$n$} states.
\newblock {\em J.~Automata, Languages and Combinatorics} {\bf 7}
  (2003), 469--486.

\bibitem{D72}
{\sc D.~Dumont,}
\newblock Sur une conjecture de {G}andhi concernant les nombres de {G}enocchi.
\newblock {\em Disc.~Math.\/} {\bf 1} (1972), 321--327.

\bibitem{D74}
{\sc D.~Dumont,}
\newblock Interpretations combinatoires des nombres de {G}enocchi.
\newblock {\em Duke Math.~J.\/} {\bf 41} (1974), 305--318.

\bibitem{DF76}
{\sc D.~Dumont, and D.~Foata,}
\newblock Une propri\'et\'e de sym\'etrie des nombres to {Genocchi}.
\newblock {\em Bull.~Soc.~Math.~France \/} {\bf 104} (1976), 433--451.

\bibitem{DR94}
{\sc D.~Dumont, and A.~Randrianarivony,}
\newblock Derangements et nombres de {G}enocchi.
\newblock {\em Disc.~Math.\/} {\bf 132} (1994), 37--49.

\bibitem{DV80}
{\sc D.~Dumont, and G.~Viennot,}
\newblock A combinatorial interpretation of the {S}eidel generation of
  {G}enocchi numbers.
\newblock {\em Disc.~Math.\/} {\bf 6} (1980), 77--87.

\bibitem{FS70}
{\sc D.~Foata, and M.~{Sch\"utzenberger},}
\newblock {\em Th{\'e}orie G{\'eom\'etrique} des Polyn{\^o}mes {Eul\'eriens}}.
\newblock Lecture Notes in Math.~Vol.~138. Springer-Verlag, 1970.

\bibitem{G70}
{\sc J.~Gandhi,}
\newblock A conjectured representation of {G}enocchi numbers.
\newblock {\em Amer.~Math.~Monthly \/} {\bf 77} (1970), 505--506.

\bibitem{H93}
{\sc G.-N.~Han,}
\newblock Escaliers {\'evalu\'es} et nombres classiques.
\newblock {\em Publ.~I.R.M.A.~Strasbourg, Actes 24e S{\'e}minaire
  Lotharingien\/} (1993), 77--85.

\bibitem{HU79}
{\sc J.~Hopcroft, and J.~Ullman,}
\newblock {\em Introduction to Automata Theory, Languages, and Computation}.
\newblock Addison-Wesley, 1979.

\bibitem{RS73}
{\sc J.~Riordan, and P.~Stein,}
\newblock Proof of a conjecture on {G}enocchi numbers.
\newblock {\em Disc.~Math.\/} {\bf 5} (1973), 381--388.

\bibitem{Sl01}
{\sc N.~Sloane,}
\newblock {\em The On-Line Encyclopedia of Integer Sequences}.
\newblock Published electronically at
  {http://www.research.att.com/$\sim$njas/sequences}, 2004.

\bibitem{Y97}
{\sc S.~Yu,}
\newblock Regular languages.
\newblock In {\em Handbook of Formal Languages, Vol.~I\/} (1997), G.~Rozenberg
  and A.~Salomaa, Eds., Springer-Verlag, pp.~41--110.

\end{thebibliography}

\section*{Appendix A: Tables}

The triangle $B_{n,j}^{(3)}$ is A065747 in Sloane \cite{Sl01}. The
column $B_{n,4}^{(3)}$ is A065753. These are given in Figure~\ref{bnj3}.
The triangle $B_{n,j}^{(4)}$ is A065748 in Sloane, while column
$B_{n,5}^{(4)}$ is A065754. These are given in Figure~\ref{bnj4}.
Figure~\ref{bnj5} gives the triangle $B_{n,j}^{(5)}$, which is A065755.
Column $B_{n,6}^{(5)}$ is given by A065757 in Sloane.

\begin{figure}[H]
\begin{center}
\begin{tabular}{rccccccccc} \hline
$n \setminus j$ &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 \\ \hline
1      &amp; 1 &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;    &amp;    \\
2      &amp; 1 &amp; 3 &amp; 3 &amp;   &amp;   &amp;   &amp;   &amp;    &amp;    \\
3      &amp; 7 &amp; 30&amp;51 &amp; 42&amp;15 &amp;   &amp;   &amp;    &amp;    \\
4      &amp;145&amp;753&amp;1656&amp;1995&amp;1410&amp;567&amp;105&amp;  &amp; \\
5      &amp;6631&amp;39048 &amp; 100704 &amp; 149394 &amp; 140475 &amp; 86562 &amp; 34566 &amp; 8316 &amp; 945 \\
\hline
\end{tabular}
\caption{Values of $B_{n,j}^{(3)}$ for $1 \le n \le 5$ and $1 \le j \le 11$.}
\label{bnj3}
\end{center}
\end{figure}


\begin{figure}[H]
\begin{center}
\begin{tabular}{rcccccccccc} \hline
$n \setminus j$ &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11&amp; 12 &amp; 13 \\ \hline
1      &amp; 1 &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;    &amp;    &amp;    \\
2      &amp; 1 &amp; 4 &amp; 6 &amp; 4  &amp;   &amp;   &amp;   &amp;    &amp;    &amp;   \\
3      &amp; 15 &amp; 88 &amp;220 &amp; 304 &amp; 250 &amp; 120 &amp; 28 &amp;    &amp;&amp;    \\
4      &amp;1025&amp; 7308 &amp; 23234 &amp; 43420 &amp; 52880 &amp; 43880 &amp; 25088 &amp; 9680 &amp; 2340 &amp; 280 \\
\hline
\end{tabular}
\caption{Values of $B_{n,j}^{(4)}$ for $1 \le n \le 4$ and $1 \le j \le 13$.}
\label{bnj4}
\end{center}
\end{figure}

\begin{figure}[H]
\begin{center}
\begin{tabular}{rccccccccc} \hline
$n \setminus j$ &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11&amp; 12 &amp; 13 \\ \hline
1      &amp; 1 &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;    &amp;     \\
2      &amp; 1 &amp; 5 &amp; 10 &amp; 10  &amp;  5 &amp;      &amp;    &amp;    &amp;   \\
3      &amp; 31 &amp; 230 &amp; 755 &amp; 1440 &amp; 1760 &amp; 1430 &amp; 770 &amp; 260 &amp; 45    \\
\hline
\end{tabular}
\caption{Values of $B_{n,j}^{(5)}$ for $1 \le n \le 3$ and $1 \le j \le 13$.}
\label{bnj5}
\end{center}
\end{figure}



\bigskip
\hrule
\bigskip

\smallskip

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

\noindent \emph{Keywords:}  
Genocchi numbers, finite automata, enumeration of permutations.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001469}
\seqnum{A064624}
\seqnum{A064625}
\seqnum{A065747}
\seqnum{A065748}
\seqnum{A065753}
\seqnum{A065754}
\seqnum{A065755}
\seqnum{A065756} and
\seqnum{A065757}
.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 19 2003;
revised version received October 6 2004.  
Published in {\it Journal of Integer Sequences}, October 7 2004.

\bigskip
\hrule
\bigskip

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


\end{document}

</pre></body></html>