\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{amsthm}
\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://oeis.org/#1}{\underline{#1}}}

\begin{document}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

%%%%%%%%%%%%%%%%%%%%%%%% Author's conventions start #######################
\def\glqq{,\,\!\!,}
\def\grqq{`\,\!`}
\def\dstyle#1{$\displaystyle #1 $}
\def\dx{d_x}
\def\genSt#1{generalized Stirling numbers of the #1 kind\ }
\def\genSts{generalized Stirling numbers\ }
\def\Stirs{Stirling numbers}
\def\Stirtris{Stirling triangles\ }
\def\Stfs{Stirling numbers of the first kind\ }
\def\Stss{Stirling numbers of the second kind\ }
\def\Stfknm{{s(k;n,m)}}
\def\Stsknm{{S(k;n,m)}}
\def\Stfnm{$s(n,m)$\ }
\def\Stsnm{$S(n,m)$\ }
\def\Stfknmset{$\{s(k;n,m)\}$}
\def\Stsknmset{$\{S(k;n,m)\}$}
\def\Stsnmset{$\{S(n,m)\}$}
\def\Stfnmset{$\{S(n,m)\}$}
\def\Stsktri{${\bf S}(k)$}
\def\Stfktri{${\bf s}(k)$}
\def\noin{\noindent}
\def\pn{\par\noindent}
\def\ps{\par\smallskip}
\def\psn{\par\smallskip\noindent}
\def\pbn{\par\bigskip\noindent}
\def\Beq{\begin{equation}}
\def\Eeq{\end{equation}}
\def\Beqarray{\begin{eqnarray}}
\def\Eeqarray{\end{eqnarray}}
\def\sspgeq{\,\geq} 
\def\sspleq{\, \leq \,}
\def\sspkl{\, < \,}
\def\sspgr{\, > \,}
\def\sspeq{\, =\,}
\def\speq{\ =\ }
\def\sspdef{\, :=\,}
\def\spdef{\ :=\ }
\def\sspfed{\, =:\,}
\def\sspin{\, \in \,}
\def\spp{\ +\ }
\def\spm{\ -\ }
\def\sspp{\, +\ }
\def\sspm{\, -\ }
\def\sspto{\,\to\,}
\def\sspneq{\, \neq \,}
\def\sspequiv{\,\equiv\,}
\def\binomial#1#2{{#1} \choose {#2}}
\def\DnAMS#1#2{\frac{d{#1}}{d{#2}}}
\def\lprod{\prod\llap {\raise 8pt\hbox{$\leftarrow \thinspace$}}} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%% Author's conventions end %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



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


%\newtheorem{theorem}{Theorem}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{defin}[theorem]{Definition}
%\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
%\newtheorem{examp}[theorem]{Example}
%\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
%\newtheorem{rema}[theorem]{Remark}
%\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}
\newtheorem{note}[theorem]{Note}
\newenvironment{Note}{\begin{note}\normalfont\quad}{\end{note}}


\vbox {\vspace{6mm}}
\begin{center}
\vskip 1cm{\Large \bf
 Combinatorial Interpretation of Generalized \\
\vskip .1in
Stirling Numbers}\\ 
\vskip 1cm
\large Wolfdieter Lang \\
Institut f\"ur Theoretische Physik \\ 
Universit\"at Karlsruhe \\
D-76128 Karlsruhe \\
Germany\\
\href{mailto:wolfdieter.lang@particle.uni-karlsruhe.de}{\tt wolfdieter.lang@particle.uni-karlsruhe.de}
\end{center}

\vskip .2in

\begin{abstract}
A combinatorial interpretation of the earlier studied generalized \Stirs, emerging in a normal ordering problem and its inversion, is given. It involves unordered forests of certain types of labeled trees. Partition number arrays related to such forests are also presented. 
\end{abstract}

\section{Introduction and Summary}

The \genSt{second} \Stsknm, $k\in \mathbb Z,\  n,m \in \mathbb N_0$, appear in the normal ordering of powers $(x^k\,\dx)^n$ according to
\Beq\label{(1.1)}
(x^k\,\dx)^n\speq \sum_{m=1}^n\,S(k;n,m)\,
x^{m+(k-1)\,n}\,\dx^{\ m}\ \ .    
\Eeq
In the inverse problem the \genSt{first} \Stfknm\ enter as
\Beq\label{(1.2)}
x^{kn}\,\dx^{\ n}\speq \sum_{m=1}^{n} s(k;n,m)\, x^{(k-1)(n-m)}\,(x^k\,\dx)^m \, .  
\Eeq 
These numbers coincide for $k=1$ with the ordinary \Stirs. 
The author \cite{WL} has previously investigated the $k-$families of number triangles \Stsktri\ and \Stfktri.\footnote{In this reference the notation is different, namely $S2$ and $S1$ are used for $S$ and $s$, respectively. The associated number triangles $s2$ and $s1$ will not appear in the present work.}
For given $k$ the recurrence relations are:
\Beq\label{(1.3)}
S(k;n,m) \speq ((k-1)(n-1)+m)\,S(k;n-1,m) \spp S(k;n-1,m-1)\  
\Eeq
and
\Beq\label{(1.4)}
s(k;n,m)\speq -[(k-1)\,m+n-1]\,s(k;n-1,m)\spp s(k;n-1,m-1)\ , 
\Eeq
with the triangle conditions: \Stsknm $\sspeq 0$ for $n<m$, and $S(k;n,0)\sspeq \delta_{n,0}\,$. $\delta_{n,m}$ is the Kronecker symbol. Similarly:  $s(k;n,m)=0$ for $n<m$, and $s(k;n,0)\sspeq \delta_{n,0}\,$. The \Stsknm\ numbers have already been considered by Carlitz \cite{Carlitz} as special 
cases. See eq. 2 there, with $\mu\sspto 1$ and $\lambda\sspto k\sspm 1$. They also have been used by Comtet in \cite[4.Example]{Comtet} with $P_{n,l}(a)\sspeq S(a+1;n,l)$, where the recurrence and an explicit form involving a sum has been given.
The ordinary \Stss have been encountered in the reordering problem as stated above by  Grunert \cite[ \S 4 ff.]{Grunert}, where $C_n^{^{^{\llap {\it k}}}}\sspeq S(1;k,n)\sspeq S(k,n)$.\ps
A combinatorial interpretation of the \Stsnm numbers is well known: there are \Stsnm ways to partition a set of $n$ elements into $m$ nonempty subsets. Therefore, these numbers are also called {\sl subset numbers} in Graham et al.\ \cite [p.\ 244]{GKP}. See also Stanley \cite[p.\ 33]{Stanley1}, and Charalambides \cite[p.\ 96 and ch.\ 8]{Chara}. As a spin-off we shall find another interpretation as numbers of forests composed of certain increasing trees.\ps
The aim of this paper is to find combinatorial meanings
for the $k-$families $|\Stsknm|$ and $|\Stfknm|$.
Because all these lower diagonal number triangles are of the Jabotinsky (a special Sheffer) type, i.e., possess the binomial (also called exponential) convolution property, they count unordered $m-$forests composed of certain vertex labeled trees with $n$ vertices. These trees will be enumerated by $|S(k;n,1)|$ and $|s(k;n,1)|$, respectively,  for each $k\in \mathbb Z$. $S(k;n,1)$, for $k\in \mathbb N$, will be seen to give the number of plane, $k-$ary rooted increasing trees with $n$ vertices (including the root vertex). This stems from the fact that the exponential generating functions (e.g.f.) of these numbers are \cite{WL}
\Beq\label{(1.5)}
g2(k;x)\speq -1\sspp (1\sspp (1\sspm k)\,x)^{\frac{1}{1-k}}\, ,\ k\sspeq 2,3, \ldots ,
\Eeq
and \dstyle{g2(1;x)\sspeq -1\sspp e^x}. Such trees fit into the varieties of trees investigated by Bergeron et al.\ \cite{BFS}, leading to the stated result. $g2(0;x)\sspeq x$ represents the trivial one vertex tree, the root with label $1$.\ps
The signless (also called absolute) numbers $|S(-k;n,m)|\sspeq (-1)^{n-m}\, S(-k;n,m)$, $k\in \mathbb N_0$, have for their first column members  $|S(-k;n,1)|$ the e.g.f.
\Beq\label{(1.6)}
g2p(k;x)\speq 1\sspm (1\sspm (k+1)\,x)^{\frac{1}{k+1}}\, \sspeq -\,g2(-k;-x)\  ,\ k\in \mathbb N_0\ . 
\Eeq         
This also fits into the varieties of increasing trees considered by Bergeron et al.\ \cite{BFS} because plane increasing trees with vertices of outdegree $r\sspin \mathbb N_0$ come in ($r\sspp k\sspm 1$) types. They will be called (incomplete) $(r\sspp k-1)-$ary trees. In general an outdegree $r=0$ is reserved for the one vertex tree given by the root and for leaves (end vertices) of a tree. The one vertex tree is always considered separately because it always appears just once. Instead of ($r\sspp k\sspm 1$)-ary vertices one can also use a repertoire of $r\sspp k\sspm 1$ colors and chose $r$ of them to color the successors of a vertex with outdegree $r\sspeq 0,1, \ldots $. The color for the one vertex tree is taken as white (no color).  \ps
The non-negative numbers $|s(k;n,m)| \sspeq (-1)^{n-m}\,s(k;n,m),\ k\in \mathbb N_0$, with e.g.f. for the first column members $|s(k;n,1)|$ 
\Beq\label{(1.7)}
g1p(k;x)\speq \frac{1}{k\sspm 1}\left (-1\sspp \frac{1}{(1\sspm x)^{k-1}}\right )\, ,\ k\sspeq 0,2,3, \ldots 
\Eeq 
and $g1p(1;x)\sspeq -\,\ln(1\sspm x)$, do, for $k\sspgeq 3$, not count any of the tree varieties considered by Bergeron et al.\ \cite{BFS}. The case $k\sspeq 0$ is trivial, because there is just the trivial tree composed of one vertex, the root. The case $k\sspeq 1$
--- the ordinary unsigned \Stfs --- is encompassed by this study \cite{BFS} in that $|s(n,1)|$ counts the number of unordered (nonplane) increasing rooted trees with $n$ vertices. This provides another combinatorial meaning besides their usual cycle number characterization. It turns out that these trees are the nonplane analogons of the plane ones counted by $|S(-1;n,1)|$. Also the $k\sspeq 2$ instance, $|s(2;n,1)|$, fits into the above mentioned study because one finds that these numbers coincide with $S(2;n,1)$ which counts plane binary increasing trees. These are the unsigned Lah numbers, Sloane's OEIS \cite[$|\seqnum{A008297}|$\ (first column, $m=1$)]{Sloane}. It is also possible to give these numbers a meaning in the nonplane increasing tree setup. For all $k\sspgeq 3$, however, the \cite{BFS} varieties are not sufficient. In accordance with the recurrence relation one can give a somewhat trivial tree and forest interpretation for the $|s(k;n,m)|$ numbers. For example, $|s(3;n,1)|$ counts the number of $n$ vertex (including the root) increasing plane trees with only outdegrees $0$ and $1$ where every vertex of depth $d\in \mathbb N_0$ is of the $(d+3)$-ary type. The depth of a vertex is its distance from the root, the number of parents. Another equivalent way to define these numbers uses special depth dependent vertex coloring for trees with outdegrees $0$ and $1$. This situation pertains to all $k\sspgeq 3$, providing thus new classes of increasing trees not covered by the study \cite{BFS}.\ps
The non-negative numbers $s(-k;n,m)$ with $k\in \mathbb N$, have as e.g.f. for $s(-k;n,1)$
\Beq\label{(1.8)}
g1(-k;x)\speq \frac{1}{1\sspp k}(-1\sspp (1\sspp x)^{1+k})\sspeq -g1p(-k;-x)\,,\ k\in \mathbb N\ .   
\Eeq      
For every $k\in \mathbb N$ it follows that these numbers do also not count trees of the variety considered by Bergeron et al.\ \cite{BFS}. Again, the recurrence relation~\eqref{(1.4)} helps to identify trees and forests with only outdegrees $0$ and $1$ which are counted by these $s(-k;n,m)$ numbers.\ps
Finally, maps from the set of partitions of $n$ with $m$ parts to numbers counting various types of forests considered in this work are presented. These number arrays will be called partition number arrays. The generalized Stirling numbers are sums over these array numbers for fixed part number $m$.   

\section{Generalized Stirling numbers of the second kind}

As anticipated in the Introduction the \genSts $|S(k;n,m)|$ and $|s(k;n,m)|$ count for many $k$ values (but not for all) certain $m$-forests of increasing trees,
either plane or nonplane, which fall into the varieties of trees studied by Bergeron et al.\ \cite{BFS}.
Therefore, some results from this study which are important for this work will be recapitulated.\ps
We start with some definitions and refer the reader to Stanley \cite[ Appendix, pp. 293--5]{Stanley1}, for general definitions regarding trees and forests. For trees the notions {\it plane} and {\it ordered} are synonyms. This may seem confusing because, e.g., in Fig. A-2, p. 295 of this reference, the second tree would be equivalent to the last one if in the plane a rotation of subtrees around the root vertex would be allowed. 

\begin{definition}\label{D1} 
A {\sl labeled tree} of size $n$, $T_n$, is a rooted tree with $n$ vertices (nodes), including the root vertex, labeled with distinct elements from the set $[n]\equiv I_n\sspeq \{1,2, \ldots ,n\}$.
\end{definition}

\begin{definition}\label{D2} 
An {\sl increasing tree} of size $n$ is a labeled tree of size $n$ with the sequence of labels from the root to any leaf (end vertex with degree $1$, outdegree $0$) increasing.
\end{definition}

\begin{example}\label{E0} 
Stanley \cite[ p.\ 295, {\it Fig}. A-2]{Stanley1} shows some ordered increasing trees of size 6. There are more than the two types shown, viz., $C_5\sspeq 42$ (the fifth Catalan number). Altogether there are $9!!\sspeq 945$ ordered increasing trees of size 6 (compare with our Figure~\ref{F4}).
\end{example}

For the analysis the most important object is the generating function (g.f.) for the numbers $s_r$ of available vertex types with outdegree $r$. For the root, the outdegree coincides with the degree. The trivial one vertex tree consists of the root with $r=0$, and there is always only one vertex type $s_0\sspeq 1$. For trees with more than one vertex, the leaves (end vertices) have also $r=0$ but degree $1$. For ordered (plane) trees the ordinary generating function (o.g.f.) \dstyle{\phi(y)\sspeq 1\sspp \sum_{r\geq 1}\, s_r\, y^r} enters, and for unordered (nonplane) trees the e.g.f. \dstyle{\varphi(y)\sspeq 1\sspp \sum_{r\geq 1}\, s_r\,\frac{y^r}{r!}} is used. For example, for incomplete ternary (3-ary) trees one has $\phi(y)\sspeq 1\sspp 3\,y\sspp 3\,y^2\sspp y^3$ in the ordered case, and 
 \dstyle{\varphi(y)\sspeq 1\sspp 3\,y\sspp 3\,\frac{y^2}{2!}\sspp \frac{y^3}{3!}} in the unordered case. $s_0=1$, as mentioned above, and a ternary vertex has three possible out legs (usually drawn downwards at equal angles). Therefore $s_1=3$ because there are three possible legs to choose. $s_2=3$ because one of the three possible legs is not present. $s_3=1$ because there is only one type of vertex with all three legs present. The ordered trees shown in Stanley \cite[{\it Fig}. A-2, p. 295]{Stanley1} could belong to $\phi(y)\sspeq 1\sspp 2\,y \sspp y^2\sspeq (1\sspp y)^2$, i.e., ordered (incomplete) binary trees.

\begin{proposition}\label{P1} \cite{BFS}

If \dstyle{Y(z)\sspeq \sum_{n\geq 0}\,Y_n\,\frac{z^n}{n!}} is the e.g.f. for $\{Y_n\}$, with $Y_n$ the number of increasing labeled trees of size $n$, and $\phi(y)$, resp. $\varphi(y)$, the outdegree g.f.s, then
\Beq\label{(2.1)} 
\int_{0}^{Y(z)}\,\frac{dy}{\Phi(y)} \sspeq z, \text{with}\ \Phi\in\{\phi,\varphi\}\ . 
\Eeq
\end{proposition}

A differential way of writing this is \dstyle{\frac{dY(z)}{dz\ \ \ \ }\sspeq \Phi(Y(z))} together with the initial condition $Y(0)\sspeq 0$ (no tree of size $0$). The explicit solution is written in the form of an {\sl Abel} equation cf. \cite[p.\ 14, (1.17) and footnote 7]{Alexander}). 
\Beq\label{(2.2)}
Y(z)\sspeq F^{[-1]}\left[ F(0)\sspp z \right]\, , \text{with}\ F[y]\sspdef \int\,\frac{dy}{\Phi(y)}\ . 
\Eeq
Here $F^{[-1]}$ denotes the compositional inverse of $F$, the primitive (anti-derivative) of $1/\Phi$.

\begin{proof}
First one recalls that \dstyle{\int_0^z\,W(t)\, dt} is the e.g.f. for numbers $\{w_{r-1}\}$ if $W(t)$ is the e.g.f. for numbers $\{w_r\}$ (index shift by $-1$ {\it via} integration). In the application below this integration will account for the inclusion of the extra root vertex if powers of $t$ correspond to the number of vertices. The proof of the solution of the differential eq. for $Y(z)$, i.e., \dstyle{Y(z)\sspeq \int_{0}^z\,\Phi(Y(t))\, dt}, is based on the recursive structure of increasing trees characterized by the outdegree g.f. Increasing trees $T_n$ of size $n$ are composed of ordered, resp. unordered, $r-$forests ($r\sspgeq 1$) of such trees of size $n-1$. These $r$ trees are connected to the root of the tree $T_n$ by $r$ lines ending at the root labeled $1$. The $r-$forest vertices are labeled with $2,3, \ldots ,n$. These $r-$forests have e.g.f. $Y^r(z)$, resp. \dstyle{\frac{1}{r!}\,Y^r(z)}. Therefore the sum over all possible outdegrees $r\sspgeq 0$ of the root vertex yields \dstyle{1\sspp \sum_{r\sspgeq 1}\, s_r\, Y^r(t) \sspeq \phi(Y(t))}, resp. \dstyle{1\sspp \sum_{r\sspgeq 1}\, s_r\, \frac{Y^r(t)}{r!} \sspeq \varphi(Y(t))}. Here we use the variable $t$ instead of $z$. The extra root vertex with label $1$ is then accounted for by the index shift by $-1$, and, as explained above, this is achieved by integration, resulting in 
\Beq\label{(2.3)}
Y(z)\sspeq \int_0^z\,\Phi(Y(t))\, dt,\  \text{hence}\ Y(0)\sspeq 1\, . 
\Eeq
\end{proof}
\begin{Note}\label{N1}
$Y^r(z)$, and also\dstyle{\frac{1}{r!}\,Y^r(z)}, are given by the multinomial theorem in terms of the partition number array  called $M_3$ in Abramowitz and Stegun \cite[ p. 831]{ASt}. See also Slone's OEIS \cite[\seqnum{A036040}]{Sloane}. Within each of the $r$ parts of the partition of $n$ the order is taken w.l.o.g. increasing. We shall expand on this in Section 4.
\end{Note}

\begin{Note}\label{N2} 
It is easy to see that  the number of ordered rooted trees of size $n$ (including the root vertex) is $C_n$, the $n$th Catalan number. See Slone's OEIS \cite[\seqnum{A000108}]{Sloane}. The tree number o.g.f. $c$ satisfies $c(x)\sspeq \sum_{r=0}^\infty\,(x\,c(x))^r\sspeq \frac{1}{1\sspm x\,c(x)}$, which is obvious from the recursive structure of these trees. The extra $x-$factor accounts for the root vertex. See also Conway and Guy \cite[p. 99]{CG}, where these trees are called plane rooted bushes. This coincides with the eq. for the o.g.f. for Catalan numbers.
\end{Note} 

\begin{Note}\label{N3}  
Cayley's classical result from 1889 \cite[pp. 23, 37, 66]{Stanley2} and \cite[p,\ 39]{BiggsLloydWilson} on the number $t_n$  of unordered trees of size $n$ with any labeling from $I_n$ can be obtained in a similar manner. The outdegree e.g.f. is now $\varphi(z)\sspeq \exp(z)$ because $s_r\sspeq 1$ for all $r\sspgeq 0$. The e.g.f. for the numbers $\{t_n\}$ of such trees is, by their recursive definition,  $Y(z)\sspeq z\,\varphi(Y(z)) \sspeq z\, \exp(Y(z))$, because the root can now have any of the labels $1,2, \ldots ,n$, and $\{n\,f_{n-1}\}$ is exponentially generated by $z\, f(z)$ if $\{f_n\}$ is exponentially generated by $f$. This holds for any $r$-forest. Then the sum over the outdegrees $r\sspgeq 0$ of the root vertex is taken. The just found implicit equation for $Y(z)$, can be solved {\it via} Lagrange inversion as
\Beq\label{(2.4)}
Y(z)\sspeq \sum_{n=1}^{\infty}\, \frac{x^n}{n!}\,\left.\left( {\DnAMS{^{n-1}}{a^n\ \ }}\, \varphi^n(a)\right)\right| _{a=0} \sspeq \sum_{n=1}^{\infty}\,t_n\, \frac{z^n}{n!} \ . 
\Eeq   
With $\varphi(a)\sspeq \exp(a) $ this becomes the classical result $t_n\sspeq n^{n-1}$. This is the sequence $[1,2,9,64,625, \ldots ]$, see Sloane's OEIS \cite[\seqnum{A000169}]{Sloane}.
\end{Note}

\begin{example}\label{E1} {\bf Ordered increasing (incomplete) $k-$ary trees}

For such trees the outdegree e.g.f. is $\varphi_k(y)\sspeq (1\sspp y)^k$ 
because there are $s_{k;r}\sspeq {\binomial{k}{r}}$ different types of outdegree $r\sspgeq 1$ vertices. E.g. $k=4, r=2$: $s_{3;2}\sspeq 6$ from chosing two lines out of a $4-$ary vertex. \dstyle{F_k(y)\sspeq \int\,dy \frac{1}{(1\sspp y)^k}}, which is (up to a constant) $F_1(y)\sspeq \ln(1\sspp y)$ and $F_k(y)\sspeq \frac{1}{1-k}\, (1\sspp y)^{1-k}$, $k\sspgeq 0, \ k\sspneq 1$. $F_1^{[-1]}(x)\sspeq \exp(x)-1$, and \dstyle{F_k^{[-1]}(x)\sspeq -1\sspp ((1-k)\,x)^{\frac{1}{1\sspm k}}}. Therefore, $Y_1(z)\sspeq \exp(z)\sspm 1$, and \dstyle{Y_k(z)\sspeq -1\sspp \left((1-k)\,(\frac{1}{1-k}\sspp z) \right)^{\frac{1}{1-k}}\sspeq -1\sspp \left(\,1\sspp (1-k)\, z\,\right)^{\frac{1}{1-k}} }. for $k\sspgeq 0, k\sspneq 1$. $k=1$ applies for unary trees, and for $k=0$ one has $Y_0(z)=z$ corresponding to the trivial tree with just one vertex, the root with label $1$. For binary trees $Y_2(z)\sspeq \frac{z}{1\sspm z}$, producing the sequence $\{n!\}_1^\infty$, Sloane's  OEIS \cite[\seqnum{A000142}]{Sloane}.
\end{example}

\begin{proposition}\label{P2}
$|S(k;n,m)|$, resp. $|s(k;n,m)|$, with $k\in \mathbb Z$, is the number of unordered $m-$forests  composed of $m$ trees with altogether $n$ vertices (including the $m$ roots). The number of such trees is exponentially generated by the $g2$ and $g1$ functions given in the Introduction. 
\end{proposition}

\begin{proof}
This follows immediately from the Jabotinsky (a special Sheffer) structure of the lower diagonal number triangles ${\bf S}(k)$, resp. ${\bf s}(k)$. See Knuth \cite{Knuth} for a general discussion of Jabotinsky triangles. In other words, they are exponential convolution triangles. This means that the e.g.f. for the $m-$th column numbers ($n\sspgeq m$) is for $k\in \mathbb N$ given by 
\Beqarray
g2_m(k;x)&\sspdef& \sum_{n=0\,(m)}\, S(k;n,m)\, \frac{x^n}{n!}\ \sspeq \frac{1}{m!}\, (g2(k;x))^m , \ \ \text{resp.} \label{(2.5)}  \\
 g1p_m(k;x)&\sspdef& \sum_{n=0\,(m)}\, |s(k;n,m)|\, \frac{x^n}{n!}\sspeq \frac{1}{m!}\, (g1p(k;x))^m \, .  
\label{(2.6)}
\Eeqarray
Similar eqs. hold with $-k \sspin \mathbb N$ for $g2p_m(k;x)$ and $g1_m(k;x)$.
The forests are unordered due to the e.g.f. Jabotinsky structure with the factor $1/m!$.
\end{proof}

Thus one only has to find a combinatorial interpretation for the $m=1$ column numbers of such lower triangular Jabotinsky matrices. The column $m=0$ is not relevant, it is always $[1,0,0, \ldots ]^\top$. 

\begin{proposition}\label{P3} $S(k;n,1), k\sspgeq 0$ 

$S(k;n,1),  k\sspgeq 1$, is the number of ordered rooted $k-$ary trees of size $n$ (including the root vertex) increasingly labeled with distinct elements from $I_n\sspeq \{1,2, \ldots ,n\}$. For $k=0$ there is only one vertex ($n=1$), the root, and $S(0;n,1)\sspeq \delta_{n,1}$.
\end{proposition}

\begin{proof} 
From Proposition~\ref{P1}, the Example~\ref{E1}, and the e.g.f.s\ \  $g2(k;x)$ given in  ~\eqref{(1.5)}.
\end{proof}

\begin{example}\label{E2} $S(3;n,1),\  n=1,2,3,4$. 

In  Figure ~\ref{F1} the ordered ternary ($3$-ary) trees with sizes $n\sspeq 1,2,3$ and $4$ are shown without vertex labeling. The (hidden) root label is used there to numerate the different trees. The number of such trees of size $n$ is $[1,3,12,55, \ldots
]$, i.e., \dstyle{{\binomial{3n}{n}}/(2n+1)\sspeq {\binomial{3\,n}{n-1}}/n}. See Sloane's OEIS \cite[\seqnum{A001764}]{Sloane}. This formula follows from the general one for $k-$ary trees, see Note~\ref{N4} below. If now increasing trees are considered, one finds for the $12$ trees with size $n=4$, in the order given in Figure~\ref{F1}, the number of different labelings $[2,1,2,2,1,1,1,1,1,1,1,1]$, altogether 15, and indeed $S(3;3,1)\sspeq 15\sspeq 5!!\sspdef 1\cdot 3\cdot 5$. For the triangle ${\bf S}(3)$ see Sloane's OEIS \cite[\seqnum{A035342}]{Sloane}. For $n=4$ the $55$ unlabeled trees shown in Figure~\ref{F1} can be labeled increasingly in $[3!,2,1,18\cdot 3, 4\cdot 2, 6\cdot 1, 2\cdot 2, 12\cdot 1, 2\cdot 2, 8\cdot 1]$   ways. Altogether this is $105$, and indeed $S(3;4,1)\sspeq 105\sspeq 7!!$. 
\end{example}

\begin{Note}\label{N4}  
The number $t_k(n)$ of ordered rooted $k-$ary trees of size $n$ is obtained from the equation for the o.g.f. $T_k(x)\sspeq \sum_{n=1}^\infty\, t_k(n)\,x^n$, viz., \dstyle{T_k(x)\sspeq 1\sspp x\,(T_k(x))^k\sspeq \frac{1}{1\sspm x\, (T_k(x))^{k-1}}}, via Lagrange inversion. This yields the Pfaff-Fuss-Catalan- or $k-$Raney sequences \cite[ p. 347, (7.66)]{GKP} and Sloane's OEIS \cite[\seqnum{A000108}, \seqnum{A001764}, \seqnum{A002293}, \seqnum{A002294}, \seqnum{A002295}, \seqnum{A002296}, \seqnum{A007556}, \seqnum{A062994}]{Sloane} for $k=2,3, \ldots ,9$. The formula is\ps 
\dstyle{t_k(n)\sspeq {\binomial{k\,n}{n}}\, \frac{1}{(k-1)\,n+1}\sspeq {\binomial{k\,n+1}{n}}\,\frac{1}{k\,n+1}}.
\end{Note}

\begin{proposition}\label{P4} {\bf Organic growth of ordered} $k${\bf-ary increasing trees}

All rooted ordered increasing $k-$ary trees of size $n$ are obtained from all such trees of size $n-1$ by adding in all possible ways, respecting the $k-$arity, the branch with leaf labeled $n$ to every vertex of each tree of size $n-1$.
\end{proposition}

\begin{proof}
It is clear that by this growth prescription the increasing labeling is respected. It is also clear that it leads only to size $n$ trees of the $k-$ary type, because the new branch can only be appended in free $k-$ary directions from each vertex. Given any such size $n$ tree, an amputation of the branch with leaf labeled $n$ will produce a tree of size $n-1$ of the considered type. In fact, no different size $n-1$ trees of this type can grow to the same size $n$ tree. This shows that all such size $n$ trees are grown. 
\end{proof}

\begin{proposition}\label{P5} {\bf Recurrence for $S(k;n,1),\ k\sspin \mathbb N$, recovered}

$a^{(k)}_n$, the number of size $n$ rooted ordered $k-$ary increasing trees satisfies the recurrence
\Beq\label{(2.7)}
a^{(k)}_n\sspeq (k\,(n-1)\sspm (n-2))\,a^{(k)}_{n-1}\, ,\ \ a^{(k)}_1\sspeq 1,\ n\sspeq 2,3,4,\ldots
\Eeq
\end{proposition}

\begin{proof}
Consider any size $(n-1)$ tree. The number of lines $E$ of such a tree is $n-2$. Clearly, $\sum_{i=1}^{n-1}\, r_i\sspeq E\sspeq n-2$ with the outdegree $r_i$ of the vertex with label $i$. Now attach the branch with leaf labeled $n$ to the vertex with label $i$ . This can be done in $k-r_i$ ways (using one of the free $k-$ary line places). Summing over all $n-1$ vertices thus yields $\sum_{i=1}^{n-1}\,(k\sspm r_i)\sspeq k\,(n-1)-(n-2)$. Therefore, any of the $a^{(k)}_{n-1}$ trees of size $n-1$ grows to $k\,(n-1)-(n-2)\sspeq (k-1)\,(n-1)\sspp 1$ different new trees of size $n$. This recurrence coincides with the one for $S(k;n,1),\ k\in \mathbb N$, obtained from ~\eqref{(1.3)} as it should due to Proposition~\ref{P3}. For the solution of this recurrence see \cite{WL}.
\end{proof}

The non-negative numbers $|S(-k;n,1)|\sspeq (-1)^{n-1}\,S(-k;n,1)$, $k\in \mathbb N_0$, also fit into the varieties of increasing trees studied by Bergeron et al.\ \cite{BFS}.

\begin{proposition}\label{P6} $|S(-k;n,1)|,\ k\sspgeq 0$

$|S(-k;n,1)|$, $k\in \mathbb N_0$, is the number of ordered rooted increasing trees of size $n$ with outdegree o.g.f. \dstyle{\Phi_k(y)\sspeq \frac{1}{(1-y)^k}}, i.e., \dstyle{s_{k;r}\sspeq {\binomial{r+k-1}{k-1}}\sspeq {\binomial{r+k-1}{r}}}. For $k=0$ one has $s_{0;r}\sspeq \delta_{r,0}$.
\end{proposition}

\begin{proof}
 Proposition~\ref{P1}, ~\eqref{(2.2)}\ , leads to \dstyle{F_k(y)\sspeq \int\,dy\,(1-y)^k \sspeq -\frac{1}{k+1}\,(1\sspm y)^{k+1}} with \pn
$F_k(0)\sspeq -1/(k+1)$. \dstyle{F_k^{[-1]}(x)\sspeq 1\sspm (-(k+1)\,x)^{1/(k+1)}}. \dstyle{Y_k(z) \sspeq 1\sspm (1\sspm (k+1)\, z)^{\frac{1}{k+1}}\sspeq g2p(k;z)}, with the e.g.f. of the numbers $\{|S(-k;n,1)|\}$ given in ~\eqref{(1.6)}. 
\end{proof}
The numbers $s_{k;r}$ defined above show that for given $k\sspgeq 1$ one has to consider ordered rooted trees with $(r\sspp k\sspm 1)-$ary vertices if their outdegree is $r\sspgeq 1$. If $r\sspeq 0$ (for the single root vertex or the leaves) there is only one vertex type. This leads to the following corollary.

\begin{corollary}\label{C1}
 $|S(-k;n,1)|,\ k\in \mathbb N_0$, is the number of ordered rooted increasing trees of size $n$ with outdegree $r\sspgeq 0$ vertices of the $(r\sspp k\sspm 1)-$ary type.
\end{corollary}

Trees of this type, with outdegree $r$ dependent arity, will be called rooted ordered $(r\sspp k\sspm 1)-$ary increasing trees in the sequel.   

\begin{example}\label{E3} $|S(-3;n,1)|$
       
The triangle $|{\bf S}(-3)|$ (meaning the signless triangle ${\bf S}(-3)$) is given in Sloane's OEIS \cite[\seqnum{A000369}]{Sloane}. For the sequence $|S(-3;n,1)|$, the $m=1$ column of this triangle, see \seqnum{A008545}. From $s_{3;r}\sspeq {\binomial{r+2}{r}}$ one has $(r\sspp 2)-$ary vertices for outdegree $r$. First one considers the ordered rooted trees of size $n$ without vertex labels.
For $n\sspeq 1,2,3,4,5$ see e.g., Conway and Guy \cite[p. 99, {\it Fig. 4.7}]{CG} (called rooted plane bushes, with missing leave vertices, and depicted upside-down). Then the multiplicity for increasing labelings is determined. See our Figure~\ref{F2} for $n=1,2,3,4$, Figure~\ref{F3} for $n=5$ and Figure~\ref{F4} for $n=6$.\ps
Instead of using $(r\sspp k\sspm 1)-$ary vertices of outdegree $r\sspgeq 0$ which can become cumbersome to draw, it is simpler to color the $r$ successor vertices of an outdegree $r$ vertex from a repertoire of pairwise different colors $C_i, i\sspeq 1,2, \ldots
,(r\sspp k\sspm 1)$. (These colors $C_i$ will not be confused with Catalan numbers.) The color indices are taken as $C_{i_1}, C_{i_2}, \ldots
,C_{i_r}$, $1\sspleq i_1\sspkl i_2\sspkl \cdots \sspkl i_r\sspleq (r\sspp k\sspm 1)$ if the vertices are considered from the left to the right. The root vertex can have any color, say $C_0$. This coloring is done independently for each non-root vertex. In this way the different colors mimic the different possible leg positions for an $(r\sspp k\sspm 1)-$ary vertex. This is the content of the next corollary.
\end{example}

\begin{corollary}\label{C2}{\bf Rooted ordered vertex colored increasingly labeled trees}
 
$|S(-3;n,1)|, k\in\mathbb N_0$, is the number of rooted ordered increasing trees of size $n$ and the $r$ successor vertices of a predecessor vertex with outdegree $r$ have colors $C_{i_1}, C_{i_2}, \ldots ,C_{i_r}$, $1\sspleq i_1\sspkl i_2\sspkl \ldots \sspkl i_r\sspleq (r\sspp k\sspm 1)$ when read from the left to the right. The root vertex carries a color $C_0$.  
\end{corollary}

\begin{example}\label{E4}
For $k=3$ the tree with $n=4$ vertices and outdegree $r=3$ of the root vertex can have for its leaves ${\binomial{5}{3}}\sspeq 10$ color configurations $C_1\, C_2\,C_3$, $C_1\,C_2\,C_4$, $C_1\,C_2\,C_5$,  $C_1\,C_3\,C_4$,  \ldots , $C_3\,C_4\,C_5$.
The root has color $C_0$. Each of these $10$ colored trees is then labeled increasingly, producing altogether $10\cdot3!\sspeq 60$ such trees with $r_1\sspeq 3$. The root has, of course, label 1. Cf. Figure~\ref{F2}, $n=4$, first row.

Also the specific trees of size $n$ counted by $|S2(-3;n,1)|$, $k\in \mathbb N$, can be obtained from those of size $n-1$ by adding a branch with a leaf labeled $n$. In the drawing of these trees one uses $s$ branches of two kinds for  an $s-$ary vertex with outdegree $r\sspleq s$; a solid line for each of the $r$ outgoing lines and $s-r$ dashed lines for the remaining ones. These $s$ lines of two types are usually drawn downwards form the vertex in a symmetric way, i.e.. the relevant angle is $\pi/(s+1)$. The first and the last line have this angle with the imagined horizontal reference axis through the vertex. Neighbouring lines also span this angle. 
\end{example}

\begin{proposition}\label{P7} {\bf Organic growth of ordered $(r\sspp k\sspm 1)$-ary increasing trees}

All rooted ordered $(r\sspp k\sspm 1)-$ary trees of size $n$ are obtained from all such trees of size $n-1$ by adding in the following way a branch with leaf labeled $n$ to every vertex of each tree of size $n-1$. A vertex with outdegree $r$ in the size $n-1$ tree has $(r\sspm 1\sspp k)\sspm r\sspeq k\sspm 1$ dashed lines. The solid line with leaf labeled $n$ is now put at any of the new $r\sspp k$ places available for an $(r\sspp k)-$ary vertex. The type (solid or dashed) of the remaining lines are carried over from the vertex of the tree of size $n-1 $ to the remaining $r\sspp k\sspm 1$ line places. In this $n-1\sspto n$ growing process the angle between the lines is diminished, of course.
\end{proposition}

\begin{proof}
 It is clear that by this growth prescription the increasing labeling is respected. 
By construction only trees of the considered $(r\sspm 1\sspp k)-$ary type are grown. In fact, all rooted ordered $(r\sspm 1\sspp k)-$ary increasing trees of size 
$n$ are grown this way. Just amputate the (solid) leg with label $n$ and enlarge the angles between the remaining lines of both types, appropriate for the arity of the vertex in the size $n-1$ tree. No different size $n-1$ trees of the considered type can grow to the same size $n$ tree.
\end{proof}

\begin{proposition}\label{P8} $|S(-k;n,1)|$ {\bf recurrence recovered}
 
$b^{(k)}_n$, the number of size $n$ rooted ordered $(r\sspm 1\sspp k)-$ary increasing trees satisfies the recurrence
\Beq\label{(2.8)}
b^{(k)}_n\sspeq (k\,(n-1)\sspp (n-2))\,b^{(k)}_{n-1}\, ,\ \ b^{(k)}_1\sspeq 1,\ n\sspeq 2,3,4, \ldots
\Eeq
\end{proposition}

\begin{proof}
 Consider any size $(n-1)$ tree of the relevant type. See the proof of Proposition~\ref{P5} for  $\sum_{i=1}^{n-1}\, r_i\sspeq n-2$ with the outdegree $r_i$ of the vertex with label $i$. The growing prescription of Proposition~\ref{P7} shows that for each vertex $v_i$ with label $i$ and outdegree $r\sspgeq 0$ there are $k\sspp r$ possible places for the line with label $n$, because the new vertex $v_i$ has become $(k\sspp r)-$ary in the size $n$ tree. The other $(k\sspp r\sspm 1)$ lines of both types are carried over (with diminished angle between the lines) from the vertex $v_i$ of the size $n-1$ tree. For every vertex $v_i$ there are thus $(k\sspp r)$ new configurations for this vertex labeled $i$ in the size $n$ tree. Summing over all vertices of the size $n-1$ tree yields $\sum_{i=1}^{n-1}\,(k\sspp r_i)\sspeq k\,(n-1)+(n-2)$. Therefore, any of the $b^{(k)}_{n-1}$ trees of size $n-1$ grows to $k\,(n\sspm1)\sspp (n\sspm2)\sspeq (k\sspp 1)\,(n-1)\sspm 1$ different new trees of size $n$. The shown recurrence coincides with the one for $|S(-k;n,1)|,\ k\in \mathbb N$, obtained from ~\eqref{(1.3)} as it should due to Corollary~\ref{C1}.  For the solution of this recurrence see \cite{WL}.
\end{proof}

\begin{Note}\label{N5} {\bf Coloured increasing trees}

Also the colored version of the increasing trees described in Corollary~\ref{C2} can be grown by appending a new line with label $n$ and a certain color to every vertex $i$ with outdegree $r_i$, i.e., $r_i$ colored successors. The growth prescription can be immediately read off from the corresponding $(r_i\sspp k\sspm 1)-$ary vertex labeled $i$. 
One just observes the pattern of dashed (unused) and solid lines from this vertex in the size 
$n-1$ tree. It shows which colors from the repertoire $\{C_1, C_2, \ldots
,C_{r_i\sspp k\sspm 1}\}$ are used (correspond to solid lines) in this order. Each such vertex labeled $i$ with colored successors is then grown to precisely $r_i\sspp k$ new vertices with label $i$ by appending the line with label $n$ in all possible $r_i\sspp k$ colors 
available for an outdegree $r_i\sspp 1$ vertex. The remaining $r_i$ successor lines carry the labels in the same order like in the original size $n\sspm 1$ tree and the colors follow the pattern of the original  size $n\sspm 1$ tree (corresponding to the pattern of dashed and solid lines in the  $(r_i\sspp k\sspm 1)-$ary version), This means that in general the color of a successor vertex with a given label will be different in the original and the grown tree. An example will make this clear. Take $k\sspeq 2$, $r_i\sspeq 3$, $n\sspeq 7$. In the size $n\sspm 1\sspeq 6$ tree $r_i\sspp k\sspm 1\sspeq 4$ different 
colors are available for the three successor vertices which have one from ${\binomial{6}{3}}\sspeq 20$ possible labelings, say $3,2,6$, in this order. Consider the vertex coloring $C_1,C_2,C_4$. This can be encoded as\ \ $\begin{matrix} 3&2&6\\1&2&4\end{matrix}$\ \ where the upper row stands for the labels and the lower one for the color indices.
The grown tree of size $7$  will now have attached to this vertex $i$ a leg with the vertex labeled $7$ and e.g., color $C_4$. This will correspond to the new vertex $i$ with successor vertices\ \ $\begin{matrix} 3&2&7&6\\1&2&4&5\end{matrix}$\ \ . $C_3$ is missing because in the original color pattern the third color was missing and in the grown case the available colors are $C_1,C_2,C_3,C_5$ because the label $7$ vertex has color $C_4$. The third color,
here $C_3$, has to be skipped, thus producing the color sequence $C_1,C_2,C_4,C_5$ for the successor vertices. The other four grown successor vertices are then \ \ $\begin{matrix} 7&3&2&6\\1&2&3&5\end{matrix}$\ \ ,\ \ $\begin{matrix} 3&7&2&6\\1&2&3&5\end{matrix}$\ \ ,\ \ $\begin{matrix} 3&2&7&6\\1&2&3&5\end{matrix}$\ \ and \ \ $\begin{matrix} 3&2&6&7\\1&2&4&5\end{matrix}$\ .
\end{Note}

\section{Generalized Stirling numbers of the first kind}

The generalized non-negative Stirling numbers of the first kind $|s(k;n,m)|\sspeq (-1)^{n-m}\,s(k;n,m)$, $k\in \mathbb N$, which arise from the (infinite) matrix inversion ${\bf s}(k)\, {\bf S}(k)\sspeq {\bf 1}_\infty\sspeq {\bf S}(k)\, {\bf s}(k)$ (considered for $N\times N$ matrices with $N$ arbitrary large) are also of the Jabotinsky type, and therefore these numbers will also count unordered $m-$forests of trees of size $n$ provided one can define them such that there are $|s(k;n,1)|$ such trees. From the e.g.f. of the numbers $|s(k;n,1)|$, given in ~\eqref{(1.7)}, one derives the outdegree function $\Phi_k(y)$ by putting $Y_k(z)\sspeq g1p(k;z)$ in Proposition $1$, computing \dstyle{\frac{d\,Y_k(z)}{dz\ \ \ \ \ \ }\sspeq (1\sspm z)^{-k}} and rewriting this for $k\sspgeq 2$ as $(1\sspp (k-1)\,Y_k(z))^{\frac{k}{k-1}}$. Therefore
\Beq\label{(3.1)} 
\Phi_k(y)\sspeq (1\sspp (k-1)\,y)^{\frac{k}{k-1}}\ ,\ k \sspgeq 2,
\Eeq      
and from $Y_1(z)\sspeq -\ln(1\sspm z)$ one finds $\Phi_1(y)\sspeq \exp(y)$\,.

Because for every outdegree $r$ the vertex type number $s_r$ has to be a non-negative integer one needs for $k\sspeq 1$ the e.g.f. $\varphi(y)\sspeq \exp(y)$. Therefore $|s(1;n,1)|\sspeq |s(n,1)|$ counts unordered (nonplane) increasing trees of size $n$. This provides another combinatorial meaning of these numbers besides the number of permutations of $n$ elements which in their cycle decomposition consist of just one cycle. This number is, of course, $(n-1)!$. 

\begin{example}\label{E5}
The number of unordered increasing trees of size $4$ with one type of vertex for all outdegrees $r\sspgeq 0$ is $|s(1;4,1)|\sspeq 3!$ because there are four types of trees, viz., the ones with $r_1\sspeq 3$; $r_1\sspeq 2$; $r_1\sspeq 1$,  $r_2\sspeq 2$ and  $r_i\sspeq 1$, $i=1,2,3$, which come respectively in $1,3,1$ and $1$ increasing labelings. Remember that $r_i$ is the outdegree of the vertex with label $i$. Hence $1\sspp3\sspp 1\sspp 1\sspeq 6\sspeq 3!$.
\end{example}

For $k\sspeq 2$ one can take the outdegree o.g.f. $\phi_2(y)\sspeq (1\sspp y)^2$ or the e.g.f. \dstyle{\varphi_2(y)\sspeq 1\sspp 2\,y\sspp 2\,\frac{y^2}{2!}}. In the first case one has to consider  ordered increasing (incomplete) binary trees. Such trees have already been encountered in the last section, where they were shown to be counted by $S(2;n,1)$, the unsigned Lah numbers, Sloane's OEIS \cite[$|\seqnum{A008287}|$ ]{Sloane}. Therefore $ |s(2;n,1)|\sspeq S(2;n,1)$, which is also clear from their recurrence relations with inputs. In the outdegree e.g.f. case $ |s(2;n,1)|$ counts unordered (nonplane) increasing trees with two types of vertices for both outdegrees $1$ and $2$ because $s_1\sspeq 2\sspeq s_2$. We shall use two-colored vertices in both outdegree cases. No other outdegree besides $r\sspeq 0$, coming only in one vertex type ($s_0\sspeq 1$), is allowed. The single root vertex in the size 1 tree and the leaves ($r\sspeq 0$) are left uncolored (color $C_0$). This gives another interpretation of the unsigned Lah numbers. See ~\ref{F5} for these trees of size $n\sspeq 4$. Only three types of trees are relevant here. The tree with $r_1\sspeq 3$ is not allowed. 

While $|s(k;n,m)|$ for $k\sspeq 1$ and $k\sspeq 2$ counts trees of varieties considered by Bergeron et al.\ \cite{BFS} this remains no longer true for $k\sspgeq 3$ as is obvious from the expansion of $\Phi_k$ from ~\eqref{(3.1)}. 
In these cases the vertex multiplicities $s_{k;r}$ for outdegree $r$ are no longer non-negative integers. This applies to the o.g.f. $\phi$ as well as to the e.g.f. $\varphi$. E.g., \dstyle{\phi_3(y)\sspeq (1\sspp 2\,y)^{\frac{3}{2}}}, \dstyle{s_{3;r}\sspeq 2^r\, {\binomial{\frac{3}{2}}{r}}}, which is \dstyle{\frac{3}{2}} for $r\sspeq 2$ and $-1$ for $r\sspeq 3$. Similarly, \dstyle{\varphi_3(y)\sspeq (1\sspp 2\,y)^{\frac{3}{2}}}, \dstyle{s_{3;r}\sspeq 2^r\, r!\, {\binomial{\frac{3}{2}}{r}}} which is $-3$ for $r\sspeq 3$. This fact is summarized in the following proposition.

\begin{proposition}\label{P9}
For $k\sspgeq 3$ values $|s(k;n,1)|$ does not count increasing trees of some variety studied by Bergeron et al.\ \cite{BFS}, i.e., there exists no outdegree function $\Phi_k$ which generates non-negative integers $s_{k;r}$ for all $r\sspgeq 0$.
\end{proposition}
In order to find a tree counting interpretation also for these numbers $|s(k;n,1)|\sspfed c^{k}_n$ with $k\sspgeq 3$ one can resort to the recurrence relation 
obtained from ~\eqref{(1.4)}
\Beq\label{(3.2)}     
c_n^{(k)}\sspeq (k\sspp n\sspm 2)\,c_{n-1}^{(k)}\ ,\ c_1^{(k)}\sspeq 1\, , \ n\sspgeq 2\, .
\Eeq
For the solution of these recurrences see \cite{WL}. For $k\sspeq 3$ this is Sloane's OEIS \cite[\seqnum{A001710}]{Sloane} $\sspeq [1,3,12,60,360,\ldots]$.
One can consider trees with outdegree $r\sspeq 0$ and $r\sspeq 1$ vertices only but take $(d\sspp 3)-$ary vertices if the depth of the vertex (the distance from the root) is $d\sspgeq 0$. For size $n\sspeq 1$ there is only the root vertex with $r\sspeq 0$. For $n\sspeq 2$ the root vertex with $r\sspeq 1$ has depth $d\sspeq 0$ and is now taken $3-$ary. The second vertex has $r\sspeq 0$, depth $d\sspeq 1$, but its $4-$arity does not matter. This leads to three trees like for the $3-$ary trees considered in the last section for $k\sspeq 3$ and $n\sspeq 2$. For size $n\sspeq 3$ one has the root with $r\sspeq 1$, $d\sspeq 0$ as a $3-$ary vertex, the $d\sspeq 1$ vertex with $r\sspeq 1$ is now $4-$ary. Again the arity of the leave with $d\sspeq 2$ does not matter. Thus one finds for each of the three $n=2$ trees four new ones; altogether there are $12\sspeq c_3^{(3)}$ trees. If only trees but not forests are considered the increasing labeling from $I_n$ coincides for each vertex with $d\sspp 1$.

Instead of employing in the $k\sspeq 3$ case $(d\sspp 3)-$ary vertices, if their depth is $d$, one may again use colors for their next successor vertices. The vertex of depth $d\in \{0,1,\ldots,n-1\}$ in a size $n$ tree comes thus in $d\sspp 2$ colors $\{C_1,C_2,\ldots,C_{d+2}\}$ for $d\sspgeq 1$ and if $d\sspeq 0$ one takes color $C_0$. It is clear that such type of trees with label depending arity and outdegree only $0$ and $1$ is not covered in the study \cite{BFS}, because for all vertices with given outdegree $r$ the same number $s_r$ of vertex types (arity) is prescribed. In the trees considered here, an outdegree $1$ vertex can have depth depending vertex type numbers $s_{3;1,d}$. Therefore one would need a two variable degree-depth polynomial to treat such trees. 

The generalization to any $k\sspgeq 3$ is obvious and is the content of the next proposition where instead of different arities, colors are used. It is also possible to apply this for the cases $k\sspeq 1$ and $k\sspeq 2$.  

\begin{proposition}\label{P10} {\bf Vertex colored trees counted by $|s(k;n,1)|\, ,\, k\sspgeq 1$}  

$|s(k;n,1)|\, ,\, k\sspgeq 1$, is the number of rooted size $n$ trees
with vertices of outdegree $r\sspeq 0$ and $1$ only, increasingly
labeled from $I_n$ and colors chosen from the color repertoire
$$ \{C_1,C_2,\ldots,C_{d+k-1}\}$$
if the vertex has depth $d\in
\{0,1,\ldots,n-1\}$. The root vertex with label $1$ and depth $0$
carries color $C_0$.
\end{proposition}

For $k\sspeq 1$ the usual Stirling numbers $|s(n,1)|\sspeq (n-1)!$ arise here from the independent color choices of the depth $d$ vertices. For $k\sspeq 2$ one has $d\sspp 1$ colors to choose from for vertices of depth $d\in \{1,2,\ldots,n-1\}$ which produces $2\cdot 3 \cdots  n\sspeq n!$ possibilities. This is appropriate for the unsigned Lah numbers $|s(2;n,1)|$.

\begin{Note}\label{N6} {\bf $|s(k;n,1)|$ as an answer to an urn problem}

It is clear from Proposition~\ref{P10} that $|s(k;n,1)|,\ k\in \mathbb N$, counts the number of ways to put one colored ball into each of $n$ distinguished urns $U_1,U_2, \ldots ,U_n$ with
the color repertoire $\{C_1,C_2, \ldots ,C_{i+k-2}\}$ for urn $U_i$, $i\in\{2,3, \ldots ,n\}$, and $\{C_0\}$ for urn $U_1$.
\end{Note}

As mentioned above, in the context of the Jabotinsky structure, $|s(k;n,m)|$ counts unordered $m-$forests of size $n$ with the $m$ increasingly vertex labeled and also vertex colored trees following the rules of Proposition~\ref{P10}.

\begin{example}\label{E6} $|s(3;5,2)|\sspeq 660$ {\bf from forest counting}

The unordered $2-$forest with $n\sspeq 5$ vertices comes from the $m\sspeq 2$ part partitions $(1,4)$ and $(2,3)$ of $5$. The first one gives rise to $(1\cdot|s(3;4,1)|)\cdot 5\sspeq (1\cdot(1\cdot3\cdot4\cdot5))\cdot 5\sspeq 300$ such forests where the last factor $5$ comes from the number of increasing labelings. The second partition leads to $(|s(3;2,1|\cdot|s(3;3,1|)\cdot {\binomial{5}{2}}\sspeq ((1\cdot 3)\,(1\cdot 3\cdot 4))\,10\sspeq 360$ forests. The last factor comes again from the increasing labelings. Thus  $|s(3;5,2)|\sspeq 660$. See Sloane's OEIS \cite[$\seqnum{A046089}(2,5)\sspeq 660$]{Sloane} and the illustration in Figure ~\ref{F6}a). In Figure ~\ref{F6}b) the forests counted by $|s(4;5,3)|\speq \seqnum{A049352}(5,3)\sspeq 440$ are shown.
\end{example}

\begin{Note}\label{N7}
The definition of these rooted increasingly labeled trees with outdegree $0$ and $1$ only and the mentioned vertex coloring is somewhat artificial, as the equivalent urn problem counting shows. One can, in fact, also give such an interpretation to the $S(k;n,m)$ and $|S(-k;n,m)|$ numbers for $k\in \mathbb N$. The prefactor in the corresponding recurrences, ~\eqref{(2.7)} and ~\eqref{(2.8)}, are positive integers which will give the number of colors for the vertices of depth $d\sspeq n\sspm 1$.
\end{Note}

Finally the non-negative numbers $s(-k;n,1)$, $k\in \mathbb N$, with e.g.f. $Y_k(z)\sspeq g1(-k;z)$ given in ~\eqref{(1.8)} are considered. From \dstyle{\frac{d\,Y_k(z)}{dz\ \ \ \ \ \ }\sspeq (1\sspp x)^k}, rewritten as \dstyle{(1\sspp (1\sspp k)\,Y_k(z))^{\frac{k}{k+1}}}, one finds the would be outdegree function 
\Beq\label{(3.3)}
\Phi_k(y)\sspeq  (1\sspp (1\sspp k)\,y)^{\frac{k}{k+1}}\ ,\ k\in \mathbb N\, .
\Eeq 
The case $k\sspeq 0$ with $s(0;n,1)\sspeq \delta_{n,1}$ and $g1(0;z)\sspeq 1$ is also covered. It is clear from the binomial expansion that for $k\in \mathbb N$ neither the o.g.f. $\phi_k$ nor the e.g.f. $\varphi_k$ will generate non-negative integers $s_{k;r}$. This is the content of the next proposition.
 
\begin{proposition}\label{P11} $s(-k;n,1),\ k\sspin \mathbb N$ 

$s(-k;n,1)$ does for $k\in \mathbb N$ not count rooted increasing trees of some variety studied Bergeron et al.\ \cite{BFS}, i.e., there exists no outdegree function $\Phi_k$ which generates non-negative integers $s_{k;r}$ for all $r\sspgeq 0$.
\end{proposition}

The recurrence relation for $s(-k;n,1)\sspfed d_n^{(k)}$, $k\sspgeq 0$, is

\Beq\label{(3.4)}
d_n^{(k)}\speq (k\sspm (n-2))\,d_{n-1}^{(k)}\, ,\ d_1^{(k)}\sspeq 1\, ,\ n\sspgeq 2.
\Eeq                  

For given $k\in \mathbb N$ one has $d_n^{(k)}\sspeq 0$ for all $n\sspgeq k\sspp 2$.Therefore one only has to interpret the positive numbers $d_1^{(k)}, \ldots ,d_{k+1}^{(k)}$, with $d_j^{(k)}\sspeq k^{\underline{j-1}}$ (falling factorials). If one considers, like above, trees with only vertex outdegrees $0$ or $1$ and depth dependent vertex coloring one is lead to the following proposition.

\begin{proposition}\label{P12} $s(-k;n,1),\ k\sspin \mathbb N_0$ 

$s(-k;n,1)$ counts for $k\in \mathbb N_0$ rooted increasing trees of sizes $n \in\{1,2, \ldots ,k+1\}$ with outdegree $r\in\{0,1\}$ and vertex coloring from the repertoire $\{C_1,C_2, \ldots ,C_{k+1-d}\}$ if the depth is $d\in \{0,1, \ldots ,n-1\}$. The vertex with $d\sspeq 0$, the root labeled $1$, carries a fixed color, say $C_0$. 
\end{proposition}

\begin{example}\label{E7} $s(-5;n,1)$ {\bf colored trees with outdegree} $0$ or $1$
 
Only unary trees (no branching) of sizes $n\sspeq 1,2, \ldots ,6$ are present. For $n=1$ one has the root vertex labeled $1$ with color $C_0$. All other $5$ trees have $k=5$ colors $C_1, \ldots ,C_5$ for the vertex of depth $1$ (labeled $2$). Then the number of available colors decreases by one with each depth increase by one. In the sixth tree, having size $6$, the leave ($d \sspeq 5 $) has the color $C_1$. The counting is therefore $1, 1\cdot 5\sspeq 5,\ 1\cdot 5\cdot 4\sspeq 20,\ 1\cdot 5\cdot 4\cdot 3\sspeq 60,\ 1\cdot 5\cdot 4\cdot 3\cdot 2 \sspeq 120,\ 1\cdot 5!\sspeq 120$, in agreement with the sequence $s(-5;n,1)\sspeq \seqnum{A008279}(5,n-1)\sspeq [1,5,20,60,120,120,\bar 0] $, where $\bar 0$ stands for the periodic sequence with  $0$ entries only.
\end{example}

The numbers $s(-k;n,m),\ k\sspin \mathbb N_0$, count then unordered $m-$forests composed of trees described in Proposition~\ref{P12}.\pbn


\section{Generalized partition number arrays}\ps   
It is well know, see e.g., Charalambides \cite[p. 292, eq.(8.25)]{Chara}, that the ordinary Stirling numbers $S(n,m)$ appear as sum over the multinomial numbers $M3$ with fixed number of parts $m$ of the underlying partitions of $n$. See Sloane's OEIS \cite[\seqnum{A036040}]{Sloane}, also Abramowitz and Stegun \cite[ p. 831--2 ]{ASt} for the array  $M3$.

\Beq\label{(4.1)}
S(n,m)\speq \sum_{\vec a\in {\cal P}(n,m)}\, M3(n,\vec a)\ ,  
\Eeq

with ${\cal P}(n,m)$ the set of partitions of $n$ with $m$ parts
written in the exponent version $(1^{a_1}\,,2^{a_2}\,, \ldots
,n^{a_n})$, $a_j\in \mathbb N_0$, $j=1, \ldots ,n$, $\vec a\sspdef
(a_1,a_2, \ldots ,a_n)$, $m\sspeq \sum_{j=1}^n\,a_j$,  $n\sspeq
\sum_{j=1}^n\,j\,a_j$ and

\Beq\label{(4.2)}
M3(n,\vec a)\speq \frac{n!}{\prod_{j=1}^n\,a_j!\,j!^{a_j}}\, .  
\Eeq

It is therefore tempting to define generalized $M32(k)$, $k\in \mathbb N$, partition number arrays such that 

\Beq\label{(4.3)}
S(k;n,m)\speq \sum_{\vec a\in {\cal P}(n,m)}\, M32(k;n,\vec a)\ , \ k\in \mathbb N\,. 
\Eeq

We write $M32(k)$ to indicate the $M3$ generalization related to the $S(k;n,m)$ numbers of the second kind. The term `partition numbers' is used because every partition defines such a number, not because they count the number of some specific partitions.
Remember that $S(1;n,m)\sspeq S(n,m)$ and $S(0;n,m)\sspeq \delta_{n,m}$. This generalization is an easy task knowing the combinatorial interpretation of $S(k;n,m)$ in terms of rooted increasing $k-$ary trees from Proposition ~\ref{P3}. The partition $(1^{a_1}\,,2^{a_2}\,, \ldots ,n^{a_n})$ corresponds to the $m-$forest built from $a_1$ trees of size $1$, $a_2$ trees of size $2$, etc. These trees of size $j\in I_n$ are counted by $S(k;j,1)$. 

\begin{definition}\label{D3} {\bf $ \vec a-$forest}

For $n\in \mathbb N$ let $\vec a\sspdef (a_1,a_2, \ldots ,a_n)$ with $a_j\in \mathbb N_0$, $m\sspdef \sum_{j=1}^n\,a_j$ and  $n\sspeq \sum_{j=1}^n\,j\,a_j$. An $\vec a-$forest of size $n$ is an $m-$forest of size $n$ with specified component trees $T_1^{a_1},T_2^{a_2}, \ldots ,T_n^{a_n}$ where the exponents $a_j $ from $\mathbb N_0$ indicate that a tree $T_j$ of size $j$ is present $a_j$ times if $a_j\sspgeq 1$, and such a tree is absent if $a_j\sspeq 0$.
\end{definition}

\begin{definition}\label{D4} ${\bf M32}(k),\ k\sspin \mathbb N$, {\bf partition number arrays}

$M32(k;n,\vec a),\ k\in \mathbb N$, is the number of unordered $\vec a-$forests of size $n$ with component trees $T_j, j\in I_n$, described in Proposition $3$ and counted by $S(k;j,1)$.
\end{definition}

With this definition and from Proposition~\ref{P2} it is clear that ~\eqref{(4.3)} holds.

\begin{example}\label{E8} ${\bf M32}(2)$ {\bf partition number array}

This array can be viewed online in Sloane's OEIS \cite[\seqnum{A130561}]{Sloane}. It begins like \pn
$1;\ 2|1;\ 6|6|1;\ 24|24,12|12|1;\ 120|120,120|60|60|20|1; \ldots$ where semi-colons separate different $n$ values and $|$ separates different part numbers $m$. For example, $n\sspeq 5$, $m\sspeq 4$ has only one partition $(1^3,2^1,3^0,4^0,5^0)\sspequiv (1^3,2)$, and the counting is $10\cdot 2\sspeq 20$ for this unordered $(3,1,0,0,0)$-forest because there are ${\binomial{5}{3}}\sspeq 10$ increasing vertex labelings and the size $2$ tree comes for $k\sspeq 2$ in two versions. Thus $M32(2;5,(3,1,0,0,0))\sspeq 20.$ This appears in array \seqnum{A130561} in row $5$, column 6 because the partitions are ordered by increasing parts number $m$ and within equal parts numbers the ordering is like Abramowitz-Stegun \cite[pp. 831--2]{ASt}. Therefore we call this the A-St ordering of partitions.
\end{example}

\begin{proposition}\label{P13} ${\bf M32}(k),\ k\sspin \mathbb N$, {\bf formula}
 
\Beq\label{(4.4)}
 M32(k;n,\vec a)\sspeq M3(n,\vec a)\, \prod_{j=1}^n\,(S(k;j,1))^{a_j}\ ,\  k\in \mathbb N.
\Eeq
\end{proposition}

\begin{proof}
$M3(n;\vec a)$ of ~\eqref{(4.2)} counts the number of ways to partition a set of $n$ objects, taken as $I_n$, into blocks of type $(1^{a_1}\,,2^{a_2}\,, \ldots
,n^{a_n})$, i.e., a block of size $j$ appears $a_j$ times and is absent if $a_j\sspeq 0$. The order of the block elements is irrelevant, so w.l.o.g. they are taken increasing. The blocks are therefore disjoint and exhaustive subsets of $I_n$. Also the $a_j$ blocks of size $j$ are not ordered. E.g., $n\sspeq 5, \vec a\sspeq (1,2,0,0,0)$ and there are three (not six) set partitions for each $j\in I_5$ taken as element of the size $1$ set. Altogether there are $15$ such set partitions. Therefore $M3(n,\vec a)$ is exactly the number of unordered $\vec a-$forests of size $n$ with increasing trees, depending on the partition $\vec a\in {\cal P}(n,m)$. What is left is to multiply each increasing $\vec a-$forest with the number of possible $k-$ary trees. This number is $S(k;j,1)$ for every tree of size $j$ and it therefore comes $a_j$ times. This explains the second part on the r.h.s. of the proposition. In the given example the extra factor is $1\cdot 3^2$ for $k\sspeq 3$ from the $j=1$ tree (a root) and the two size $j=2$ ternary trees.
\end{proof}

\begin{Note}\label{N8} 
The first rows of number arrays ${\bf M32}(k)$ are shown under Sloane's OEIS \cite[\seqnum{A036040}, \seqnum{A130561},\  \seqnum{A134144},\  \seqnum{A134149},\ \seqnum{A134273},\ \seqnum{A134278}]{Sloane} for $k\sspeq 1,2, \ldots
,6$, respectively, where they are called  $M_3(k)$.
\end{Note}

\begin{definition}\label{D5} ${\bf \widehat{M32}}(k)\sspequiv '{\bf M32}(k)/{\bf M3}'$ {\bf partition number array}
\Beq\label{(4.5)}
\widehat{ M32}(k;n,\vec a)\sspdef \prod_{j=1}^n\,(S(k;j,1))^{a_j}\ ,\  k\in \mathbb N.
\Eeq       
\end{definition}

Some of these arrays are shown under Sloane's OEIS \cite[\seqnum{A134286}, \seqnum{A134133}, \seqnum{A134145},  \seqnum{A134150},  \seqnum{A134274}, \seqnum{A134279} ]{Sloane} for $k\sspeq 1,2, \ldots ,6$, respectively, where they are called symbolically $M_3(k)/M_3$. Division of arrays of the same shape here means division of corresponding entries. 

\begin{definition}\label{D6} ${\bf \widehat {S}}(k)$ {\bf triangle of numbers}

\Beq\label{(4.6)}
\widehat{S}(k;n,m)\spdef \sum_{\vec a\in {\cal P}(n,m)}\, \widehat{M32}(k;n,\vec a)\ ,\  k\in \mathbb N.
\Eeq 
\end{definition}

$\widehat{S}(k;n,m)\sspeq 0$ if $n\sspkl m$ (lower triangular matrix). One may add colum $m\sspeq 0$ and row $n\sspeq 0$ putting $\widehat{S}(k;n,0)\sspeq \delta_{n,0}$. Some of these triangles are shown under Sloane's OEIS \cite[\seqnum{A023531} (unit matrix), \seqnum{A134134}, \seqnum{A134146}, \seqnum{A134151}, \seqnum{A134275}, \seqnum{A134280}]{Sloane}, for $k\sspeq 1,2, \ldots
,6$, respectively, where they are called $S2(k)^\prime$.

It is clear that one can also define partition number arrays ${\bf M32}(-k), k\in\mathbb N$, related to the unordered $\vec a-$forests composed of rooted increasing trees $T_j, j\in \mathbb N$, defined in Proposition~\ref{P6} and counted by $|S(-k;j,1)|$. The definition is analogous to Definition~\ref{D4}. This will lead to

\Beq\label{(4.8)}
|S(-k;n,m)|\speq \sum_{\vec a\in {\cal P}(n,m)}\, M32(-k;n,\vec a)\ , \ k\in \mathbb N\, , 
\Eeq
and the formula for $M32(-k;n,\vec a)\sspeq M3(n,\vec a)\,\widehat{M32}(-k;n,\vec a)$ with

\Beq\label{(4.9)}
 \widehat{M32}(-k;n,\vec a)\sspeq \prod_{j=1}^n\,(|S(-k;j,1)|)^{a_j}\ ,\  k\in \mathbb N.
\Eeq 

 Some of these ${\bf M32}(-k)$ arrays are shown in Sloane's OEIS \cite[\seqnum{A143171},\ \seqnum{A143172},\ \seqnum{A143173}, \seqnum{A144267}, \seqnum{A144268} ]{Sloane}, for $k\sspeq 1,2, \ldots ,5$. Some of the ${\bf \widehat{M32}}(-k)$ arrays are shown there under \seqnum{A144269},\ \seqnum{A144274},\ \seqnum{A144279},\ \seqnum{A144284},\ \seqnum{A144341}, for $k\sspeq 1,2, \ldots ,5$.\pn
The corresponding triangle of numbers ${\bf \widehat {S}}(-k)$, defined analogous to Definition~\ref{D6}, are shown there under \seqnum{A144270},\ \seqnum{A144275},\ \seqnum{A144280},\ \seqnum{A144285},\ \seqnum{A144342}, for $k\sspeq 1,2, \ldots ,5$.

It is also well known, see e.g., Charalambides \cite[ p. 292, eq.(8.24) ]{Chara}, that the unsigned (also called absolute) \Stfs $|s(n,m)|$ satisfy

\Beq\label{(4.10)}
|s(n,m)|\speq \sum_{\vec a\in {\cal P}(n,m)}\, M3(n,\vec a)\, \prod_{j=1}^n\,
((j\sspm 1)!)^{a_j}\ . 
\Eeq

The $\vec a-$forest discussion in the proof of Proposition~\ref{P13} explains this because $|s(n,m)|\sspeq (j\sspm 1)!$ counts the trees of these forests. See the $k\sspeq 1$ remark following Proposition ~\ref{P10}. The straightforward generalization is then given by the following definition.

\begin{definition}\label{D7} ${\bf M31}(k)$ {\bf partition number array}

$M31(k;n,\vec a)$, $k\in \mathbb N$, is the number of unordered $\vec a-$forests of size $n$ with component trees $T_j, j\in I_n$, described in Proposition~\ref{P10} and counted by $|s(k;j,1)|$.
\end{definition}

Similarly one has

\begin{proposition}\label{P14} ${\bf M31}(k),\ k\sspin \mathbb N$, {\bf formula} 
\Beq\label{(4.11)}
 M31(k;n,\vec a)\sspeq M3(n,\vec a)\, \prod_{j=1}^n\,(|s(k;j,1)|)^{a_j}\ ,\  k\in \mathbb N,
\Eeq 
with $|s(k;n,1)|\sspeq (n\sspp k\sspm 2)!/(k\sspm 1)!,\ k\in \mathbb N$\footnote{There is a typo in Lang \cite{WL}, (45) upper alternative: it should read ${\binomial{k-2+n}{k-2}}\,(k-1)^{n-2}\ \text{for}\ k\sspeq 2,3, \ldots \ \text{and}\ n\in \mathbb N$\,.}.
\end{proposition}

Some of these arrays are shown in Sloane's OEIS \cite[\seqnum{A036039},\ \seqnum{A130561},\ \seqnum{A144353},\ \seqnum{A144354},\ \seqnum{A144355}, \seqnum{A144356}]{Sloane} for $k\sspeq 1,..,6$, respectively.

\begin{proposition}\label{P15} ${\bf M31}(-k),\ k\sspin \mathbb N$, {\bf formula}   

\Beq\label{(4.12)}
 M31(-k;n,\vec a)\sspeq M3(n,\vec a)\, \prod_{j=1}^n\,(s(-k;j,1))^{a_j}\ ,\  k\in \mathbb N,
\Eeq 
with $s(-k;n,1)\sspeq k^{\underline{n-1}},\ k\in \mathbb N$.
\end{proposition}

The first of these triangles are shown in Sloane's OEIS \cite[\seqnum{A144357},\ \seqnum{A144358},\ \seqnum{A144877},\ \seqnum{A144878}, \seqnum{A144879}]{Sloane} for $k\sspeq 1,2, \ldots ,5$.

The corresponding partition arrays which are obtained by factoring out
the $\bf M3$ array are then ${\bf \widehat{M31}}(k)$ and ${\bf
\widehat{M31}}(-k)$, for $k\in \mathbb N$. From these partition arrays
one obtains triangles by summing over like part numbers in each row.
These triangles are called ${\bf {\widehat {s}}}(k)$ for $k\in \mathbb
Z$, ${\bf {\widehat {s}}}(0)$ is the infinite unit matrix ${\bf
1}_\infty$. We list the $A-$numbers in Sloane's OEIS \cite{Sloane} for
the first of these arrays and triangles:

${\bf\widehat{ M31}}(k)$, $k=1,2, \ldots ,6$: \seqnum{A107106},\ \seqnum{A134133},\ \seqnum{A144880},\ \seqnum{A144885},\ \seqnum{A144890},\ \seqnum{A145356}.\psn
${\bf\widehat{s}}(k)$, $k=1,2, \ldots ,6$: \seqnum{A144351},\ \seqnum{A134134},\ \seqnum{A144881},\ \seqnum{A144886},\ \seqnum{A144891},\ \seqnum{A145357}.

${\bf\widehat{ M31}}(-k)$, $k=1,2, \ldots ,5$: \seqnum{A145361},\ \seqnum{A145363},\ \seqnum{A145366},\ \seqnum{A145369},\ \seqnum{A145372}.

${\bf\widehat{s}}(-k)$, $k=1,2, \ldots ,5$: \seqnum{A145362},\ \seqnum{A145364},\ \seqnum{A145367},\ \seqnum{A145370},\ \seqnum{A145373}.

\begin{Note}\label{N9} {\bf Generalizations of} ${\bf S}(k),\ k\sspin \mathbb N$

Blasiak et al.\ \cite{BPS1},\ \cite{BPS2} have generalized $S(k;n,m)$ to $S(k,l;n,m)$ with $l\in\mathbb N$ by considering also powers $d_x^l$ in eq. \ref{(1.1)} with special emphasis on the row sums, the Bell numbers $B_{k,l}(n)$\footnote{The labels in these references are $r,s$ instead of $k,l$.}. Blasiak et al.\ \cite{BPSHD} noticed via Sloane's OEIS that the Bell numbers $B_{r,1}(n)$ enumerate $r-$ary forests. M\'endez et al.\ \cite{MBP} gave a combinatorial approach to further generalized Stirling numbers of the second kind (see Schork \cite{Schork}), called $S_{\bf{r,s}}(k)$ with $\bf r$ and $\bf s$ standing for $n-$tuples of positive integers and $k$ taking certain values\footnote{$S_{\bf{r,s}}(k)\equiv S_{\bf{r,s}}(n,k)$ appears in the normal ordering of the ordered product $\lprod_{i=1}^n\, x^{r_i}\,(d_x)^{s_i}$ and $k\sspeq s_1, \ldots ,\sum_{i=1}^n\, s_i$.}. This approach, specialized to the $S(r;n,m)$ numbers for $r\in \mathbb N$, differs from the interpretation given in this paper\footnote{E.g., the Lah number $S(2;3,2)$ is according to the approach of \cite{MBP} $4+2 \sspeq 6$, using $n\sspeq 3,\ r_i\sspeq 2,\ s_i\sspeq 1,\ i\sspeq 1,2,3$, but in the interpretation as unordered $2-$forest of binary increasing trees with $4$ leaves it is  $3\cdot 2 \sspeq 6 $. }.   
\end{Note}

\section{Acknowledgements} 

The author would like to thank Simon Pl\"atzer for pointing out the program \href{http://www.graphviz.org}{Graphviz}.

\begin{figure}[H]
\vspace*{-.3cm}
\begin{center}
{\includegraphics[height=21cm,width=.7\linewidth]{graph1f.eps}
{\hfill}}
\end{center}
\caption{\label{F1}{\bf Ternary (${\bf 3}$-ary) ordered trees with ${\bf n\sspeq 1,2,3}$ and ${\bf 4}$ vertices}.\psn
There are $1,3,12,55$ such trees for $n\sspeq 1,2,3,4$, respectively. See \cite{Sloane}, \seqnum{A001764}.\pn
The trees of all figures have been produced with the help of \href{http://www.graphviz.org}{Graphviz}.
}
\end{figure}

\begin{figure}[H]
\vspace*{-1.cm}
\begin{center}
{\includegraphics[height=18cm,width=.8\linewidth]{graph1b.eps}
{\hfill}}
\end{center}
\caption{\label{F2}{\bf Rooted ordered trees with $\bf{n\sspeq 1,2,3,4}$ vertices.}\psn
There are $1,1,2,5,$ ({\sl Calalan} numbers) such trees without vertex labels. The trees are arranged according to the $1,1,2,4$ types of unordered rooted trees for $n=1,2,3,4$, respectively.\pn
The number of increasing labelings is the same for every tree in given row. It .\pn
The outdegree values $r$ appearing in a tree with the corresponding $k+r-1$-ary vertices, here with $k\sspeq 3$, are given. The box gives the multiplicity. The first factor is the number of diagrams in the row. The second factor comes from the various vertex types (due to the arity) and the last factor gives the number of increasing labelings. \pn   
The multiplicities for $n=1,2,3,4$ add up to $1,3,21,231$, respectively, corresponding to the $|S(-3,n,1)|\sspeq \seqnum{A008545}(n-1)$ numbers.
}
\end{figure}

\begin{figure}[H]
\vspace*{-.5cm}
\begin{center}
{\includegraphics[height=18cm,width=.8\linewidth]{graph1c.eps}
{\hfill}}
\end{center}
\caption{\label{F3}{\bf Rooted ordered trees with $\bf{n\sspeq 5 }$ vertices.}\psn
There are $C_4\sspeq 14$ such trees without vertex labels. The trees are arranged according to the 9 types of unordered rooted trees.\pn
The number of increasing labelings is the same for every tree in a given row.\pn
The outdegree values $r$ appearing in the tree with the corresponding $k+r-1$-ary vertices, here with $k\sspeq 3$, are given. The box gives the multiplicity. The first factor is the number of diagrams in the row. The second factor comes from the various vertex types (due to the arity)  and the last factor gives the number of increasing labelings. \pn   
The multiplicities add up to $3465\sspeq |S(-3,5,1)|\speq \seqnum{A008545}(4)$.
}
\end{figure}

\begin{figure}[H]
\vspace*{-1cm}
\begin{center}
{\includegraphics[height=19cm,width=.5\linewidth]{graph1a.eps}
{\hfill}}
\end{center}
\caption{\label{F4}{\bf Rooted ordered trees with $\bf{n\sspeq 6 }$ vertices.}\psn
There are $C_5\sspeq 42$ such trees without vertex labels. The trees are arranged according to the 20 types of unordered rooted trees.\pn
The number of increasing labelings is the same for each tree in any row. It is given in the upper box on the right of each row. These numbers add up to $945\sspeq 9!!$.\pn
The number in the lower box in each row is the multiplicity for each tree when outdegree $r\sspgeq 1$ vertices are taken $(r+2)$-ary. This applies for the case $k=3$. The total sum (upperbox $\cdot$ lower box numbers) is $65835\sspeq |S(-3;6,1)|$.
The $20$ unordered rooted trees come in altogether $426$ increasing labelings. 
}
\end{figure}

\begin{figure}[H]
\begin{center}
{\includegraphics[height=18cm,width=1\linewidth]{graph1d.eps}
{\hfill}}
\end{center}
\caption{\label{F5}{\bf Rooted unordered trees of size $\bf{ n \sspeq 4} $ with vertex types $\bf{s_0\sspeq 1}$, $\bf{s_1\sspeq 2\sspeq s_2}$.}\psn
In the first row the three types of size $n\sspeq 4$ trees which are present are shown together with their multiplicities when coloring (first factor) and increasing labeling (second factor) are considered. These trees are shown in the subsequent rows. 
}
\end{figure}

\begin{figure}[H]
\begin{center}
{\includegraphics[height=18cm,width=1\linewidth]{graph1e.eps}
{\hfill}}
\end{center}
\caption{\label{F6}{\bf Nonordered forest counting for} $|s(k;n,m)|$\psn
In Figure 6a) the $2-$forests counted by $|s(3;5,2)|\sspeq 300\sspp 360\sspeq 660$ are illustrated. The vertex colors are here called $C0,C1, \ldots ,C5$. The number of possible increasing labelings is given by the last factors $5$ and $10$.\pn
In Figure 6b) the $3-$forests counted by $|s(4;5,3)|\sspeq 200\sspp 240\sspeq 440$ are illustrated. The possible colors are indicated, giving rise to the first factor and the increasing labelings account for the second one.
\pbn
}
\end{figure}


\begin{thebibliography}{5}
\bibitem{ASt} 
M. Abramowitz and I. A. Stegun, eds., \textit{Handbook of Mathematical Functions}, National Bureau of Standards Applied Math. Series 55, Tenth Printing, reprinted as  Dover publication, New York, 1972.

\bibitem{Alexander} 
D. S. Alexander, \textit{A History of Complex Dynamics: from Schr\"oder to Fatou and Julia}, Vieweg, Braunschweig, 1994. 

\bibitem{BFS} 
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees, in  J.-C. Raoult, ed., Springer, 1992, \textit{ CAAP '92, Lecture Notes in Computer Science}, vol. \textbf{581}, pp. 24--48.

\bibitem{BiggsLloydWilson}  
N. L. Biggs, E. K. Lloyd and R. J. Wilson, \textit{Graph Theory: 1736--1936}, Clarendon Pr., 1986, Oxford.

\bibitem{BPS1}  
P. Blasiak, K. A. Penson and A. I. Solomon, The Boson normal ordering problem and generalized Bell numbers, \textit{Ann. Comb.} \textbf{7} (2003) 127--139.

\bibitem{BPS2}  
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, \textit {Phys. Lett. A}\ \textbf{309}\ (2003), 198--205.

\bibitem{BPSHD} 
P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. H. E. Duchamp, Some useful combinatorial formulae for bosonic operators, \textit{J. Math. Phys.}\ \textbf{46}\ (2005) 052110 and  arXiv:quant-ph/0405103.  
\bibitem{Carlitz} 
L. Carlitz, On arrays of numbers, \textit{Amer. J. Math.} \textbf{54} (1932) 739--752. 

\bibitem{Chara}
Ch. A. Charalambides, \textit{Enumerative Combinatorics}, Chapman \& Hall/CRC, Boca Raton, 2002.

\bibitem{Comtet} 
L. Comtet,  Une formule explicite pour les puissances successives de l'opirateur de d\'erivation de Lie, \textit{Comptes Rendus Acad. Sc. Paris}, \textbf{276 A} (1973) 165--168. 

\bibitem{CG}  J. H. Conway and R. K. Guy, \textit{The Book of Numbers}, Copernicus, (Springer) New York, 1996. 

\bibitem{GKP} 
R.L. Graham, D.E. Knuth, and O. Patashnik:  \textit{Concrete Mathematics}, Addison-Wesley, Reading MA, 1989.

\bibitem{Grunert} 
J. A. Grunert, Ueber die Summirung der Reihen von der Form $A\,\varphi(0), A_1\,\varphi(1)\,x, A_2\,\varphi(2)\,x^2,  \ldots A_n\,\varphi(n)\,x^n, \ldots ,$ wo $A$ eine beliebige constante Gr\"o\ss e, $A_n$ eine beliebige und $\varphi(n)$ eine ganze rationale algebraische Function der positiven ganzen Zahl $n$ bezeichnet, \textit{J. Reine Angew. Math.} {\bf 25} (1843), 240--279.

\bibitem{Knuth} 
Knuth, D. E., Convolution polynomials, \textit{Mathematica J.}, \textbf{2} (1992), 67--78.

\bibitem{WL} 
W. Lang, On generalizations of the Stirling number triangles, \textit{J. Integer Sequences}, \textbf{3} (2000) Article 00.2.4 

\bibitem{MBP} 
M. A. M\'endez, P. Blasiak and K. A. Penson, Combinatorial approach to generalized Bell and Stirling numbers and boson normal ordering problem, arXiv:quant-ph/0505180, 24 May 2005.

\bibitem{Schork} 

M. Schork, On the combinatorics of normal ordering boson operators and deformations of it, \textit{J. Phys. A: Math. Gen.}, \textbf{36} (2003) 4651--4665.

\bibitem{Sloane}  
N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences/index.html}{The On-Line Encyclopedia of Integer Sequences}, 2008. 


\bibitem{Stanley1} 
R. P. Stanley, \textit{Enumerative Combinatorics}, Vol. I, Cambridge University Press, 1997.

\bibitem{Stanley2} 
R. P. Stanley, \textit{Enumerative Combinatorics}, Vol. II, Cambridge University Press, 1999.

\end{thebibliography}

\pbn\pbn
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15, Secondary 05A17, 05C05.
\pn
\emph{Keywords:} 
Increasing trees, enumeration, partition number arrays.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000108}, 
\seqnum{A000142}, 
\seqnum{A000169}, 
\seqnum{A000369}, 
\seqnum{A001710}, 
\seqnum{A001764}, 
\seqnum{A002293}, 
\seqnum{A002294}, 
\seqnum{A002295}, 
\seqnum{A002296}, 
\seqnum{A007556}, 
\seqnum{A008287}, 
\seqnum{A008297}, 
\seqnum{A008545}, 
\seqnum{A023531}, 
\seqnum{A035342}, 
\seqnum{A036039}, 
\seqnum{A036040}, 
\seqnum{A046089}, 
\seqnum{A049352}, 
\seqnum{A062994}, 
\seqnum{A107106}, 
\seqnum{A130561}, 
\seqnum{A134133}, 
\seqnum{A134134}, 
\seqnum{A134144}, 
\seqnum{A134145}, 
\seqnum{A134146}, 
\seqnum{A134149}, 
\seqnum{A134150}, 
\seqnum{A134151}, 
\seqnum{A134273}, 
\seqnum{A134274}, 
\seqnum{A134275}, 
\seqnum{A134278}, 
\seqnum{A134279}, 
\seqnum{A134280}, 
\seqnum{A134286}, 
\seqnum{A143171}, 
\seqnum{A143172}, 
\seqnum{A143173}, 
\seqnum{A144267}, 
\seqnum{A144268}, 
\seqnum{A144269}, 
\seqnum{A144270}, 
\seqnum{A144274}, 
\seqnum{A144275}, 
\seqnum{A144279}, 
\seqnum{A144280}, 
\seqnum{A144284}, 
\seqnum{A144285}, 
\seqnum{A144341}, 
\seqnum{A144342}, 
\seqnum{A144351}, 
\seqnum{A144353}, 
\seqnum{A144354}, 
\seqnum{A144355}, 
\seqnum{A144356}, 
\seqnum{A144357}, 
\seqnum{A144358}, 
\seqnum{A144877}, 
\seqnum{A144878}, 
\seqnum{A144879}, 
\seqnum{A144880}, 
\seqnum{A144881}, 
\seqnum{A144885}, 
\seqnum{A144886}, 
\seqnum{A144890}, 
\seqnum{A144891}, 
\seqnum{A145356}, 
\seqnum{A145357}, 
\seqnum{A145361}, 
\seqnum{A145362}, 
\seqnum{A145363}, 
\seqnum{A145364}, 
\seqnum{A145366}, 
\seqnum{A145367}, 
\seqnum{A145369}, 
\seqnum{A145370}, 
\seqnum{A145372} and 
\seqnum{A145373}.
)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 16 2008;
revised version received March 6 2009. 
Published in {\it Journal of Integer Sequences}, March 14 2009.

\bigskip
\hrule
\bigskip

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


\end{document}