\documentclass[12pt]{article} \usepackage{epsfig, amssymb, latexsym} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{definition}{Definition}[section] \newtheorem{example}{Example}[section] \renewcommand{\theequation}{\thesection.\arabic{equation}} \newenvironment{proof}{{\bf Proof}:\ }{\hfill $\Box$ }%\vrule height7pt % width5pt\par\vspace{0.2cm}} \newcommand{\de}{\mbox{\rm d}} \def\stdue#1#2{\left\{{#1\atop#2}\right\}} \def\stuno#1#2{\left[{#1\atop#2}\right]} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \vspace*{-60pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005), \#A05} \vskip 50pt \bibliographystyle{plain} \begin{center} {\bf THE AKIYAMA - TANIGAWA TRANSFORMATION} \vskip 20pt {\bf Donatella Merlini}\\ {\smallit Dipartimento di Sistemi e Informatica \\ viale Morgagni 65, 50134, Firenze, Italia}\\ {\tt merlini@dsi.unifi.it}\\ \vskip 10pt {\bf Renzo Sprugnoli}\\ {\smallit Dipartimento di Sistemi e Informatica \\ viale Morgagni 65, 50134, Firenze, Italia}\\ {\tt sprugnoli@dsi.unifi.it}\\ \vskip 10pt {\bf M. Cecilia Verri}\\ {\smallit Dipartimento di Sistemi e Informatica \\ viale Morgagni 65, 50134, Firenze, Italia}\\ {\tt verri@dsi.unifi.it}\\ \vskip 10pt \end{center} \vskip 30pt \centerline{\smallit Received: 7/27/04, Revised: 2/25/05, Accepted: 3/12/05, Published: 3/14/05} \vskip 30pt \centerline{\bf Abstract} We consider the transformation proposed by Akiyama and Tanigawa to obtain the Bernoulli numbers and extend it to other important sequences. We also show its connection to two particular Riordan Arrays, which allow us to prove a number of combinatorial sums related to the transformation. \noindent \footnotesize \vspace{0.3cm} \noindent {\it Keywords:} Bernoulli numbers, combinatorial sum inversion, Riordan arrays, Stirling numbers. \normalsize \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005), \#A05\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt %%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 1. Introduction} \addtocounter{section}{+1} %%%%%%%%%%%%%%%%%%%%%% During his recent visit to our Department in Florence, Zhi-Wei Sun gave a seminar related to \cite{Sun02} and cited some papers of M. Kaneko, among which was \cite{Kan00} ``The Akiyama - Tanigawa algorithm for Bernoulli numbers''. The algorithm consists in writing in a row the sequence $1, 1/2, 1/3, \ldots$ and then forming successive rows by applying a well-defined rule. If we denote the starting row by $a_{0,0} = 1, a_{0,1} = 1/2, a_{0,2} = 1/3, \cdots$ and, in general $a_{0,n-1} = 1/n$, then the rule defining $a_{n+1,k}$ is: \begin{equation}\label{definingrule} a_{n+1,k} = (k+1) (a_{n,k} - a_{n,k+1}). \end{equation} The infinite matrix thus obtained is: $$\begin{array}{c|cccccc} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 1 & 1/2 & 1/3 & 1/4 & 1/5 & 1/6 \\ 1 & 1/2 & 1/3 & 1/4 & 1/5 & 1/6 & 1/7 \\ 2 & 1/6 & 1/6 & 3/20 & 2/15 & 5/42 & 3/28 \\ 3 & 0 & 1/30 & 1/20 & 2/35 & 5/84 & 5/84 \\ 4 & -1/30 & -1/30 & -3/140 & -1/105 & 0 & \cdots \\ 5 & 0 & -1/42 & -1/28 & -4/105 & \cdots & \cdots \\ \end{array}$$ and we can easily recognize in column 0 the sequence of the Bernoulli numbers, with the term $B_1$ having positive sign. As it is well-known, the exponential generating function (e.g.f.\ for short) of the Bernoulli numbers is: $B(t)= t/(e^t - 1)$, and therefore the e.g.f.\ for column 0 should be: $$B^*(t) = \frac{t}{e^t-1} + t = \frac{te^t}{e^t-1}.$$ In his paper, M. Kaneko proves that the Akiyama - Tanigawa method actually produces the Bernoulli numbers, and extends this result to poly-Bernoulli numbers. However, in our opinion, the important point in the paper is a remark that the author ascribes to an anonymous referee: if $a(t)$ is the ordinary generating function (o.g.f.\ for short) of the starting sequence, i.e., $a(t) = a_{0,0} + a_{0,1}t + a_{0,2} t^2 + \cdots$, then the sequence in column 0 has the exponential generating function $b(t)$ given by: $b(t) = e^t a(1-e^t)$. This observation creates a link between the Akiyama - Tanigawa algorithm and Riordan Arrays, a link which is worthy of being studied and allows us to extend the method to other interesting sequences. The paper is organized in the following way. In Section 2 we give a proof of the referee's remark, make explicit the connection with Riordan Arrays and give other examples of the Akiyama - Tanigawa algorithm. In Section 3 we show which other sequences can be generated by reversing the algorithm, starting with column 0 and arriving to row 0. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 2. The Akiyama - Tanigawa transformation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \setcounter{equation}{0} \addtocounter{section}{+1} Let $a(t) = a_0(t)$ be the o.g.f.\ of the starting sequence, i.e., of the row 0 in the Akiyama - Tanigawa matrix. It is possible to find an expression for the o.g.f.\ $a_n(t)$ of any row in this matrix and then to establish a formula for the elements in column 0, by simply computing $a_n(t)$ at $t = 0$, denoted\footnote{We try to be consistent with our notations: $a_n(t)$ is the g.f. of row $n$; $a_n=a_{0,n}$ is the $n$-th element in row 0, the o.g.f.\ of which is denoted by $a(t) = a_0(t)$.} by $a_n(0)$. Let us begin with the defining expression (\ref{definingrule}), and apply to it the {\em generating function operator} $\cal{G}$, i.e., the operator that transforms a sequence $\{a_n\}_{n\in N}$ into the corresponding o.g.f.: $${\cal G}\{a_{n+1,k}\} = {\cal G}\{ka_{n,k}\} + {\cal G}\{a_{n,k}\} - {\cal G}\{(k+1)a_{n,k+1}\}.$$ If we denote by $D$ the differentiation operator with respect to the indeterminate $t$, i.e., $D = \de/\de t$, the usual rules of the ${\cal G}$ operator show that we have: $$a_{n+1}(t) = tDa_n(t) + a_n(t) - Da_n(t) = a_n(t) - (1-t)Da_n(t).$$ Therefore, we pass from a row in the Akiyama - Tanigawa matrix to the next by applying the operator\footnote{Usually, the symbol $\Delta$ denotes the {\em difference operator}, but this operator will not be used here.} $\Delta = 1 - (1-t)D$, or, in other words, the o.g.f.\ $a_n(t)$ of row $n$ is given by $a_n(t) = \Delta^n a_0(t)$. The next step is to determine an explicit form for $\Delta^n$. \begin{theorem} The operator $\Delta^n$ has the form: $$\Delta^n = \sum_{k=0}^n (-1)^k \stdue{n+1}{k+1} (1-t)^k D^k,$$ where $\stdue{n}{k}$ denotes a Stirling number of second kind (see, e.g., \cite{GKP89}). \end{theorem} \begin{proof} For $n=0$ this expression becomes $\Delta^0 = 1$, where 1 denotes the identity operator. For $n=1$ we have: $$\Delta = 1 - (1-t)D = \stdue{2}{1} - \stdue{2}{2} (1-t)D$$ this being the defining relation. Therefore, let us proceed by mathematical induction by computing: $$\Delta^{n+1} = \Delta \Delta^n = \sum_{k=0}^n (-1)^k \stdue{n+1}{k+1} \Delta (1-t)^k D^k.$$ Now we have: $$\begin{array}{ccl} \Delta(1-t)^k D^k & = & (1-t)^k D^k + k(1-t)^k D^k - (1-t)^{k+1} D^{k+1} = \\ & = & (k+1)(1-t)^k D^k - (1-t)^{k+1} D^{k+1}, \end{array}$$ hence: $$\Delta^{n+1} = \sum_{k=0}^n (-1)^k (k+1) \stdue{n+1}{k+1} (1-t)^k D^k -\sum_{k=0}^n (-1)^k \stdue{n+1}{k+1} (1-t)^{k+1} D^{k+1}=$$ $$= \sum_{k=0}^{n+1} (-1)^k (k+1) \stdue{n+1}{k+1} (1-t)^k D^k + \sum_{k=1}^{n+1} (-1)^{k} \stdue{n+1}{k} (1-t)^{k} D^{k}=$$ $$= \sum_{k=0}^{n+1} (-1)^k \stdue{n+2}{k+1} (1-t)^k D^k,$$ where we used the recurrence relation for the Stirling numbers of the second kind: $$(k+1) \stdue{n+1}{k+1} + \stdue{n+1}{k} = \stdue{n+2}{k+1}.$$ This proves the formula given by the theorem. %If we consider the coefficient of the term containing $(1 - t)^k %D^k$, it is the sum of two quantities: the first coming from %$\Delta (1 - t)^k D^k$ with coefficient $k+1$, and the second %coming from $\Delta (1 - t)^{k-1} D^{k-1}$ with coefficient $-1$. %Since, however, the coefficient of $(1 - t)^{k-1} D^{k-1}$ has %opposite sign to that of $(1 - t)^k D^k$, the new coefficient is %given by: % $$(k+1) \stdue{n+1}{k+1} + \stdue{n+1}{k} = \stdue{n+2}{k+1},$$ %where we used the recurrence relation of the Stirling numbers of %the second kind. This proves the formula given by the theorem. \end{proof} At this point, we have the announced formula for the elements in column 0 of the Akiyama - Tanigawa matrix: \begin{theorem} If $a(t)$ is the o.g.f.\ of row 0 in any Akiyama - Tanigawa matrix and $b_n = a_n(0)$ is the $n$-th element of column 0, then we have: \begin{equation}\label{genformula} b_n = \sum_{k=0}^n (-1)^k \stdue{n+1}{k+1} k! a_k. \end{equation} \end{theorem} \begin{proof} The previous theorem gives us the formula for $a_n(t)$, the o.g.f.\ of row $n$; the constant term is obtained by setting $t = 0$ and so we have: $$b_n = \sum_{k=0}^n (-1)^k \stdue{n+1}{k+1} D^k a(0),$$ and since $D^k a(0) = k!a_k$ is the well-known rule of the differentiation operator, the formula is proved. \end{proof} Instead of limiting ourselves to any specific case, let us continue with general considerations. The concept of a Riordan Array was introduced by Shapiro et al. \cite{SGWW91} and then used in various ways \cite{Mer95,MRSV97,MS02,MSV94c,Spr94}, especially to perform combinatorial sums. In general, a Riordan Array is a couple of formal power series $R = (d(t), h(t))$, which defines an infinite, lower triangular array $\{d_{n,k}\}_{n,k \in N}$ by the rule: \begin{equation}\label{riordana} d_{n,k} = [t^n] d(t) (th(t))^k, \end{equation} where $[t^n]$ denotes ``the coefficient of operator", that is $[t^n]f(t)=[t^n]\sum_{k \geq 0} f_kt^k=f_n.$ We write $(d(t), h(t)) = {\cal R}(d_{n,k})$. Here, we only consider the case in which $d(0) = h(0) = 1$, but other cases can also be of interest. Riordan Arrays generalize well-known cases of infinite, lower triangular matrices, as the Pascal, Catalan, Motzkin and Schr\"oder triangles, but their main property (at least from our present point of view) is their capability in performing combinatorial sums through the use of generating functions. In fact, if $R = (d(t), h(t))$ is any Riordan Array and $f(t)$ is the o.g.f.\ of any sequence $f_0, f_1, f_2, \cdots$, then we have: \begin{equation}\label{sommeRA} \sum_{k=0}^n d_{n,k} f_k = [t^n] d(t) f(th(t)). \end{equation} For example, since $P = (1/(1-t), 1/(1-t))$ is the Riordan Array corresponding to the Pascal triangle, every sum involving the simple binomial coefficients can be executed by the so-called {\em Euler transformation}: $$\sum_{k=0}^n {n \choose k} f_k = [t^n] \frac{1}{1-t} f\left( \frac{t}{1-t} \right).$$ In \cite{Spr94} we have shown many applications of this method, which allows us also to perform sums involving Stirling numbers of first and second kind, since they correspond to the two Riordan Arrays: $${\cal R} \left( \frac{k!}{n!} \stuno{n}{k} \right) = \left( 1, \frac{1}{t} \ln \frac{1}{1-t} \right) \qquad {\rm and} \qquad {\cal R} \left( \frac{k!}{n!} \stdue{n}{k} \right) = \left( 1, \frac{e^t - 1}{t} \right),$$ where $\stuno{n}{k}$ denotes a Stirling number of first kind (see, e.g., \cite{GKP89}). In the present case, we are mostly interested in the related Riordan Array: $$\left( e^t, \frac{e^t-1}{t} \right) = {\cal R} \left( \frac{k!}{n!} \stdue{n+1}{k+1} \right).$$ This correspondence is easily proved by means of the defining relation (\ref{riordana}): $$d_{n,k} = [t^n] e^t (e^t-1)^k = [t^n] (e^t-1)^{k+1} + [t^n] (e^t-1)^k =$$ $$= \frac{(k+1)!}{n!} \stdue{n}{k+1} + \frac{k!}{n!} \stdue{n}{k} = \frac{k!}{n!} \left( (k+1) \stdue{n}{k+1} + \stdue{n}{k} \right) = \frac{k!}{n!} \stdue{n+1}{k+1},$$ where, again, we have used the basic recurrence for the Stirling numbers of the second kind. At this point, we have a proof of the referee's observation: \begin{theorem} If $a(t)$ is the o.g.f.\ of row 0 and $b(t)$ is the e.g.f.\ of column 0 in any Akiyama - Tanigawa matrix, then we have: \begin{equation}\label{trasformazione} b(t) = e^t a(1 - e^t). \end{equation} \end{theorem} \begin{proof} Formula (\ref{genformula}) can be written as follows: $$b_n = n! \sum_{k=0}^n \frac{k!}{n!} \stdue{n+1}{k+1} (-1)^k a_k;$$ the o.g.f.\ of $(-1)^k a_k$ is $a(-t)$ and by (\ref{sommeRA}), together with the previous considerations about the Riordan Array $(e^t, (e^t-1)/t)$, we have: $$b_n = n![t^n] e^t a(1-e^t),$$ as desired. \end{proof} As noted by the referee of the Kaneko paper, the case studied by Akiyama e Tanigawa is $a(t) = -\ln(1-t)/t$ and consequently we have: $$b_n = n! [t^n] \frac{e^t}{1-e^t} \ln \frac{1}{1-1+e^t} = n! [t^n] \frac{te^t}{e^t-1} =$$ $$= n! [t^n] \left( \frac{t}{e^t-1} + t \right) = B_n + \delta_{n,1},$$ where $\delta_{n,k}$ is the Kronecker symbol. This is just the Riordan Array approach to prove combinatorial sums; in this case we have proved: \begin{equation}\label{casoKan} \sum_{k=0}^n \stdue{n+1}{k+1} \frac{(-1)^k k!}{k+1} = B_n + \delta_{n,1}. \end{equation} As a direct consequence of the previous theorem, we obtain a number of well-known sequences; here is a short list of possible applications, most of which we leave to the interested reader for verification. A simple Maple program can be written to generate the upper left corner of the infinite Akiyama - Tanigawa matrix. \begin{example} \emph{If we start with the sequence: $0, 1, 1/2, 1/3, \cdots$, the generating function of which is $a(t) = -\ln(1-t)$, we get: $$b_n = n![t^n] \frac{e^t}{1-1+e^t} = n! [t^n] (-t) e^t = -n! [t^{n-1}]e^t = -n.$$ This is the proof of the following combinatorial sum: $$\sum_{k=1}^n \stdue{n+1}{k+1} (-1)^k (k-1)! = -n.$$ The Akiyama - Tanigawa matrix is rather curious: $$\begin{array}{c|ccccc} & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 0 & 1 & 1/2 & 1/3 & 1/4 \\ 1 & -1 & 1 & 1/2 & 1/3 & 1/4 \\ 2 & -2 & 1 & 1/2 & 1/3 & 1/4 \\ 3 & -3 & 1 & 1/2 & 1/3 & 1/4 \\ 4 & -4 & 1 & 1/2 & 1/3 & 1/4 \\ \end{array}$$} \end{example} \begin{example} \emph{Starting with the sequence $1, -1, 1, -1, \cdots$, having o.g.f.\ $a(t) = 1/(1+t)$, we get: $$b_n = n! [t^n] \frac{e^t}{2-e^t} = n! [t^n] \frac{2}{2-e^t} - 1 = n! [t^n] 2{\cal O}(t) -1 = 2{\cal O}_n - \delta_{0,n},$$ where ${\cal O}(t)$ is the e.g.f.\ of the ordered Bell numbers: $${\cal O}(t) = \frac{1}{2-e^t} = 1 + t + \frac{3}{2!}t^2 + \frac{13}{3!} t^3 + \frac{75}{4!}t^4 + \frac{541}{5!}t^5 + \cdots.$$ The corresponding combinatorial sum is: $$\sum_{k=0}^n \stdue{n+1}{k+1} k! = 2{\cal O}_n - \delta_{0,n}.$$} \end{example} \begin{example} \emph{Starting with the sequence $1, 1, 1, 1, \ldots$, the generating function of which is $a(t) = (1-t)^{-1}$, we obtain: $$b_n = n![t^n] \frac{e^t}{1-1+e^t} = n! [t^n] 1 = \delta_{n,0};$$ The Akiyama - Tanigawa matrix is rather peculiar and the corresponding combinatorial sum is: $$\sum_{k=0}^n \stdue{n+1}{k+1} (-1)^k k! = \delta_{n,0}.$$} \end{example} \begin{example}\emph{Starting with the sequence $1, 0, 0, 0, \ldots$, the generating function of which is $a(t) = 1$, we obtain: $$b_n = n! [t^n] e^t = 1.$$ This is the rather obvious combinatorial sum: $$\sum_{k=0}^n \stdue{n+1}{k+1} \delta_{k.0} = \stdue{n+1}{1} = 1.$$} \end{example} \begin{example} \emph{Starting with the sequence $0, -1, 0, 0, \ldots$, the generating function of which is $a(t) = -t$, we obtain: $$b_n = n![t^n] e^t (e^t - 1) = n! \left( \frac{2^n}{n!} - \frac{1}{n!} \right) = 2^n - 1.$$ This also is a simple combinatorial sum: $$\sum_{k=0}^n \stdue{n+1}{k+1} (-1)^{k-1} k! \delta_{k,1} = \stdue{n+1}{2} = 2^n - 1.$$} \end{example} \begin{example} \emph{Starting with the sequence of harmonic numbers $H_k$, the generating function of which is $a(t) = -\ln(1-t)/(1-t)$, we obtain: $$b_n = n! [t^n] \frac{e^t}{1-1+e^t} \ln \frac{1}{1-1-e^t} = n! [t^n] (-t) = -\delta_{n,1}.$$ The reader is invited to write down the Akiyama - Tanigawa matrix for this example. When we did so, we were puzzled by the matrix, but after a bit we realized that it was obvious and we should have imagined it in advance. The associated combinatorial sum can be rather interesting: $$\sum_{k=0}^n \stdue{n+1}{k+1} (-1)^k k! H_k = -\delta_{n,1}.$$} \end{example} \begin{example} \emph{Starting with the sequence $1, -1, 1/2, -1/6, 1/24, \ldots$, the generating function of which is $a(t) = e^{-t}$, we obtain: $$b_n = n![t^n] e^t \exp(e^t-1) = n![t^n] \frac{\de}{\de t} \exp (e^t - 1) =$$ $$= n! (n+1) [t^{n+1}] \exp(e^t-1) = (n+1)! \frac{{\cal B}_{n+1}}{(n+1)!} = {\cal B}_{n+1},$$ where ${\cal B}_n$ is the $n$-th Bell number; in fact: $${\cal B}(t) = \exp(e^t-1) = 1 + t + \frac{2}{2!}t^2 + \frac{5}{3!} t^3 + \frac{15}{4!}t^4 + \frac{52}{5!}t^5 + \frac{203}{6!}t^6 + \cdots.$$ The upper part of the Akiyama - Tanigawa matrix is worth of being explicitly given: $$\begin{array}{c|cccccc} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 1 & -1 & 1/2 & -1/6 & 1/24 & -1/120 \\ 1 & 2 & -3 & 2 & -5/6 & 1/4 \\ 2 & 5 & -10 & 17/2 & -13/3 \\ 3 & 15 & -37 & 77/2 \\ 4 & 52 & -151 \\ 5 & 203 \\ \end{array}$$ However, from a combinatorial point of view, the combinatorial sum corresponding to this matrix is just the well-known defining expression of the Bell numbers, the total number of possible partitions of a set with $n+1$ elements: $$\sum_{k=0}^n \stdue{n+1}{k+1} = {\cal B}_{n+1}.$$} \end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 3. The inverse transformation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \setcounter{equation}{0} \addtocounter{section}{+1} It is a simple matter to define the {\em inverse} Akiyama - Tanigawa transformation; from the basic recurrence (\ref{definingrule}): $a_{n+1,k} =(k+1)a_{n,k} - (k+1)a_{n,k+1}$, we exchange $n$ and $k$ in order to transpose the matrix: $$b_{n,k+1} = (n+1) b_{n,k} - (n+1)b_{n+1,k}$$ and since we inductively suppose that row $n$ is known, we compute $b_{n+1,k}$: \begin{equation}\label{newdefining} b_{n+1,k} = b_{n,k} - \frac{1}{n+1} b_{n,k+1}. \end{equation} In this way, row 1 is obtained as the differences of the elements of row 0, and so on. The construction is easy and the reader can start with the Bernoulli numbers (where $[t^1]B^*(t) = 1/2$, instead of being $-1/2$), apply the transformation (\ref{newdefining}) and obtain in column 0 the sequence $1, 1/2, 1/3, 1/4, \ldots$. In terms of generating functions, everything is now obvious: \begin{theorem} Let $b(t)$ be the e.g.f.\ of row 0 in the inverse Akiyama - Tanigawa matrix; then the o.g.f.\ of column 0 is given by: $$a(t) = \frac{1}{1-t} b(\ln(1-t)).$$ \end{theorem} \begin{proof} If we set $y = 1-e^t$, the relation (\ref{trasformazione}) becomes: $$b(\ln(1-y)) = (1-y) a(y),$$ since $e^t = 1 - y$ and $t = \ln(1-y)$. But this is just the desired formula. \end{proof} By formula (\ref{sommeRA}), this transformation corresponds to the Riordan Array: $$\left( \frac{1}{1-y}, \ln(1-y) \right) = {\cal R} \left( (-1)^k \frac{k!}{n!} \stuno{n+1}{k+1} \right).$$ In fact, the generic element is: $$d_{n,k} = [y^n] \frac{1}{1-y} (\ln(1-y))^k = (-1)^k [y^n] \frac{1}{1-y} \left( \ln \frac{1}{1-y} \right)^k = \frac{(-1)^k}{k+1} [y^n] \frac{\de}{\de y} \left( \ln \frac{1}{1-y} \right)^k =$$ $$= \frac{(-1)^k}{k+1} (n+1) [y^{n+1}] \left( \ln \frac{1}{1-y} \right)^{k+1} = (-1)^k \frac{n+1}{k+1} \frac{(k+1)!}{(n+1)!} \stuno{n+1}{k+1} = (-1)^k \frac{k!}{n!} \stuno{n+1}{k+1}.$$ Therefore, we can invert the combinatorial sums corresponding to the Akiyama - Tanigawa transformation; again, let $a(t)$ be the o.g.f.\ of column 0 and $b(t)$ the e.g.f.\ of row 0; then by formula (\ref{sommeRA}) we have: $$a_n = \sum_{k=0}^n \frac{k!}{n!} \stuno{n+1}{k+1} (-1)^k \frac{b_k}{k!} = \frac{1}{n!} \sum_{k=0}^n \stuno{n+1}{k+1} (-1)^k b_k,$$ which is the sum inverse of (\ref{genformula}). Sum inversion is a classical problem and often, as in this case, can be performed quite easily by using Riordan Arrays. The inverse of the sum (\ref{casoKan}) corresponding to the Bernoulli original application of the Akiyama - Tanigawa transformation is: $$\sum_{k=0}^n \stuno{n+1}{k+1} (-1)^k B^*_k = \frac{n!}{n+1}$$ Obviously, the examples given in the previous section are also examples of the inverse Akiyama - Tanigawa transformation, and it is sufficient to transpose the matrices found there. Consequently, it is more constructive to use the previous theorem to solve a problem that is naturally occurred to the reader. As we have seen, by using the Akiyama - Tanigawa transformation we have not exactly obtained the Bernoulli numbers, as we have not obtained the Bell numbers or the ordered Bell numbers. We can wonder how these numbers can be obtained, that is what is the right initial sequence giving us the exact sequence of Bernoulli, Bell or ordered Bell numbers. The reader is invited to write down the combinatorial sums corresponding to the inverse transformation, involving the Stirling numbers of the first kind and representing the inverse sum (in the sense of Riordan \cite{Rio68}) of the ones given in the previous section. \begin{example} \emph{The e.g.f.\ of the Bernoulli numbers is $B(t) = t/(e^t - 1)$, and therefore we can apply to it the inverse Akiyama - Tanigawa transformation: $$B(t) = \frac{t}{e^t-1} \quad \Rightarrow \quad \frac{1}{1-y} \cdot \frac{\ln(1-y)}{1-y-1} = \frac{1}{y(1-y)} \ln \frac{1}{1-y}.$$ This is just the shifted sequence of the harmonic numbers, that is $1, 3/2, 11/6, 25/12, \ldots$. The corresponding Akiyama - Tanigawa matrix is now easily obtained and the sequence of Bernoulli numbers is generated in column 0: $$\begin{array}{c|ccccc} & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 1 & 3/2 & 11/6 & 25/12 & 137/60 \\ 1 & -1/2 & -2/3 & -3/4 & -4/5 \\ 2 & 1/6 & 1/6 & 3/20 \\ 3 & 0 & 1/30 \\ 4 & -1/30 \\ \end{array}$$ The starting sequence is not so simple as $1, 1/2, 1/3, 1/4, \ldots$ and this can justify Kaneko in proposing the modified Bernoulli numbers as a meaningful example of the method (see however that row number 1 is composed by the elements $-n/(n+1)$, another interesting example).} \end{example} \begin{example} \emph{The e.g.f.\ of the Bell numbers is ${\cal B}(t) = \exp(e^t-1)$ and the inverse transformation gives: $$b(y) = \frac{1}{1-y} \exp(e^{\ln(1-y)} -1) = \frac{e^{-y}}{1-y},$$ that is $b(t)$ represents the partial sums of the coefficients (with alternating signs) of the exponential function. The starting sequence is therefore $1, 0, 1/2, 1/3, 3/8, 11/30, \ldots$ and the Akiyama - Tanigawa matrix is: $$\begin{array}{c|cccccc} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 1 & 0 & 1/2 & 1/3 & 3/8 & 11/30 \\ 1 & 1 & -1 & 1/2 & -1/6 & 1/24 \\ 2 & 2 & -3 & 2 & -5/6 \\ 3 & 5 & -10 & 17/2 \\ 4 & 15 & -37 \\ 5 & 52 \\ \end{array}$$ Actually, in the second row we recognize the coefficients of the exponential function (i.e., the differences of the partial sums).} \end{example} \begin{example} \emph{The e.g.f.\ of the ordered Bell numbers is ${\cal O}(t) = 1/(2-e^t)$, so that we have: $$b(t) = \frac{1}{1-y} \cdot \frac{1}{2-(1-y)} = \frac{1}{1-y^2}.$$ Therefore, the starting sequence is $1, 0, 1, 0, 1, \ldots$: $$ \begin{array}{c|cccccc} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & -2 & 3 & -4 & 5 \\ 2 & 3 & -10 & 21 & -36 \\ 3 & 13 & -62 & 171 \\ 4 & 75 & -466 \\ 5 & 541 \\ \end{array}$$} \end{example} \begin{example} \emph{A more appropriate example for the inverse Akiyama - Tanigawa matrices is given by the Euler numbers, the e.g.f.\ of which is $E(t) = 2e^t/(e^{2t}+1)$. Now we have: $$b(y) = \frac{1}{1-y} \cdot \frac{2\exp(\ln(1-y))}{\exp(\ln(1-y)^2) + 1} = \frac{2}{(1-y)^2 + 1} = \frac{1}{1-y+y^2/2}, $$ $$b_n={2 \over \sqrt{2}^{n+1} } \sin \left({(n+1) \pi \over 4} \right).$$ If we start with the coefficients of this o.g.f., column 0 of the (direct) Akiyama - Tanigawa matrix contains the Euler numbers: $$\begin{array}{c|cccccc} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 1 & 1 & 1/2 & 0 & -1/4 & -1/4 \\ 1 & 0 & 1 & 3/2 & 1 & 0 \\ 2 & -1 & -1 & 3/2 & 4 \\ 3 & 0 & -5 & -15/2 \\ 4 & 5 & 5 \\ 5 & 0 \\ \end{array}$$} \end{example} \begin{example} \emph{As a last example, similar to the previous one, we consider Genocchi numbers, the e.g.f.\ of which is $G(t) = 2t/(e^t+1)$: $$\frac{2t}{e^t + 1} = \frac{1}{1!}t - \frac{1}{2!}t^2 + \frac{1}{4!}t^4 - \frac{3}{6!}t^6 + \frac{17}{8!}t^8 + \frac{155}{10!}t^{10} \cdots.$$ We find: $$b(y) = \frac{1}{1-y} \cdot \frac{2\ln(1-y)}{\exp(\ln(1-y))+1} = \frac{2\ln(1-y)}{(1-y)(2-y)}, \qquad b_n=-{1 \over 2^n} \sum_{k=0}^n H_k2^k.$$ This is not a particularly simple function, but the Akiyama - Tanigawa matrix can be easily built: $$\begin{array}{c|cccccc} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 0 & -1 & -2 & -17/6 & -7/2 & -121/30 \\ 1 & 1 & 2 & 5/2 & 8/3 & 8/3 \\ 2 & -1 & -1 & -1/2 & 0 \\ 3 & 0 & -1 & -3/2 \\ 4 & 1 & 1 \\ 5 & 0 \\ \end{array}$$} \end{example} %%%%%%%%%%%%%%%%%%%% %\bibliography{d:/Articoli/Biblio/bibliogr} %%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{10} \footnotesize \bibitem{GKP89} R.~L. Graham, D.~E. Knuth, and O.~Patashnik. \newblock {\em Concrete {M}athematics}. \newblock Addison-Wesley, 1989. \bibitem{Kan00} M.~Kaneko. \newblock The {A}kiyama-{T}anigawa algorithm for {B}ernoulli numbers. \newblock {\em Journal of Integer Sequences}, 3, 2000. \bibitem{Mer95} D.~Merlini. \newblock I {R}iordan {A}rray nell'{An}alisi degli {A}lgoritmi. \newblock Tesi di Dottorato, Universit{\`a} degli Studi di Firenze, 1996. \bibitem{MRSV97} D.~Merlini, D.~G. Rogers, R.~Sprugnoli, and M.~C. Verri. \newblock On some alternative characterizations of {R}iordan arrays. \newblock {\em Canadian Journal of Mathematics}, 49(2):301--320, 1997. \bibitem{MS02} D.~Merlini and R.~Sprugnoli. \newblock A {R}iordan {A}rray proof of a curious identity. \newblock {\em Integers: The Electronic Journal of Combinatorial Number Theory}, 2:A8, 2002. \bibitem{MSV94c} D.~Merlini, R.~Sprugnoli, and M.~C. Verri. \newblock A uniform model for the storage utilization of {B}-trees-like structures. \newblock {\em Information Processing Letters}, 57:53--58, 1996. \bibitem{Rio68} J.~Riordan. \newblock {\em Combinatorial identities}. \newblock Wiley, New York, 1968. \bibitem{SGWW91} L.~W. Shapiro, S.~Getu, W.-J. Woan, and L.~Woodson. \newblock The {R}iordan group. \newblock {\em Discrete Applied Mathematics}, 34:229--239, 1991. \bibitem{Spr94} R.~Sprugnoli. \newblock Riordan arrays and combinatorial sums. \newblock {\em Discrete Mathematics}, 132:267--290, 1994. \bibitem{Sun02} Z.-W. Sun. \newblock A curious identity involving binomial coefficients. \newblock {\em Integers: The Electronic Journal of Combinatorial Number Theory}, 2:A4, 2002. \end{thebibliography} \end{document}