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

\usepackage{indentfirst}
\usepackage{mathtools}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

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

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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\renewcommand*{\thefootnote}{\fnsymbol{footnote}}

\begin{center}
\vskip 1cm{\LARGE\bf 
Shifting Property for Riordan, Sheffer and \\
\vskip .1in 
Connection Constants Matrices
}
\vskip 1cm
\large
Emanuele Munarini\footnote{The work is partially supported by MIUR (Ministero dell'Istruzione, dell'Universit\`a e della Ricerca).}\\
Politecnico di Milano\\
Dipartimento di Matematica\\
Piazza Leonardo da Vinci 32 \\
20133 Milano \\
Italy\\
\href{mailto:emanuele.munarini@polimi.it}{\tt emanuele.munarini@polimi.it}
\end{center}

\vskip .2 in

\renewcommand*{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}

\newcommand{\ii}{\mathrm{i}}
\newcommand{\ee}{\textrm{e}}
\newcommand{\dd}{\textrm{d}}

\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\R}{\mathcal{R}}

\newcommand{\zero}{\mathbf{0}}

\newcommand{\mchoose}[2]{ { \left(\!\!\!\left( { #1 \atop #2 } \right)\!\!\!\right) } }
\newcommand{\Mchoose}[2]{ { \left(\!\!\left( { #1 \atop #2 } \right)\!\!\right) } }

\newcommand{\map}[3]{{#1}:{#2}\rightarrow{#3}}

\newenvironment{examples}{ \bigskip \noindent {\bf Examples} \begin{enumerate} }{ \end{enumerate} }

\def\lah{\atopwithdelims||}


\vskip .2 in

\begin{abstract}
 We study the \emph{shifting property} of
 a matrix $ R = [r_{n,k}]_{n,k\geq0} $ and a sequence $ (h_n)_{n\in\NN} $,
 i.e., the identity
 $$ \sum_{k=0}^n r_{n,k} h_{k+1} = \sum_{k=0}^n r_{n+1,k+1} h_k \, , $$
 when $ R $ is a \emph{Riordan matrix}, a \emph{Sheffer matrix} (exponential Riordan matrix),
 or a \emph{connection constants matrix} (involving symmetric functions and continuants).
 Moreover, we consider the shifting identity for several sequences of combinatorial interest,
 such as the binomial coefficients, the polynomial coefficients,
 the Stirling numbers (and their $q$-analogues), the Lah numbers, the De Morgan numbers,
 the generalized Fibonacci numbers, the Bell numbers, the involutions numbers,
 the Chebyshev polynomials, the Stirling polynomials, the Hermite polynomials,
 the Gaussian coefficients, and the $q$-Fibonacci numbers.
\end{abstract}

\section{Introduction}

We say that a matrix $ R = [r_{n,k}]_{n,k\geq0} $ and a sequence $ (h_n)_{n\in\NN} $
satisfy the \emph{shifting property} when they satisfy the \emph{shifting identity}
\begin{equation}\label{shifting}
 \sum_{k=0}^n r_{n,k} h_{k+1} = \sum_{k=0}^n r_{n+1,k+1} h_k
\end{equation}
for every $ n \in \NN $.
This relation turns out to be satisfied by several combinatorial sequences, as already noted in the Abstract.
In this paper, we will consider the following classes of matrices.
\begin{itemize}
 \item \emph{Riordan matrices} \cite{ShapiroGetuWoanWoodson}
  (see also \cite{ShapiroSurvey,Shapiro,Sprugnoli,WangWang}):
  $ R = [ r_{n,k} ]_{n,k\geq 0} = (g(t),f(t)) $ is an infinite lower triangular matrix
  whose columns have generating series $$ r_k(t) = \sum_{n\geq k} r_{n,k}\; t^n = g(t)f(t)^k \, , $$
  where $ g(t) $ and $ f(t) $ are ordinary formal series
  with $ g_0 = 1 $, $ f_0 = 0 $ and $ f_1 \ne 0 $.
 \item \emph{Sheffer matrices} \cite{Roman,RomanRota,WangWang} (or \emph{exponential Riordan matrices}):
  $ R = [ r_{n,k} ]_{n,k\geq 0} = (g(t),f(t)) $ is an infinite lower triangular matrix
  whose columns have exponential generating series
  $$ r_k(t) = \sum_{n\geq k} r_{n,k}\; \frac{t^n}{n!} = g(t)\frac{f(t)^k}{k!} \, , $$
  where $ g(t) $ and $ f(t) $ are exponential formal series
  with $ g_0 = 1 $, $ f_0 = 0 $ and $ f_1 \ne 0 $.
 \item \emph{Connection constants matrices} \cite{DAntonaMunarini,DamianiDAntonaNaldi}:
  $ R = C^{(\rho,\sigma)} = \left[ C_{n,k}^{(\rho,\sigma)} \right]_{n,k\geq 0} $
  is an infinite lower triangular matrix whose entries are the \emph{connection constants}
  between the two persistent sequences of polynomials
  $ ( p_n^{(\rho)}(x) )_{n\geq0} $ and $ ( p_n^{(\sigma)}(x) )_{n\geq0} $,
  i.e., are the coefficients for which
  \begin{equation}\label{ConnectionRel}
   p_n^{(\rho)}(x) = \sum_{k=0}^n C_{n,k}^{(\rho,\sigma)} p_k^{(\sigma)}(x) \, ,
  \end{equation}
  where $ \rho = (r_1,r_2,\ldots) $ and $ \sigma = (s_1,s_2,\ldots) $,
  and $ p_n^{(\rho)}(x) = (x-r_1)(x-r_2)\cdots(x-r_n) $.
\end{itemize}

Notice that, in the case of Riordan and Sheffer matrices,
$ g(t) $ is invertible with respect to the product of series
and $ f(t) $ is invertible with respect to the composition of series.
The compositional inverse of the series $ f(t) $ is denoted by $ \widehat{f}(t) $.
Moreover, Riordan and Sheffer matrices form a group with respect to the matrix product.
In particular, we have
$$
 (g(t),f(t))\,(G(t),F(t)) = (g(t)G(f(t)),F(f(t)))
 \qquad\text{and}\qquad
 (g(t),f(t))^{-1} = \left(\frac{1}{g(\widehat{f}(t))},\widehat{f}(t)\right).
$$

For the connection constants matrices, we have the closure property
$$ C^{(\rho,\sigma)} C^{(\sigma,\tau)} = C^{(\rho,\tau)} \, . $$
Moreover, all connection constants matrices are invertible, and the inverse matrices are given by
\begin{equation}\label{id-inverse-CC-matrix}
 (C^{(\rho,\sigma)})^{-1} = C^{(\sigma,\rho)} \, .
\end{equation}

\section{General properties}

Given a matrix $ R $, we can have infinite sequences $ (h_n)_{n\in\NN} $
for which the shifting property is satisfied.
However, for a \emph{normalized sequence} $ (h_n)_{n\in\NN} $, i.e., a sequence with $ h_0 = 1 $,
we have the following
\begin{lemma}\label{lemma-1}
 For every invertible infinite lower triangular matrix $ R = [r_{n,k}]_{n,k\geq0} $,
 there exists a unique normalized sequence $ (h_n)_{n\in\NN} $ for which the shifting property holds.
\end{lemma}
\begin{proof}
 Since $ R $ is invertible, all its diagonal entries are non-zero.
 So, by identity (\ref{shifting}), we obtain the recurrence
 $$ h_{n+1} = \frac{1}{r_{n,n}}\left( \sum_{k=0}^n r_{n+1,k+1} h_k - \sum_{k=0}^{n-1} r_{n,k} h_{k+1} \right). $$
 This recurrence, with the initial value $ h_0 = 1 $, defines an unique sequence.
\end{proof}

In particular, for $ n = 0 $ in identity (\ref{shifting}),
we have $ r_{0,0} h_1 = r_{1,1} h_0 $,
So, if the sequence is normalized and $ r_{0,0} = r_{1,1} $, then $ h_1 = h_0 = 1 $.

\begin{lemma}\label{lemma-main}
 Let $ R = [r_{n,k}]_{n,k\geq0} $ be an invertible infinite lower triangular matrix
 and let $ (h_n)_{n\in\NN} $ be a normalized sequence satisfying the shifting property.
 If there exist a matrix $ S = [s_{n,k}]_{n,k\geq0} $ such that
 \begin{equation}\label{rec-R-S}
  r_{n+1,k+1} = \sum_{i=k}^n r_{n,i} s_{i,k}
 \end{equation}
 for every $ n, k \in \NN $,
 then the elements of the sequence $ (h_n)_{n\in\NN} $ satisfy the recurrence
 \begin{equation}\label{rec-h-S}
  h_{n+1} = \sum_{k=0}^n s_{n,k} h_k \, .
 \end{equation}
 In particular, if $ R' = [r_{n+1,k+1}]_{n,k\geq0} $, then
 \begin{equation}\label{id-S-R}
  S = R^{-1} R' \, .
 \end{equation}
\end{lemma}
\begin{proof}
 Consider the normalized sequence defined by recurrence (\ref{rec-h-S}).
 This sequence and the matrix $ R $ satisfy the shifting property (\ref{shifting}).
 Indeed, by recurrences (\ref{rec-R-S}) and (\ref{rec-h-S}), we have
 $$
  \sum_{k=0}^n r_{n+1,k+1} h_k =
  \sum_{k=0}^n \left(\sum_{i=k}^n r_{n,i} s_{i,k}\right) h_k =
  \sum_{i=0}^n r_{n,i} \left(\sum_{k=0}^i s_{i,k}h_k \right) =
  \sum_{i=0}^n r_{n,i} h_{i+1} \, .
 $$
 Since by Lemma \ref{lemma-1} there is only one normalized sequence
 satisfying the shifting property (\ref{shifting}) for a given invertible matrix $ R $,
 the first part of the lemma follows.
 To obtain the second part of the lemma,
 just note that identity (\ref{rec-R-S}) is equivalent to $ R' = RS $.
 Since $ R $ is invertible, we have identity (\ref{id-S-R}).
\end{proof}


\section{Shifting property for Riordan matrices}

Recall that the \emph{incremental ratio} is the linear operator $ \map{\R}{\RR[\![x]\!]}{\RR[\![x]\!]} $ defined by
$$
 u(t) = \sum_{n\geq0} u_n t^n
 \qquad\longmapsto\qquad
 \R u(t) = \frac{u(t)-u_0}{t} = \sum_{n\geq0} u_{n+1}\;t^n \, .
$$
Moreover, the \emph{A-series} of a Riordan matrix $ R = (g(t),f(t)) $ is the series
$$ a(t) = \sum_{n\geq0} a_n\;t^n = \frac{t}{\widehat{f}(t)}\, . $$

\begin{theorem}\label{thm-ShPr-Riordan}
 A Riordan matrix $ R = (g(t),f(t)) $ and a normalized sequence $ (h_n)_{n\in\NN} $,
 with ordinary generating series $ h(t) $,
 satisfy the shifting property, if and only if
 \begin{equation}\label{series-h}
  h(t) = \frac{\widehat{f}(t)}{\widehat{f}(t)-t^2} \, ,
 \end{equation}
 or, equivalently, if and only if
 \begin{equation}\label{series-f-inv}
  \widehat{f}(t) = \frac{th(t)}{\R h(t)} \, ,
 \end{equation}
 or, equivalently, if and only if
 \begin{equation}\label{rec-h-R}
  h_{n+1} = \sum_{k=0}^n a_k h_{n-k}
 \end{equation}
 where the numbers $ a_k $ are the coefficients of the $A$-series of the matrix $ R $.
 If the shifting property holds, then the generating series for the shifting sums is
 \begin{equation}\label{series-shifting}
  s(t) = g(t)\,\R h(f(t)) = g(t)\frac{f(t)}{t}\;h(f(t))\, .
 \end{equation}
\end{theorem}
\begin{proof}
 Let $ R = [r_{n,k}]_{n,k\geq0} = (g(t),f(t)) $ be a Riordan matrix.
 Then, for every formal series $ u(t) = \sum_{n\geq0} u_n t^n $, we have the identity
 $$ g(t) u(f(t)) = \sum_{n\geq0} \left[\sum_{k=0}^n r_{n,k} u_k\right] t^n $$
 and the Riordan matrix
 $$ R' = [ r_{n+1,k+1} ]_{n,k\geq0} = \left(g(t)\frac{f(t)}{t},f(t)\right). $$
 Hence, identity (\ref{shifting}) is equivalent to the identity
 $$ g(t) \R h(f(t)) = g(t)\frac{f(t)}{t}\; h(f(t)) $$
 (and this gives series (\ref{series-shifting})).
 Since $ g(t) $ is invertible with respect to multiplication, we have the equivalent identity
 $$ \frac{h(f(t))-1}{f(t)} = \frac{f(t)}{t}\; h(f(t))\, . $$
 Finally, since $ f(t) $ is invertible with respect to composition, we have the equivalent identity
 $$
  \frac{h(t)-1}{t} = \frac{t}{\widehat{f}(t)}\; h(t)
  \qquad\text{or}\qquad
  \R h(t) = a(t) h(t)
 $$
 from which we obtain
 (\ref{series-h}), (\ref{series-f-inv}) and (\ref{rec-h-R}).
\end{proof}

\begin{theorem}\label{thm-Absorbing-Riordan}
 A Riordan matrix $ R = (g(t),f(t)) $ and a normalized sequence $ (h_n)_{n\in\NN} $,
 with ordinary generating series $ h(t) $,
 satisfy the shifting property, if and only if they satisfy the \emph{absorbing identity}
 \begin{equation}\label{id-absorbing-R}
  \sum_{k=0}^n r_{n,k} h_k = \sum_{k=0}^n r_{n+k,2k} \, .
 \end{equation}
\end{theorem}
\begin{proof}
 First, we have
 $$
  \sum_{n\geq0}\left(\sum_{k=0}^n r_{n+k,2k}\right)t^n
  = \sum_{n\geq0} \frac{1}{t^k} \left(\sum_{n\geq k} r_{n,2k}\; t^n\right)
  = \sum_{n\geq0} g(t) \frac{f(t)^{2k}}{t^k}
  = \frac{g(t)}{1-f(t)^2/t}\, .
 $$
 So, identity holds if and only if
 $$ g(t) h(f(t)) = \frac{tg(t)}{t-f(t)^2}\, . $$
 Since $ f(t) $ is invertible with respect to composition
 and $ g(t) $ is invertible with respect to multiplication,
 this relation is equivalent to
 $$ h(t) = \frac{\widehat{f}(t)}{\widehat{f}(t)-t^2} \, , $$
 and, by Theorem (\ref{thm-ShPr-Riordan}), this condition holds
 if and only if the shifting property holds.
\end{proof}

Next lemma will be useful to prove Theorem \ref{thm-shifting-m} and to obtain some examples.
\begin{lemma}
 Let $ R = [r_{n,k}]_{n,k\geq0} = (g(t),f(t)) $ be a Riordan matrix.
 \begin{enumerate}
  \item
   For every $ a \in \NN $, we have the Riordan matrix
   \begin{equation}\label{Riordan-m1}
    R^{(a)} = \left(g(t)\left(\frac{f(t)}{t}\right)^{\!\!a},\, f(t)\right) = [r_{a+n,a+k}]_{n,k\geq0}.
   \end{equation}
  \item
   Let $ g(t) = 1 $. Then, for every $ a \in \NN $, we have the Riordan matrix
   \begin{equation}\label{Riordan-m2}
    R^{[a]} = \left(f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a},f(t)\right)
            = \left[\frac{a+n+1}{a+k+1}\;r_{a+n+1,a+k+1}\right]_{n,k\geq0}.
   \end{equation}
 \end{enumerate}
\end{lemma}
\begin{proof}
 Since
 $$ [t^n]\; g(t)\left(\frac{f(t)}{t}\right)^{\!\!a}f(t)^k = [t^{a+n}]\; g(t)f(t)^{a+k} = r_{a+n,a+k}\, , $$
 we have identity (\ref{Riordan-m1}).
 Moreover, if $ g(t) = 1 $, then
 \begin{eqnarray*}
  [t^n] f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a}f(t)^k
  & = & [t^{a+n}] f'(t)f(t)^{a+k}
    =   [t^{a+n}] \left(\frac{f(t)^{a+k+1}}{a+k+1}\right)' \\
  & = & \frac{a+n+1}{a+k+1}\;[t^{a+n+1}] f(t)^{a+k+1}
    =   \frac{a+n+1}{a+k+1}\;r_{a+n+1,a+k+1} \, ,
 \end{eqnarray*}
 and we also have identity (\ref{Riordan-m2}).
\end{proof}

By Theorem \ref{thm-ShPr-Riordan} (resp. Theorem \ref{thm-Absorbing-Riordan}),
the shifting property (resp. absorbing property) for a Riordan matrix $ R = (g(t),f(t)) $
depends only on the series $ f(t) $, but not on the series $ g(t) $.
So, for any sequence $ (h_n)_{n\in\NN} $,
there are infinite Riordan matrices satisfying the shifting property (resp. absorbing property).
In particular, we have
\begin{theorem}\label{thm-shifting-m}
 If a Riordan matrix $ R = [r_{n,k}]_{n,k\geq0} = (g(t),f(t)) $
 and a normalized sequence $ (h_n)_{n\in\NN} $
 satisfy the shifting property, then
 \begin{align}
  & \sum_{k=0}^n r_{a+n,a+k} h_{k+1} = \sum_{k=0}^n r_{a+n+1,a+k+1} h_k \label{shifting-m1} \\
  & \sum_{k=0}^n r_{a+n,a+k} h_k = \sum_{k=0}^n r_{a+n+k,a+2k} \label{absorbing-m1}
 \end{align}
 for every $ a \in \NN $.
 In this case, the generating series for the shifting sums is
 \begin{equation}\label{series-shifting-m1}
  s(t) = g(t)\left(\frac{f(t)}{t}\right)^{\!\!a}\R h(f(t)) = g(t)\left(\frac{f(t)}{t}\right)^{\!\!a+1} h(f(t))
 \end{equation}
 and
 \begin{equation}\label{seriescoeff-shifting-m1}
  s_n = \sum_{k=0}^n r_{a+n+k+1,a+2k+1} \, .
 \end{equation}

 Moreover, if $ g(t) = 1 $, then
 \begin{align}
  & \sum_{k=0}^n \frac{a+n+1}{a+k+1}\;r_{a+n+1,a+k+1} h_{k+1}
  = \sum_{k=0}^n \frac{a+n+2}{a+k+2}\;r_{a+n+2,a+k+2} h_k \label{shifting-m2} \\
  & \sum_{k=0}^n \frac{a+n+1}{a+k+1}\;r_{a+n+1,a+k+1} h_k
  = \sum_{k=0}^n \frac{a+n+k+1}{a+2k+1}\;r_{a+n+k+1,a+2k+1} \label{absorbing-m2}
 \end{align}
 for every $ a \in \NN $.
 In this case, the generating series for the shifting sums is
 \begin{equation}\label{series-shifting-m2}
  s(t) = f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a}\R h(f(t)) = f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a+1} h(f(t))
 \end{equation}
 and
 \begin{equation}\label{seriescoeff-shifting-m2}
  s_n = \sum_{k=0}^n \frac{a+n+k+2}{a+2k+2}\;r_{a+n+k+2,a+2k+2}\, .
 \end{equation}
\end{theorem}
\begin{proof}
 In the Riordan matrices (\ref{Riordan-m1}) and (\ref{Riordan-m2})
 the second series is always $ f(t) $, for all $ a \in \NN $.
 So, both matrices (\ref{Riordan-m1}) and (\ref{Riordan-m2}), with the sequence $ (h_n)_{n\in\NN} $,
 satisfy the shifting property and the absorbing property, for all $ a \in \NN $.
 Moreover, series (\ref{series-shifting-m1}) and (\ref{series-shifting-m2})
 derive from Riordan matrices (\ref{Riordan-m1}) and (\ref{Riordan-m2}) and identity (\ref{series-shifting}).
 Finally, identities (\ref{seriescoeff-shifting-m1}) and (\ref{seriescoeff-shifting-m2})
 are just a reformulation of the absorbing property.
\end{proof}

\begin{examples}
 \item If $ h_n $ is the \emph{generalized Fibonacci number}\footnote{
  For $ m = 2, 3, 4, 5, 6, 7, 8 $, we have
  the \emph{Fibonacci numbers} $ f^{[2]}_n $ (\seqnum{A000045}),
  the \emph{Tribonacci numbers} $ f_n^{[3]} $ (\seqnum{A000073}),
  the \emph{Tetranacci numbers} $ f_n^{[4]} $ (\seqnum{A000078}),
  the \emph{Pentanacci numbers} $ f_n^{[5]} $ (\seqnum{A001591}),
  the \emph{Hexanacci numbers} $ f_n^{[6]} $ (\seqnum{A001592}),
  the \emph{Heptanacci numbers} $ f_n^{[7]} $ (\seqnum{A122189},\seqnum{A066178}),
  the \emph{Octanacci numbers} $ f_n^{[8]} $ (\seqnum{A079262}),
  and so on. See \cite{MunariniGenFibo}.}
  $ f^{[m]}_n $,
  with $ m \in \NN $, $ m \geq 1 $, then, by Theorem \ref{thm-ShPr-Riordan}, we have
  $$
   h(t) = \sum_{n\geq0} f^{[m]}_n\;t^n = \frac{1}{1-t-t^2-\cdots-t^m} \qquad\text{and}\qquad
   \widehat{f}(t) = \frac{t}{1+t+t^2+\cdots+t^{m-1}} \, .
  $$

  In particular, for $ m = 2 $, we have the \emph{Fibonacci numbers} $ f^{[2]}_n = f_n = F_{n+1} $ and
  $$
   h(t) = \frac{1}{1-t-t^2} \quad\iff\quad
   \widehat{f}(t) = \frac{t}{1+t} \quad\iff\quad
   f(t) = \frac{t}{1-t} \, .
  $$
  Moreover, for $ m = 3 $, we have
 \begin{align*} 
   h(t) = \frac{1}{1-t-t^2-t^3} &\quad\iff\quad
   \widehat{f}(t) = \frac{t}{1+t+t^2} \\
   & \quad\iff\quad
   f(t) = \frac{1-t-\sqrt{1-2t-3t^2}}{2t} \, .
\end{align*}

  Let us consider the Riordan matrix $ R = (1,f(t)) $.
  Since the \emph{polynomial coefficients}\footnote{For $ m = 2, 3, \ldots, 10 $, we have
  the \emph{binomial coefficients} \seqnum{A007318},
  the \emph{trinomial coefficients} \seqnum{A027907},
  the \emph{quadrinomial coefficients} \seqnum{A008287},
  the \emph{pentanomial coefficients} \seqnum{A035343},
  the \emph{hexanomial} or \emph{sextinomial coefficients} \seqnum{A063260},
  the \emph{heptanomial} or \emph{septinomial coefficients} \seqnum{A063265},
  the \emph{octonomial coefficients} \seqnum{A171890},
  the \emph{9-nomial coefficients} \seqnum{A213652},
  the \emph{10-nomial coefficients} \seqnum{A213651}.} \cite{Comtet} are defined by
  $$ (1+x+x^2+\cdots+x^{m-1})^n = \sum_{k=0}^{(m-1)n} { n;\,m \choose k } x^k \, , $$
  by the Lagrange inversion formula we have
\begin{align*}
   r_{n,k} &= [t^n]f(t)^k
   = \frac{k}{n}\;[t^{n-k}]\left(\frac{t}{\widehat{f}(t)}\right)^{\!\!n} \\
   &= \frac{k}{n}\;[t^{n-k}](1+t+t^2+\cdots+t^{m-1})^n
   = { n;\,m \choose n-k }\frac{k}{n}
\end{align*}
  for every $ n,k \in \NN $, $ n \geq 1 $.
  So, identities (\ref{shifting-m1}) and (\ref{shifting-m2}) become
  \begin{align}
    \sum_{k=0}^n { a+n;\,m \choose n-k }\frac{a+k}{a+n}\;f^{[m]}_{k+1} &=
   \sum_{k=0}^n { a+n+1;\,m \choose n-k }\frac{a+k+1}{a+n+1}\;f^{[m]}_k \\
    \sum_{k=0}^n { a+n+1;\,m \choose n-k } f^{[m]}_{k+1} &=
     \sum_{k=0}^n { a+n+2;\,m \choose n-k } f^{[m]}_k \, .
  \end{align}
  In particular, for $ m = 2 $, these two identities are equivalent and become
  \begin{equation}\label{identity-Bin-Fibo-a}
   \sum_{k=0}^n { a+n \choose a+k } f_{k+1} = \sum_{k=0}^n { a+n+1 \choose a+k+1 } f_k \, .
  \end{equation}
  Moreover, and for $ a = 0 $, we have the identity
  \begin{equation}\label{identity-Bin-Fibo}
   \sum_{k=0}^n { n \choose k } f_{k+1} = \sum_{k=0}^n { n+1 \choose k+1 } f_k \, .
  \end{equation}
  Finally, by (\ref{seriescoeff-shifting-m1}), we also have the identities
  \begin{align}
   & \sum_{k=0}^n { a+n;\,m \choose n-k }\frac{a+k}{a+n}\;f^{[m]}_{k+1} =
     \sum_{k=0}^n { a+n+k+1;\,m \choose n-k }\frac{a+2k+1}{a+n+k+1} \\
   & \sum_{k=0}^n { a+n+1;\,m \choose n-k }\frac{a+k+1}{a+n+1}\;f^{[m]}_k =
     \sum_{k=0}^n { a+n+k+1;\,m \choose n-k }\frac{a+2k+1}{a+n+k+1}
  \end{align}
  and by (\ref{seriescoeff-shifting-m2}), we have the identities
  \begin{align}
   & \sum_{k=0}^n { a+n+1;\,m \choose n-k } f^{[m]}_{k+1} = \sum_{k=0}^n { a+n+k+2;\,m \choose n-k } \\
   & \sum_{k=0}^n { a+n+2;\,m \choose n-k } f^{[m]}_k = \sum_{k=0}^n { a+n+k+2;\,m \choose n-k }\, .
  \end{align}
 \item If $ h_n $ is the \emph{Catalan number} $ C_n = { 2n \choose n }\frac{1}{n+1} $ (\seqnum{A000108}),
  then, by Theorem \ref{thm-ShPr-Riordan}, we have
  $$
   h(t) = \frac{1-\sqrt{1-4t}}{2t} \qquad\text{and}\qquad
   \widehat{f}(t) = t\;\frac{1+\sqrt{1-4t}}{2} \, .
  $$
  Notice that $ h(t) = t/\widehat{f}(t) = a(t) $.

  Consider the Riordan matrix $ R = (1,f(t)) $.
  By the Lagrange inversion formula, we have
  $$
   r_{n,k} = [t^n]f(t)^k
   = \frac{k}{n}\;[t^{n-k}]\left(\frac{t}{\widehat{f}(t)}\right)^{\!\!n}
   = \frac{k}{n}\;[t^{2n-k}]\left(\frac{1-\sqrt{1-4t}}{2}\right)^{\!\!n}
   = { 3n-2k \choose n-k }\frac{k}{3n-2k}
  $$
  for every $ n,k \in \NN $, $ n \geq 1 $.
  So, replacing $ a $ with $ a+1 $, identities (\ref{shifting-m1}) and (\ref{shifting-m2}) become
  \begin{align}
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+k+1}{a+3n-2k+1}\;C_{k+1} =
     \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+k+2}{a+3n-2k+2}\;C_k \label{id-shifting-Catalan-01} \\
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+n+1}{a+3n-2k+1}\;C_{k+1} =
     \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+n+2}{a+3n-2k+2}\;C_k \label{id-shifting-Catalan-02}\, .
  \end{align}
  Moreover, by (\ref{seriescoeff-shifting-m1}), we have the identities
  \begin{align}
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+k+1}{a+3n-2k+1}\;C_{k+1}
   = \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+2k+2}{a+3n-k+2} \\
   & \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+k+2}{a+3n-2k+2}\;C_k
   = \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+2k+2}{a+3n-k+2}
  \end{align}
  and by (\ref{seriescoeff-shifting-m2}), we have the identities
  \begin{align}
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+n+1}{a+3n-2k+1}\;C_{k+1}
   = \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+n+k+2}{a+3n-k+2} \\
   & \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+n+2}{a+3n-2k+2}\;C_k
   = \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+n+k+2}{a+3n-k+2} \, .
  \end{align}
  In this case, we obtain a closed form for the shifting identities.
  Indeed, since the generating series for the sums (\ref{id-shifting-Catalan-01}) is given by (\ref{shifting-m1}), we have
  \begin{eqnarray*}
   \lefteqn{
      [t^n] \left(\frac{f(t)}{t}\right)^{\!\!a+1} h(f(t))
    = [t^n] \left(\frac{f(t)}{t}\right)^{\!\!a+1} \frac{f(t)}{t}
    = [t^n] \left(\frac{f(t)}{t}\right)^{\!\!a+2} =
   } && \\ &&
    = [t^{a+n+2}] f(t)^{a+2}
    = { a+3n+2 \choose n }\frac{a+2}{a+3n+2}
    = { a+3n+1 \choose n }\frac{a+2}{a+2n+2}.
  \end{eqnarray*}
  So, we also have the identities
  \begin{align}
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+k+1}{a+3n-2k+1}\;C_{k+1} = { a+3n+2 \choose n }\frac{a+3}{a+2n+3} \\
   & \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+k+2}{a+3n-2k+2}\;C_k = { a+3n+2 \choose n }\frac{a+3}{a+2n+3} \\
   & \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+2k+2}{a+3n-k+2} = { a+3n+2 \choose n }\frac{a+3}{a+2n+3} \, .
  \end{align}
  For $ a = 0, 1, \ldots, 7 $ we have sequences \seqnum{A001764}, \seqnum{A006629}, \seqnum{A102893}, \seqnum{A006630},
  \seqnum{A102594}, \seqnum{A006631}, \seqnum{A230547}, \seqnum{A233657}.

  Similarly, since the generating series for the sums (\ref{id-shifting-Catalan-02}) is given by (\ref{shifting-m2}),
  we have
  \begin{eqnarray*}
   \lefteqn{
      [t^n] f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a+1} h(f(t))
    = [t^n] f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a+1} \frac{f(t)}{t}
    = [t^n] f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a+2} =
   } && \\
   &&
    = [t^{a+n+2}] f'(t)f(t)^{a+2}
    = [t^{a+n+2}] \left(\frac{f(t)^{a+3}}{a+3}\right)'
    = \frac{a+n+3}{a+3}\;[t^{a+n+3}] f(t)^{a+3} \\
   &&
    = { a+3n+3 \choose n }\frac{a+n+3}{a+3n+3}
    = { a+3n+2 \choose n }\frac{a+n+3}{a+2n+3}.
  \end{eqnarray*}
  So, we also have the identities
  \begin{align*}
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+n+1}{a+3n-2k+1}\;C_{k+1} = { a+3n+2 \choose n }\frac{a+n+3}{a+2n+3} \\
   & \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+n+2}{a+3n-2k+2}\;C_k = { a+3n+2 \choose n }\frac{a+n+3}{a+2n+3} \\
   & \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+n+k+2}{a+3n-k+2} = { a+3n+2 \choose n }\frac{a+n+3}{a+2n+3}\, .
  \end{align*}
 \item If $ h_n $ is the \emph{central binomial coefficients} $ { 2n \choose n } $ (\seqnum{A000984}),
  then, by Theorem \ref{thm-ShPr-Riordan}, we have
  $$
   h(t) = \frac{1}{\sqrt{1-4t}}\, , \qquad
   \widehat{f}(t) = t\frac{1+\sqrt{1-4t}}{4} \qquad\text{and}\qquad
   \frac{1}{\sqrt{1-4f(t)}} = \frac{f(t)}{4t-f(t)} \, .
  $$
  So, the situation is very similar to the one we have already considered for the Catalan numbers.
  In particular, for the Riordan matrix $ R = (1,f(t)) $, we have
  $$  r_{n,k} = { 3n-2k \choose n-k }\frac{k}{3n-2k}\;2^n \qquad (n,k \in \NN \, , n \geq 1)\, . $$
  So, after some simplifications of identities (\ref{shifting-m1}) and (\ref{shifting-m2}),
  we obtain
  \begin{align}
   & \sum_{k=0}^n { a+3n-2k \choose n-k }\frac{a+k}{a+3n-2k}\;{ 2k+1 \choose k+1 } = \\
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+n+1}{a+3n-2k+1}\;{ 2k \choose k } \\
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+n+1}{a+3n-2k+1}\;{ 2k+1 \choose k+1 } = \\
   & \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+n+2}{a+3n-2k+2}\;{ 2k \choose k } \, .
  \end{align}
  Again, by (\ref{seriescoeff-shifting-m1}), we have the identities
  \begin{align}
   & \sum_{k=0}^n { a+3n-2k \choose n-k }\frac{a+k}{a+3n-2k}\;{ 2k+1 \choose k+1 }
   = \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+2k+2}{a+3n-k+2}\;2^k \\
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+n+1}{a+3n-2k+1}\;{ 2k \choose k }
   = \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+2k+2}{a+3n-k+2}\;2^k
  \end{align}
  and, by (\ref{seriescoeff-shifting-m2}), we have the identities
  \begin{align}
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+n+1}{a+3n-2k+1}\;{ 2k+1 \choose k+1 } \\
   & = \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+n+k+2}{a+3n-k+2}\;2^k \\
   & \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+n+2}{a+3n-2k+2}\;{ 2k \choose k } \\
   & = \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+n+k+2}{a+3n-k+2}\;2^k \, .
  \end{align}
  These last identities admit a closed form.
  Indeed, by (\ref{series-shifting-m2}), we have
  $$
   s(t) = f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a+1} h(f(t))
        = f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a+1} \frac{1}{\sqrt{1-4f(t)}}
        = f'(t)\left(\frac{f(t)}{t}\right)^{\!\!a+1} \frac{f(t)}{4t-f(t)}\, .
  $$
  Then, using the Cauchy integral formula, we have
  $$
   s_n = [t^{a+n+1}]\;\frac{f(t)^{a+2}}{4t-f(t)}\;f'(t)
       = \frac{1}{2\pi\ii} \oint \frac{f(z)^{a+2}}{4z-f(z)}\;f'(z)\;\frac{\dd z}{z^{a+n+2}} \, .
  $$
  Setting $ w = f(z) $, we have $ z = \widehat{f}(w) $, $ \dd w = f'(z)\,\dd z $ and
  \begin{eqnarray*}
   \lefteqn{
    s_n = \frac{1}{2\pi\ii} \oint \left(\frac{w}{\widehat{f}(w)}\right)^{\!\!a+n+2}
          \frac{w}{4\widehat{f}(w)-w}\;\frac{\dd w}{w^{n+1}}
        = [t^n] \left(\frac{t}{\widehat{f}(t)}\right)^{\!\!a+n+2}\frac{t}{4\widehat{f}(t)-t} =
   } && \\ &&
        = 2^{a+n+1}\,[t^{a+2n+1}] \frac{1}{\sqrt{1-4t}}\left(\frac{1-\sqrt{1-4t}}{2}\right)^{\!\!a+n+2}
        = { a+3n+2 \choose n } 2^{a+n+1}\, .
  \end{eqnarray*}
   So, we have the identities
  \begin{align}
   & \sum_{k=0}^n { a+3n-2k+1 \choose n-k }\frac{a+n+1}{a+3n-2k+1}\;{ 2k+1 \choose k+1 } = { a+3n+2 \choose n } \\
   & \sum_{k=0}^n { a+3n-2k+2 \choose n-k }\frac{a+n+2}{a+3n-2k+2}\;{ 2k \choose k } = { a+3n+2 \choose n } \\
   & \sum_{k=0}^n { a+3n-k+2 \choose n-k }\frac{a+n+k+2}{a+3n-k+2}\;2^k = { a+3n+2 \choose n } \, .
  \end{align}
  For $ a = 0, 1, 2, 3, 4 $ we have the sequences \seqnum{A025174}, \seqnum{A004319}, \seqnum{A236194}, \seqnum{A236194}, \seqnum{A236194}.
 \item If $ h_n $ is the \emph{Chebyshev polynomial of the second kind} $ U_n(x) $, then we have
  $$ h(t) = \frac{1}{1-2xt+t^2} \quad\iff\quad f(t) = \frac{2xt}{1+t}\, . $$
  So, if we consider the Riordan matrix
  $$
   R = \left( 1, \frac{2xt}{1+t} \right)
     = \left[ { n-1 \choose n-k } (-1)^{n-k} (2x)^k \right]_{n,k\geq0},
  $$
  then, replacing $ a $ with $ a+1 $ in identities (\ref{shifting-m1}) and (\ref{shifting-m2}), we obtain
  \begin{equation}
    \sum_{k=0}^n { a+n \choose n-k } (-1)^{n-k} (2x)^k U_{k+1}(x) =
     \sum_{k=0}^n { a+n+1 \choose n-k } (-1)^{n-k} (2x)^{k+1} U_k(x) 
\end{equation}
   \begin{multline}
   \sum_{k=0}^n { a+n+1 \choose n-k }\frac{a+n+2}{a+k+2}\; (-1)^{n-k} (2x)^k U_{k+1}(x) = \\
     \sum_{k=0}^n { a+n+2 \choose n-k }\frac{a+n+3}{a+k+3}\; (-1)^{n-k} (2x)^{k+1} U_k(x) \, .
  \end{multline}
  Moreover, by (\ref{seriescoeff-shifting-m1}), we have the identities
  \begin{align}
   & \sum_{k=0}^n { a+n \choose n-k } (-1)^{n-k} (2x)^k U_{k+1}(x)
   = \sum_{k=0}^n  { a+n+k+1 \choose n-k } (-1)^{n-k}(2x)^{2k+1} \\
   & \sum_{k=0}^n { a+n+1 \choose n-k } (-1)^{n-k} (2x)^{k+1} U_k(x)
   = \sum_{k=0}^n  { a+n+k+1 \choose n-k } (-1)^{n-k}(2x)^{2k+1}
  \end{align}
  and, by (\ref{seriescoeff-shifting-m2}), we have the identities
  \begin{equation}
   \begin{aligned}
    \MoveEqLeft
     \sum_{k=0}^n { a+n+1 \choose n-k }\frac{a+n+2}{a+k+2}\; (-1)^{n-k} (2x)^k U_{k+1}(x)  \\
    &= \sum_{k=0}^n  { a+n+k+2 \choose n-k }\frac{a+n+k+3}{a+2k+3}\; (-1)^{n-k}(2x)^{2k+1}
   \end{aligned}
  \end{equation}
  \begin{equation}
   \begin{aligned}
    \MoveEqLeft
     \sum_{k=0}^n { a+n+2 \choose n-k }\frac{a+n+3}{a+k+3}\; (-1)^{n-k} (2x)^{k+1} U_k(x)  \\
   &= \sum_{k=0}^n  { a+n+k+2 \choose n-k }\frac{a+n+k+3}{a+2k+3}\; (-1)^{n-k}(2x)^{2k+1} \, .
   \end{aligned}
  \end{equation}

  Similarly, if $ h_n $ is the \emph{Chebyshev polynomial of the first kind} $ T_n(x) $,
  then we have
 \begin{align*} 
   h(t) = \frac{1-xt}{1-2xt+t^2} & \quad\iff\quad
   \widehat{f}(t) = \frac{t-xt^2}{x-t} \\
   & \quad\iff\quad
   f(t) = \frac{1+t-\sqrt{1+2(1-2x)t+t^2}}{1+t}\, .
\end{align*}
  Consider the Riordan matrix $ R = [R_{n,k}(x)]_{n,k\geq0} = (f(t)/t,f(t)) $.
  Then, by the Lagrange inversion formula, we have
 \begin{align*} 
   R_{n,k}(x) = [t^n]\frac{f(t)}{t}\;f(t)^k = [t^{n+1}]f(t)^{k+1}
   & = \frac{k+1}{n+1}\;[t^{n-k}]\left(\frac{t}{\widehat{f}(t)}\right)^{\!\!n+1} \\
&   = \frac{k+1}{n+1}\;[t^{n-k}]\left(\frac{x-t}{1-xt}\right)^{\!\!n+1}
\end{align*}
  and so
  $$ R_{n,k}(x) = \sum_{i=0}^{n-k} { n \choose i } { 2n-k-i \choose n } \frac{k+1}{n-i+1}\;(-1)^ix^{2n-2i-k+1}\, . $$
  For these polynomials, we have the shifting identities
  \begin{align}
   & \sum_{k=0}^n R_{a+n,a+k}(x) T_{k+1}(x) = \sum_{k=0}^n R_{a+n+1,a+k+1}(x) T_k(x) \\
   & \sum_{k=0}^n \frac{a+n+1}{a+k+1}\;R_{a+n,a+k}(x) T_{k+1}(x)
   = \sum_{k=0}^n \frac{a+n+2}{a+k+2}\;R_{a+n+1,a+k+1}(x) T_k(x) \, .
  \end{align}
  Finally, as we did for (\ref{seriescoeff-shifting-m1}) and (\ref{seriescoeff-shifting-m2}),
  we can also obtain the identities
  \begin{align}
   & \sum_{k=0}^n R_{a+n,a+k}(x) T_{k+1}(x) = \sum_{k=0}^n R_{a+n+k+1,a+k+1}(x) \\
   & \sum_{k=0}^n R_{a+n+1,a+k+1}(x) T_k(x) = \sum_{k=0}^n R_{a+n+k+1,a+k+1}(x)
  \end{align}
  and
  \begin{align}
   & \sum_{k=0}^n \frac{a+n+1}{a+k+1}\;R_{a+n,a+k}(x) T_{k+1}(x)
   = \sum_{k=0}^n \frac{a+n+k+2}{a+2k+2}\;R_{a+n+k+1,a+k+1}(x) \\
   & \sum_{k=0}^n \frac{a+n+2}{a+k+2}\;R_{a+n+1,a+k+1}(x) T_k(x)
   = \sum_{k=0}^n \frac{a+n+k+2}{a+2k+2}\;R_{a+n+k+1,a+k+1}(x) \, .
  \end{align}
\end{examples}

\section{Shifting property for Sheffer matrices}

First, we consider the particular case of Sheffer matrices with $ g(t) = 1 $,
and then we consider the general case which is more complex.
\begin{theorem}\label{thm-exp-shifting-g1}
 A Sheffer matrix $ R = (1,f(t)) $ and a normalized sequence $ (h_n)_{n\in\NN} $,
 with exponential generating series $ h(t) $,
 satisfy the shifting property, if and only if
 \begin{equation}\label{series-h-exp-g1}
  h(t) = \ee^{\int_0^t f'(\widehat{f}(u))\,\dd u} \, ,
 \end{equation}
 or, equivalently, if and only if
 \begin{equation}\label{series-h-exp-inv-g1}
  \widehat{f}(t) = \int_0^t \frac{h(u)}{h'(u)}\; \dd u \, .
 \end{equation}
 In particular, the numbers $ h_n $ satisfy the recurrence
 \begin{equation}\label{rec-h-exp-g1}
  h_{n+1} = \sum_{k=0}^n s_{n,k} h_k
 \end{equation}
 where
 \begin{equation}\label{id-snk-exp-g1}
  s_{n,k} = \frac{n!}{k!}\;[t^{n-k}]\frac{1}{\widehat{f}'(t)}\, .
 \end{equation}
 If the shifting property holds, then the exponential generating series for the shifting sums is
 \begin{equation}\label{series-exp-shifting}
  s(t) = f'(t) \ee^{\int_0^t f'(u)^2\dd u}\, .
 \end{equation}
\end{theorem}
\begin{proof}
 Let $ R = [r_{n,k}]_{n,k\geq0} = (g(t),f(t)) $ be a Sheffer matrix.
 Then, for every exponential formal series $ u(t) = \sum_{n\geq0} u_n \frac{t^n}{n!} $, we have the identity
 $$ g(t)\, u(f(t)) = \sum_{n\geq0} \left[\sum_{k=0}^n r_{n,k} u_k\right] \frac{t^n}{n!} $$
 and (for $ g(t) = 1 $) the Sheffer matrix
 $$ R' = [ r_{n+1,k+1} ]_{n,k\geq0} = \left(f'(t),f(t)\right). $$
 Hence, if $ g(t) = 1 $, then identity (\ref{shifting}) turns out to be equivalent to the identity
 \begin{equation}\label{eq-exp-shifting}
  h'(f(t)) = f'(t)\; h(f(t))\, .
 \end{equation}
 Since $ f(t) $ is invertible with respect to composition, we have the equivalent identity
 $$ h'(t) = f'(\widehat{f}(t))\; h(t) $$
 from which we obtain (\ref{series-h-exp-g1}).
 Since $ f'(\widehat{f}(t)) = 1/\widehat{f}'(t) $, we also have the identity
 $$ \widehat{f}'(t) = \frac{h(t)}{h'(t)} $$
 from which we have (\ref{series-h-exp-inv-g1}).
 Finally, recurrence (\ref{rec-h-exp-g1}) derives from recurrence (\ref{rec-h-S}),
 where, by identity (\ref{id-S-R}), the Sheffer matrix $ S = [ s_{n,k} ]_{n,k\geq0} $ is defined by
 $$
  S = R^{-1}R' = (1,\widehat{f}(t))(f'(t),f(t))
    = (f'(\widehat{f}(t)),t)
    = \left(\frac{1}{\widehat{f}'(t)},t\right).
 $$
 This also implies (\ref{id-snk-exp-g1}).
 Finally, by (\ref{eq-exp-shifting}) and (\ref{series-h-exp-g1}),
 we obtain the exponential generating series for the shifting sums:
 $$ s(t) = f'(t)\; h(f(t)) = f'(t)\; \ee^{\int_0^{f(t)} f'(\widehat{f}(v))\,\dd v} \, . $$
 Setting $ u = \widehat{f}(v) $, we have $ v = f(u) $, $ \dd v = f'(u)\;\dd u $
 and $ s(t) $ assumes the form in (\ref{series-exp-shifting}).
\end{proof}

\begin{examples}
 \item\label{Ex-Stirling1} By Theorem \ref{thm-exp-shifting-g1}, we have
  $$ f(t) = \ln\frac{1}{1-t} \quad\iff\quad \widehat{f}(t) = 1-\ee^{-t} \quad\iff\quad h(t) = \ee^{\ee^t-1} \, . $$
  In this case, the numbers $ h_n $ are the \emph{Bell numbers} $ b_n $ (\seqnum{A000110}).
  Since $ \widehat{f}(t) = 1-\ee^{-t} $ and $ \widehat{f}'(t) = \ee^{-t} $,
  we have $ s_{n,k} = \frac{n!}{k!}[t^{n-k}]\ee^t = { n \choose k } $,
  and recurrence (\ref{rec-h-exp-g1}) becomes the usual recurrence for the Bell numbers:
  $$ b_{n+1} = \sum_{k=0}^n { n \choose k } b_k \, . $$

  In particular, for the Sheffer matrix of the \emph{Stirling numbers of the first kind}
  \cite{GrahamKnuthPatashnik} (\seqnum{A132393})
  $$ R = \left[ { n \brack k } \right]_{n,k\geq0} = \left( 1, \ln\frac{t}{1-t} \right), $$
  we have the shifting identity
  \begin{equation}\label{sum-Stirling1-Bell}
   \sum_{k=0}^n { n \brack k } b_{k+1} = \sum_{k=0}^n { n+1 \brack k+1 } b_k \, .
  \end{equation}
  By identity (\ref{series-exp-shifting}), we obtain the series
  $$ s(t) = \frac{1}{1-t}\;\ee^{\frac{t}{1-t}} $$
  (which is the exponential generating series for sequence \seqnum{A002720}). Since
  $$ \ee^{\frac{t}{1-t}} = \sum_{n\geq0} \ell_n\;\frac{t^n}{n!} $$
  is the exponential generating series of the \emph{cumulative Lah numbers} (\seqnum{A000262}),
  we also have the identities
  \begin{equation}
   \sum_{k=0}^n { n \brack k } b_{k+1}
   = \sum_{k=0}^n { n+1 \brack k+1 } b_k
   = \sum_{k=0}^n { n \choose k } (n-k)! \ell_k \, .
  \end{equation}
 \item\label{Ex-Stirling2} By Theorem \ref{thm-exp-shifting-g1}, we have
  $$ f(t) = \ee^t-1 \quad\iff\quad \widehat{f}(t) = \ln(1+t) \quad\iff\quad h(t) = \ee^{t+t^2/2} \, . $$
  In this case, the numbers $ h_n $ are the \emph{involution numbers} $ i_n $ (\seqnum{A000085}).
  Since $ \widehat{f}(t) = \ln(1+t) $ and $ \widehat{f}'(t) = \frac{1}{1+t} $, we have
  $$
   s_{n,k} = \frac{n!}{k!}[t^{n-k}](1+t) =
   \begin{cases}
    1, & \text{if } k = n; \\
    n, & \text{if } k = n-1; \\
    0, & \text{otherwise}\, ,
   \end{cases}
  $$
  and recurrence (\ref{rec-h-exp-g1}) becomes the usual recurrence for the involution numbers:
  $ i_{n+1} = i_n + n i_{n-1} $ (for $ n \geq 1 $).

  In particular, for the Sheffer matrix of the \emph{Stirling numbers of the second kind}
  \cite{GrahamKnuthPatashnik} (\seqnum{A008277})
  $$ R = \left[ { n \brace k } \right]_{n,k\geq0} = \left( 1, \ee^t-1 \right), $$
  we have the shifting identity
  \begin{equation}\label{sum-Stirling2-inv}
   \sum_{k=0}^n { n \brace k } i_{k+1} = \sum_{k=0}^n { n+1 \brace k+1 } i_k
  \end{equation}
  Finally, by identity (\ref{series-exp-shifting}), we obtain the series
  $$ s(t) = \ee^{t+\ee^t\sinh t} $$
  which is the exponential generating series for the \emph{Dowling numbers} (\seqnum{A007405}).
 \item\label{Ex-Lah} By Theorem \ref{thm-exp-shifting-g1}, we have
  $$ f(t) = \frac{t}{1-t} \quad\iff\quad \widehat{f}(t) = \frac{t}{1+t} \quad\iff\quad h(t) = \ee^{t+t^2+t^3/3} \, . $$
  In this case, the numbers $ h_n $ form sequence \seqnum{A049425}.
  Since $ \widehat{f}(t) = \frac{t}{1+t} $ and $ \widehat{f}'(t) = \frac{1}{(1+t)^2} $, we have
  $$
   s_{n,k} = \frac{n!}{k!}[t^{n-k}](1+t)^2 =
   \begin{cases}
         1, & \text{if } k = n;   \\
        2n, & \text{if } k = n-1; \\
    n(n-1), & \text{if } k = n-2; \\
         0, & \text{otherwise}\, ,
   \end{cases}
  $$
  and recurrence (\ref{rec-h-exp-g1}) becomes $ h_{n+1} = h_n + 2 n h_{n-1} + n(n-1) h_{n-2} $ (for $ n \geq 2 $).

  In particular, for the Sheffer matrix of the \emph{Lah numbers} (\seqnum{A105287})
  $$ R = \left[ { n \lah k } \right]_{n,k\geq0} = \left( 1, \frac{t}{1-t} \right), $$
  we have the shifting identity
  \begin{equation}
   \sum_{k=0}^n { n \lah k } h_{k+1} = \sum_{k=0}^n { n+1 \lah k+1 } h_k \, .
  \end{equation}
  Finally, by identity (\ref{series-exp-shifting}), we obtain the series
  $$ s(t) = \frac{1}{(1-t)^2}\;\ee^{\frac{3t-3t^2+t^3}{3(1-t)^3}}\, . $$
 \item
  If $ h_n $ is the \emph{Stirling polynomial} $ S_n(x) = \sum_{k=0}^n { n \brace k } x^k $,
  then, by identity (\ref{series-h-exp-inv-g1}), we have
  $$
   h(t) = \ee^{x(\ee^t-1)} \quad\iff\quad
   \widehat{f}(t) = \frac{1-\ee^{-t}}{x} \quad\iff\quad
   f(t) = \ln\frac{1}{1-xt}\, .
  $$
  So, if we consider the Sheffer matrix
  $$  R = \left(1,\ln\frac{1}{1-xt}\right) = \left[ { n \brack k } x^n \right]_{n,k\geq0}, $$
  then the shifting identity simplifies in
  \begin{equation}
   \sum_{k=0}^n { n \brack k } S_k(x) = x \sum_{k=0}^n { n+1 \brack k+1 } S_{k+1}(x)\, .
  \end{equation}
  By identity (\ref{series-exp-shifting}), we obtain the series
  $$ s(t) = \frac{x}{1-xt}\;\ee^{\frac{x^2t}{1-xt}}. $$
  Since
  $$ \ee^{\frac{x^2t}{1-xt}} = \sum_{n\geq0} x^nL_n(x)\;\frac{t^n}{n!} $$
  where the coefficients
  $$ L_n(x) = \sum_{k=0}^n { n \lah k } x^k $$
  are the \emph{Lah polynomials}, we also have the identities
  \begin{equation}
   \sum_{k=0}^n { n \brack k } S_k(x)
   = x \sum_{k=0}^n { n+1 \brack k+1 } S_{k+1}(x)
   = \sum_{k=0}^n { n \choose k } (n-k)! L_k(x) \, .
  \end{equation}
 \item
  If $ h_n $ is the \emph{Hermite polynomial} $ H_n(x) $ \cite{Roman},
  then, by identity (\ref{series-h-exp-inv-g1}), we have
  $$
   h(t) = \ee^{2xt-t^2} \quad\iff\quad
   \widehat{f}(t) = -\frac{1}{2}\;\ln\left(1-\frac{x}{t}\right) \quad\iff\quad
   f(t) = -x(\ee^{-2t}-1)\, .
  $$
  So, if we consider the Sheffer matrix
  $$  R = (1,-x(\ee^{-2t}-1)) = \left[ { n \brace k } (-1)^{n-k} 2^n x^k \right]_{n,k\geq0}, $$
  then the shifting identity simplifies in
  \begin{equation}
   \sum_{k=0}^n { n \brace k } (-1)^{n-k} x^k H_k(x) =
   2 \sum_{k=0}^n { n+1 \brace k+1 } (-1)^{n-k} x^{k+1} H_{k+1}(x)\, .
  \end{equation}
  By identity (\ref{series-exp-shifting}), we obtain the series
  $$ s(t) =  2x \ee^{-2t+x^2(1-\ee^{-4t})}\, . $$
\end{examples}

More in general, we have
\begin{theorem}
 A Sheffer matrix $ R = (g(t),f(t)) $
 and a normalized sequence $ (h_n)_{n\in\NN} $, with exponential generating series $ h(t) $,
 satisfy the shifting property, if and only if
 \begin{equation}\label{series-h-exp}
  h'(t) = f'(\widehat{f}(t)) h(t) + \frac{g'(\widehat{f}(t))}{g(\widehat{f}(t))} \int_0^t h(u)\,\dd u \, ,
 \end{equation}
\end{theorem}
\begin{proof}
 First, denoting with $ D $ the derivative with respect to $ t $, we have
 $$
  \sum_{n\geq k} r_{n+1,k+1} \frac{t^n}{n!} =
  D \sum_{n\geq k} r_{n,k+1} \frac{t^n}{n!} =
  D\left[ g(t)\frac{f(t)^{k+1}}{(k+1)!}\right] =
  g'(t)\frac{f(t)^{k+1}}{(k+1)!} + g(t)f'(t)\frac{f(t)^k}{k!}\, .
 $$
 So, we have
 \begin{eqnarray*}
  \sum_{n\geq0} \left[\sum_{k=0}^n r_{n+1,k+1} h_n\right] \frac{t^n}{n!}
  & = & \sum_{k\geq0} h_n \left[\sum_{n\geq k}^n r_{n+1,k+1} \frac{t^n}{n!} \right] \\
  & = & g'(t)\sum_{k\geq0} h_n \frac{f(t)^{k+1}}{(k+1)!} + g(t)f'(t)\sum_{k\geq0} h_n \frac{f(t)^k}{k!} \\
  & = & g'(t)\sum_{k\geq1} h_{n-1} \frac{f(t)^k}{k!} + g(t)f'(t)h(f(t)) \\
  & = & g'(t)\int_0^{f(t)} h(u)\; \dd u + g(t)f'(t)h(f(t)) \, .
 \end{eqnarray*}
 Consequently, identity (\ref{shifting}) becomes
 $$ g(t)h'(f(t)) = g'(t) \int_0^{f(t)} h(u)\,\dd u + g(t) f'(t) h(f(t)) \, . $$
 Since $ g(t) $ is invertible with respect to multiplication
 and $ f (t) $ is invertible with respect to composition,
 this identity is equivalent to identity (\ref{series-h-exp}).
\end{proof}

\begin{theorem}
 Let $ R = [r_{n,k}]_{n,k\geq0} = (1,f(t)) $ be a Sheffer matrix
 and let $ (h_n)_{n\in\NN} $ be a normalized sequence with exponential generating series $ h(t) $.
 If $ R $ and $ (h_n)_{n\in\NN} $ satisfy the shifting property,
 then the Sheffer matrix $ R' = [r_{n+1,k+1}]_{n,k\geq0} = (f'(t),f(t)) $
 satisfies the shifting property with respect to the normalized sequence
 $ (H_n)_{n\in\NN} $ whose exponential generating series $ H(t) $ is given by
 \begin{equation}\label{series-h-H-exp}
  H(t) = 1 + h'(t) \int_0^t \frac{\dd u}{h(u)}\, ,
 \end{equation}
 or, equivalently, by
 \begin{equation}\label{series-h-H-exp-2}
  H'(t) = \frac{h''(t)}{h'(t)}\;H(t) - \frac{h(t)h''(t)-h'(t)^2}{h(t)h'(t)}\, .
 \end{equation}
\end{theorem}
\begin{proof}
 The series $ H(t) $ is defined by identity (\ref{series-h-exp}), where $ g(t) = f'(t) $.
 By identity (\ref{series-h-exp-inv-g1}), we have
 $$
  \widehat{f}'(t) = \frac{h(t)}{h'(t)}
  \qquad\text{and}\qquad
  \widehat{f}''(t) = \frac{h'(t)^2-h(t)h''(t)}{h'(t)^2}\, .
 $$
 Since
 $$
  f'(\widehat{f}(t)) = \frac{1}{\widehat{f}'(t)}
  \qquad\text{and}\qquad
  f''(\widehat{f}(t)) = -\frac{\widehat{f}''(t)}{\widehat{f}'(t)^3}\, ,
 $$
 we have
 $$
  \frac{g'(\widehat{f}(t))}{g(\widehat{f}(t))} =
  \frac{f''(\widehat{f}(t))}{f'(\widehat{f}(t))} =
  -\frac{\widehat{f}''(t))}{\widehat{f}'(t)^2} =
  -\frac{h'(t)^2-h(t)h''(t)}{h(t)^2}\, .
 $$
 So, the series $ H(t) $ is defined by the equation
 $$ H'(t) = \frac{h'(t)}{h(t)}\;H(t) - \frac{h'(t)^2-h(t)h''(t)}{h(t)^2}\int_0^t H(u)\,\dd u \, . $$

 Now, let $ w(t) = \int_0^t H(u)\,\dd u $. Then $ w'(t) = H(t) $, $ w''(t) = H'(t) $,
 and the above equation becomes
 $$ w''(t) - \frac{h'(t)}{h(t)}\;w'(t) + \frac{h'(t)^2-h(t)h''(t)}{h(t)^2}\;w(t) = 0 \, . $$
 It is easy to see that $ w(t) = h(t) $ is a particular solution of this equation.
 So, we can set $ w(t) = h(t)z(t) $. Then, we have
 \begin{align*}
  & w'(t) = h'(t)z(t) + h(t)z'(t) \\
  & w''(t) = h''(t)z(t) + 2h'(t)z'(t) + h(t)z''(t)
 \end{align*}
 and the previous equation becomes
 $$ h(t)z''(t)+h'(t)z'(t) = 0 $$
 or, equivalently, $ (h(t)z'(t))' = 0 $.
 Hence, we have $ h(t)z'(t) = K $, with $ K $ constant.
 Since $ h_0 = 1 $ and $ z_0 = 0 $, we have $ z_1 = 1 $.
 So $ K = 1 $, and $ h(t)z'(t) = 1 $, that is
 $$ z'(t) = \frac{1}{h(t)}\, . $$
 Since $ z_0 = 0 $, by integrating, we have
 $$ z(t) = \int_0^t \frac{1}{h(u)}\; \dd u \, , $$
 that is
 $$
  w(t) = h(t) \int_0^t \frac{1}{h(u)}\; \dd u
  \qquad\text{or}\qquad
  \int_0^t H(u)\,\dd u = h(t) \int_0^t \frac{1}{h(u)}\; \dd u \, ,
 $$
 By differentiating this last equation, we obtain identity (\ref{series-h-H-exp}).
 Finally, by differentiating (\ref{series-h-H-exp}), we obtain identity (\ref{series-h-H-exp-2}).
\end{proof}

\begin{examples}
 \item By (\ref{series-h-exp}), for the Sheffer matrix
  $$ R = \left[ { n+1 \brack k+1 } \right]_{n,k\geq0} = \left( \frac{1}{1-t}, \ln\frac{t}{1-t} \right), $$
  we have that the series $ h(t) $ satisfies the integro-differential equation
  $$ h'(t) = \ee^t \int_0^t h(u)\;\dd u + \ee^t\,h(t) \, . $$
  By differentiating, we obtain the differential equation
  $$ h''(t) - (1+\ee^t) h'(t) - \ee^t h(t) = 0 $$
  from which we have that the numbers $ h_n $ satisfy the recurrence
  $$ h_{n+2} = h_{n+1} + \sum_{k=0}^n { n \choose k } h_{k+1} + \sum_{k=0}^n { n \choose k } h_k\, . $$
  Let $ b(t) = \ee^{\ee^t-1} $ be the exponential generating series for the Bell numbers.
  Then, by equation (\ref{series-h-H-exp}) and Example \ref{Ex-Stirling1} on page \pageref{Ex-Stirling1}, we have
  $$ h(t) = 1 + b'(t) \int_0^t \frac{\dd u}{b(u)} = 1 + \ee^{\ee^t+t-1} \int_0^t \ee^{-(\ee^u-1)}\;\dd u\, . $$
  Since $$ \ee^{x(\ee^t-1)} = \sum_{n\geq0} S_n(x)\;\frac{t^n}{n!} $$
  is the generating series for the Stirling polynomials, we have the explicit expression
  $$ h_n = \delta_{n,0} + \sum_{k=1}^n { n \choose k } S_k(-1) b_{n-k+1} \, . $$
  These numbers form sequence \seqnum{A040027}.
  By equation (\ref{series-h-H-exp-2}), we also have
  $$ h'(t) = (1+\ee^t) h(t) - 1 \, , $$
  from which we obtain the following other recurrence
  $$ h_{n+1} = h_n + \sum_{k=0}^n { n \choose k } h_k - \delta_{n,0} \, . $$
  Finally, we have the shifting property
  \begin{equation}
   \sum_{k=0}^n { n+1 \brack k+1 } h_{k+1} = \sum_{k=0}^n { n+2 \brack k+2 } h_k \, .
  \end{equation}
  These sums form sequence \seqnum{A002793}.
 \item By (\ref{series-h-exp}), for the Sheffer matrix
  $$ R = \left[ { n+1 \brace k+1 } \right]_{n,k\geq0} = \left( \ee^t, \ee^t-1 \right), $$
  we have that the series $ h(t) $ satisfies the integro-differential equation
  $$ h'(t) = \int_0^t h(u)\;\dd u + (1+t) h(t) \, . $$
  By differentiating, we obtain the differential equation
  $$ h''(t) - (1+t) h'(t) - 2 h(t) = 0 $$
  from which we have that the numbers $ h_n $ satisfy the recurrence
  $$ h_{n+2} = h_{n+1} + (n+2) h_n $$
  with the initial values $ h_0 = h_1 =  1 $. These numbers form sequence \seqnum{A000932}.
  Moreover, by equation (\ref{series-h-H-exp}) and Example \ref{Ex-Stirling2} on page \pageref{Ex-Stirling2}, we have
  $$ h(t) = 1 + (1+t)\ee^{t+t^2/2} \int_0^t \ee^{-(u+u^2/2)}\;\dd u\, . $$

  Finally, we have the shifting identity
  \begin{equation}
   \sum_{k=0}^n { n+1 \brace k+1 } h_{k+1} = \sum_{k=0}^n { n+2 \brace k+2 } h_k \, .
  \end{equation}
 \item By (\ref{series-h-exp}), for the Sheffer matrix
  $$ R = \left[ { n+1 \lah k+1 } \right]_{n,k\geq0} = \left( \frac{1}{(1-t)^2}, \frac{1}{1-t} \right), $$
  we have that the series $ h(t) $ satisfies the integro-differential equation
  $$ h'(t) = 2(1+t)\int_0^t h(u)\;\dd u + (1+t)^2 h(t) \, . $$
  By differentiating, we obtain the differential equation
  $$ (1+t) h''(t) - (2+3t+3t^2+t^3) h'(t) - 3 (1+t)^2 h(t) = 0\, . $$
  From this equation, we have that the numbers $ h_n $ satisfy the recurrence
  $$ h_{n+4} + n h_{n+3} - 3(n+3) h_{n+2} - 3(n+3)(n+2) h_{n+1} - (n+3)(n+2)(n+1) h_n = 0 $$
  with the initial values $ h_0 = h_1 = 1 $, $ h_2 = 5 $, $ h_3 = 17 $.
  The first few values of this sequence are:
  1, 1, 5, 17, 69, 339, 1677, 9321, 55137, 343659, 2285289, 15910857, 116120781.
  This sequence does not appear in \cite{Sloane}.
  Moreover, by equation (\ref{series-h-H-exp}) and Example \ref{Ex-Lah} on page \pageref{Ex-Lah}, we have
  $$ h(t) = 1 + (1+t)^2\ee^{t+t^2+t^3/3} \int_0^t \ee^{-(u+u^2+u^3/3)}\;\dd u\, . $$

  Finally, we have the shifting identity
  \begin{equation}
   \sum_{k=0}^n { n+1 \lah k+1 } h_{k+1} = \sum_{k=0}^n { n+2 \lah k+2 } h_k \, .
  \end{equation}
 \item By (\ref{series-h-exp}), for the Sheffer matrix
  $$ R = \left[ { n \choose k } \frac{n!}{k!} \right]_{n,k\geq0} = \left( \frac{1}{1-t}, \frac{1}{1-t} \right), $$
  we have that the series $ h(t) $ satisfies the integro-differential equation
  $$ h'(t) = (1+t)^2 h(t) + (1+t)\int_0^t h(u)\;\dd u  \, . $$

  By differentiating, we obtain the differential equation
  $$ (1+t) h''(t) - (2+3t+3t^2+t^3) h'(t) - 2 (1+t)^2 h(t) = 0\, . $$
  From this equation, we have that the numbers $ h_n $ satisfy the recurrence
  $$ h_{n+4} + n h_{n+3} - (3n+8) h_{n+2} - (3n+7)(n+2) h_{n+1} - (n+2)^2(n+1) h_n = 0 $$
  with the initial conditions $ h_0 = h_1 = 1 $, $ h_2 = 4 $, $ h_3 = 13 $.
  The first few values are:
  1, 1, 4, 13, 50, 231, 1106, 5909, 33818, 205055, 1326226, 9014181, 64329034, 480660103.
  This sequence does not appear in \cite{Sloane}.
  In this case we have the shifting identity
  \begin{equation}
   \sum_{k=0}^n { n \choose k } \frac{n!}{k!}\; h_{k+1} = \sum_{k=0}^n { n+1 \choose k+1 } \frac{(n+1)!}{(k+1)!}\; h_k \, .
  \end{equation}
\end{examples}

\section{Shifting property for connection constants matrices}

The \emph{elementary} and the \emph{homogeneous symmetric functions} \cite{Macdonald,DAntonaMunarini}
are respectively defined by
$$
 { x_1,x_2,\ldots,x_n \choose k} = e_k(x_1,x_2,\ldots,x_n)
 = \sum_{1 \leq i_1 < \cdots < i_k \leq n} x_{i_1} \cdots x_{i_k}
$$
$$
 \Mchoose{x_1,x_2,\ldots,x_n}{k} = h_k(x_1,x_2,\ldots,x_n)
 = \sum_{i_1, \ldots, i_n \geq 0 \atop i_1+\cdots+i_n=k} x_1^{i_1} \cdots x_n^{i_n}
$$
and have generating series
\begin{align*}
 & \sum_{k\geq0} { x_1,x_2,\ldots,x_n \choose k} t^k = (1+x_1t)(1+x_2t)\cdots(1+x_nt) \\
 & \sum_{k\geq0} \Mchoose{x_1,x_2,\ldots,x_n}{k} t^k = \frac{1}{(1-x_1t)(1-x_2t)\cdots(1-x_nt)}\, .
\end{align*}

We proved \cite{DAntonaMunarini} that every connection constant
can be expressed in terms of these symmetric functions.
More precisely, given the zero sequence $ \zero = (0,0,\ldots) $, we proved that
\begin{align}
 & C_{n,k}^{(\rho,\zero)} = { r_1, \dots, r_n \choose n-k } (-1)^{n-k} \label{FirstClosedForm} \\
 & C_{n,k}^{(\zero,\sigma)} = \mchoose{ s_1, \dots, s_{k+1} }{n-k} \label{SecondClosedForm}
\end{align}
and that
\begin{equation}
 C_{n,k}^{(\rho,\sigma)} = \sum_{j=k}^n { r_1, \ldots, r_n \choose n-j } \mchoose{s_1,\ldots,s_{k+1}}{j-k}(-1)^{n-j} \, .
\end{equation}

Let us consider, now, the following generalization of the connection constants
$ C_{n,k}^{(\rho,\zero)} $ and $ C_{n,k}^{(\zero,\sigma)} $.
Given two sequences $ \sigma = (s_1,s_2,\ldots) $ and $ \tau = (t_1,t_2,\ldots) $,
we define the coefficients
\begin{align}
 & N_{n,k}^{(\sigma,\tau)} = { s_1, \dots, s_n \choose n-k } \frac{1}{t_1\cdots t_n}
   \qquad (t_k \ne 0 \, , \text{ for every } k \in \NN) \\
 & M_{n,k}^{(\sigma,\tau)} = \mchoose{s_1,\ldots,s_{k+1}}{n-k} t_1 t_2 \cdots t_k \, .
\end{align}
The $ M_{n,k}^{(\sigma,\tau)} $ are the \emph{generalized De Morgan numbers}\footnote{Notice that
this is a slight generalization of the De Morgan numbers considered in \cite{DAntonaMunarini}.}.
Since the homogeneous symmetric functions satisfy the recurrence
\begin{equation}\label{rec-homogeneousSF}
 \mchoose{x_1,x_2,\ldots,x_{n+1}}{k+1} =
 \mchoose{x_1,x_2,\ldots,x_n}{k+1} + \mchoose{x_1,x_2,\ldots,x_{n+1}}{\phantom{+1}k\phantom{+1}} x_{n+1} \, ,
\end{equation}
the generalized De Morgan numbers satisfy the recurrence
\begin{equation}\label{rec-Mnk}
 M_{n+1,k+1}^{(\sigma,\tau)} = t_{k+1} M_{n,k}^{(\sigma,\tau)} + s_{k+2} M_{n,k+1}^{(\sigma,\tau)} \, .
\end{equation}

Finally, we define the \emph{generalized continuants} $ K_n^{(\sigma,\tau)} $ by the recurrence
\begin{equation}\label{rec-continuant}
 K_{n+2}^{(\sigma,\tau)} = t_{n+2} K_{n+1}^{(\sigma,\tau)} + s_{n+2} K_n^{(\sigma,\tau)}
\end{equation}
with the initial conditions $ K_0^{(\sigma,\tau)} = 1 $ and $ K_1^{(\sigma,\tau)} = t_1 $,
\cite{GrahamKnuthPatashnik}.
For convenience, we also define $ K_{-1}^{(\sigma,\tau)} = 0 $.

Then, we have
\begin{theorem}
 The matrix $ R = \left[ M_{n,k}^{(\sigma,\tau)} \right]_{n,k\geq0} $
 and the sequence $ ( K_n^{(\sigma,\tau)} )_{n\geq0} $
 satisfy the shifting property, that is
 \begin{equation}\label{sum-Mnk-K}
  \sum_{k=0}^n M_{n,k}^{(\sigma,\tau)} K_{k+1}^{(\sigma,\tau)} =
  \sum_{k=0}^n M_{n+1,k+1}^{(\sigma,\tau)} K_k^{(\sigma,\tau)}\, .
 \end{equation}
\end{theorem}
\begin{proof}
 By the recurrences (\ref{rec-Mnk}) and (\ref{rec-continuant}), we have
 \begin{eqnarray*}
  \sum_{k=0}^n M_{n+1,k+1}^{(\sigma,\tau)} K_k^{(\sigma,\tau)}
  & = & \sum_{k=0}^n M_{n,k}^{(\sigma,\tau)} t_{k+1} K_k^{(\sigma,\tau)}
      + \sum_{k=0}^{n-1} M_{n,k+1}^{(\sigma,\tau)} s_{k+2} K_k^{(\sigma,\tau)} \\
  & = & \sum_{k=0}^n M_{n,k}^{(\sigma,\tau)} t_{k+1} K_k^{(\sigma,\tau)}
      + \sum_{k=1}^n M_{n,k}^{(\sigma,\tau)} s_{k+1} K_{k-1}^{(\sigma,\tau)} \\
  & = & \sum_{k=0}^n M_{n,k}^{(\sigma,\tau)} (t_{k+1}K_k^{(\sigma,\tau)}+s_{k+1}K_{k-1}^{(\sigma,\tau)}) \\
  & = & \sum_{k=0}^n M_{n,k}^{(\sigma,\tau)} K_{k+1}^{(\sigma,\tau)} \, .
 \end{eqnarray*}
\end{proof}

Using recurrences (\ref{rec-Mnk}) and (\ref{rec-continuant}),
we obtain the following particular instances of the sifting identity (\ref{sum-Mnk-K}).
In particular, we obtain the $q$-analogues of some identities obtained in the previous sections.
Recall that the $q$-numbers are defined as $ [n] := 1 + q + q^2 + \cdots + q^{n-1} $,
and that the $q$-factorials are defined as $ [n]! = [n][n-1]\cdots[2][1] $.

\begin{examples}
 \item For $ s_n = n-1 $ and $ t_n = n $, we obtain the ordinary \emph{De Morgan numbers} $ M_{n,k} $
  (\seqnum{A131689}) defined by the recurrence
  $$ M_{n+1,k+1} = (k+1) M_{n,k} + (k+1) M_{n,k+1} \, . $$
  Moreover, the numbers $ K_n^{(\sigma,\tau)} = h_n $ satisfy the recurrence
  $$ h_{n+2} = (n+2) h_{n+1} + (n+1) h_n $$
  with the initial conditions $ h_0 = h_1 = 1 $.
  They have exponential generating series
  $$ h(t) = \frac{\ee^{-t}}{(1-t)^2} $$
  and form sequence \seqnum{A000255}.
  Finally, we have the shifting identity
  \begin{equation}\label{identity-DeMorgan}
   \sum_{k=0}^n M_{n,k} h_{k+1} = \sum_{k=0}^n M_{n+1,k+1} h_k \, .
  \end{equation}
 \item For $ s_n = q^{n-1} $ and $ t_n = 1 $, we obtain the \emph{Gaussian coefficients}
  $$ \mchoose{1,q,q^2,\ldots,q^k}{n-k} = { n \choose k }_{\!\!q} = \frac{[n]!}{[k]![n-k]!} $$
  satisfying the recurrence
  $$ { n+1 \choose k+1 }_{\!\!q} = { n \choose k }_{\!\!q} + q^{k+1}{ n \choose k+1 }_{\!\!q} \, . $$
  Moreover, we have the \emph{$q$-Fibonacci numbers} $ K_n^{(\sigma,\tau)} = f_n(q) $,
  defined by the recurrence $ f_{n+2}(q) = f_{n+1}(q) + q^{n+1} f_n(q) $
  with the initial conditions $ f_0(q) = f_1(q) = 1 $, \cite{Carlitz,MunariniqFibo}.
  So, we have the shifting identity
  \begin{equation}\label{identity-Bin-Fibo-q}
   \sum_{k=0}^n { n \choose k }_{\!\!q} f_{k+1}(q) = \sum_{k=0}^n { n+1 \choose k+1 }_{\!\!q} f_k(q) \, .
  \end{equation}
  Clearly, for $ q = 1 $, we reobtain identity (\ref{identity-Bin-Fibo}).
 \item For $ s_n = [n-1] $ and $ t_n = 1 $,
  we have the \emph{$q$-Stirling numbers of the second kind} \cite{DAntonaMunarini}:
  $$ \mchoose{[0],[1],[2],\ldots,[k]}{n-k} = \mchoose{[1],[2],\ldots,[k]}{n-k} = { n \brace k }_{\!\!q} $$
  satisfying the recurrence
  $$ { n+1 \brace k+1 }_{\!\!q} = { n \brace k }_{\!\!q} + [k+1] { n \brace k+1 }_{\!\!q} \, . $$
  Moreover, we have the $q$-involution numbers $ K_n^{(\sigma,\tau)} = i_n(q) $
  satisfying the recurrence $ i_{n+2}(q) = i_{n+1}(q) + [n+1] i_n(q) $
  with the initial conditions $ i_0(q) = i_1(q) = 1 $.
  So, we have the shifting identity
  \begin{equation}
   \sum_{k=0}^n { n \brace k }_{\!\!q} i_{k+1}(q) = \sum_{k=0}^n { n+1 \brace k+1 }_{\!\!q} i_k(q) \, .
  \end{equation}
  Clearly, for $ s_n = n-1 $ (i.e., for $ q = 1 $), we reobtain identity (\ref{sum-Stirling2-inv}).
 \item For $ s_n = [n-1] $ and $ t_n = [n] $, we obtain the
  \emph{$q$-De Morgan numbers} $ M_{n,k}(q) = { n \brace k }_{\!q} [k]! $ satisfying the recurrence
  $$ M_{n+1,k+1}(q) = [k+1] M_{n,k}(q) + [k+1] M_{n,k+1}(q) \, . $$
  Moreover, the numbers $ K_n^{(\sigma,\tau)} = h_n(q) $ satisfy the recurrence
  $$ h_{n+2}(q) = [n+2] h_{n+1}(q) + [n+1] h_n(q) $$
  with the initial conditions $ h_0(q) = h_1(q) = 1 $.
  Finally, we have the shifting identity
  \begin{equation}\label{identity-DeMorgan-q}
   \sum_{k=0}^n M_{n,k}(q) h_{k+1}(q) = \sum_{k=0}^n M_{n+1,k+1}(q) h_k(q)
  \end{equation}
  which is a $q$-analogue of identity (\ref{identity-DeMorgan}).
\end{examples}

\begin{lemma}
 If $ t_k \ne 0 $ for every $ k \in \NN $, then the matrices
 $$
  M^{(\sigma,\tau)} = \left[ M_{n,k}^{(\sigma,\tau)} \right]_{n,k\geq0}
  \qquad\text{and}\qquad
  N^{(\sigma,\tau)} = \left[ N_{n,k}^{(\sigma,\tau)} \right]_{n,k\geq0}
 $$
 are invertible, and their inverses are
 \begin{align*}
  & \left[ M_{n,k}^{(\sigma,\tau)} \right]_{n,k\geq0}^{-1} =
    \left[ N_{n,k}^{(\sigma,\tau)} (-1)^{n-k} \right]_{n,k\geq0} \\
  & \left[ N_{n,k}^{(\sigma,\tau)} \right]_{n,k\geq0}^{-1} =
    \left[ M_{n,k}^{(\sigma,\tau)} (-1)^{n-k} \right]_{n,k\geq0} \, .
 \end{align*}
\end{lemma}
\begin{proof}
 Both $ M^{(\sigma,\tau)} $ and $ N^{(\sigma,\tau)} $
 are infinite lower triangular matrices with non-zero diagonal entries.
 So, they are invertible.
 Moreover, by relations (\ref{FirstClosedForm}) and (\ref{SecondClosedForm})
 and by property (\ref{id-inverse-CC-matrix}), we have at once the identities
 \begin{align*}
  & \left[ \mchoose{ s_1, \dots, s_{k+1} }{n-k} \right]_{n,k\geq0}^{-1} =
    \left[ { r_1, \dots, r_n \choose n-k } (-1)^{n-k} \right]_{n,k\geq0} \\
  & \left[ { r_1, \dots, r_n \choose n-k } \right]_{n,k\geq0}^{-1} =
    \left[ \mchoose{ s_1, \dots, s_{k+1} }{n-k} (-1)^{n-k} \right]_{n,k\geq0}
 \end{align*}
 which imply the assertion.
\end{proof}

\begin{theorem}\label{thm-shifting-N}
 The matrix $ R = [ N_{n,k}^{(\sigma,\tau)} ]_{n,k\geq0} $
 and the sequence $ ( h_n^{(\sigma,\tau)} )_{n,k\geq0} $ defined by the recurrence
 $$ h_{n+1}^{(\sigma,\tau)} = \sum_{k=0}^n s_{n,k}^{(\sigma,\tau)} h_k^{(\sigma,\tau)} $$
 with $ h_0^{(\sigma,\tau)} = 1 $, where
 \begin{equation}\label{id-snk-ConnConst}
  s_{n,k}^{(\sigma,\tau)} = \sum_{i=k}^n
   \mchoose{s_1,\ldots,s_{i+1}}{n-i} { s_1, \ldots, s_{i+1} \choose i-k } \frac{(-1)^{n-i}}{t_{i+1}} \, ,
 \end{equation}
 satisfy the shifting property.
\end{theorem}
\begin{proof}
 For the matrix $ R = [ N_{n,k}^{(\sigma,\tau)} ]_{n,k\geq0} $, we have
 $$
  R' = \left[ N_{n+1,k+1}^{(\sigma,\tau)} \right]_{n,k\geq0}
  \qquad\text{and}\qquad
  R^{-1} = \left[ M_{n,k}^{(\sigma,\tau)} (-1)^{n-k} \right]_{n,k\geq0} \, .
 $$
 Consequently, the entries of the matrix $ S = R^{-1}R' $ are
 $$ s_{n,k}^{(\sigma,\tau)} = \sum_{i=k}^n M_{n,i}^{(\sigma,\tau)} (-1)^{n-i} N_{i+1,k+1}^{(\sigma,\tau)} \, , $$
 which simplify in (\ref{id-snk-ConnConst}).
 Now, the theorem follows from Lemma \ref{lemma-main}.
\end{proof}

\begin{examples}
 \item By Theorem \ref{thm-shifting-N}, for $ s_n = q^{n-1} $ and $ t_n = 1 $, we have the $q$-coefficients
  $$
   \mchoose{1,q,\ldots,q^k}{n-k} = { n \choose k }_{\!\!q}
   \qquad\text{and}\qquad
   { 1,q,\ldots,q^{n-1} \choose n-k } = { n \choose k }_{\!\!q} q^{{ n-k \choose 2 }},
  $$
  and
  $$ s_{n,k}(q) = \sum_{i=k}^n { n \choose i }_{\!\!q} { i+1 \choose k+1 }_{\!\!q} q^{{ i-k \choose 2 }} (-1)^{n-i} \, . $$
  For the \emph{$q$-Fibonacci numbers} defined by the recurrence
  $$ F_{n+1}(q) = \sum_{k=0}^n s_{n,k}(q) F_k(q) $$
  with the initial condition $ F_0(q) = 1 $, we have the shifting property
  \begin{equation}
   \sum_{k=0}^n { n \choose k }_{\!\!q} q^{{ n-k \choose 2 }} F_{k+1}(q)
   = \sum_{k=0}^n { n+1 \choose k+1 }_{\!\!q} q^{{ n-k \choose 2 }} F_k(q)
  \end{equation}
  which is another $q$-analogue of identity (\ref{identity-Bin-Fibo}).
 \item By Theorem \ref{thm-shifting-N}, for $ s_n = [n-1] $ and $ t_n = 1 $, we have the $q$-coefficients
  $$
   \mchoose{[1],\ldots,[k]}{n-k} = { n \brace k }_{\!\!q}
   \qquad\text{and}\qquad
   { [1],\ldots,[n] \choose n-k } = { n \brack k }_{\!\!q},
  $$
  and
  $$ s_{n,k}(q) = \sum_{i=k}^n { n \brace i }_{\!\!q} { i+1 \brack k+1 }_{\!\!q} (-1)^{n-i} \, . $$
  For the \emph{$q$-Bell numbers} defined by the recurrence
  $$ B_{n+1}(q) = \sum_{k=0}^n s_{n,k}(q) B_k(q) $$
  with the initial condition $ B_0(q) = 1 $, we have the shifting property
  \begin{equation}
   \sum_{k=0}^n { n \brack k }_{\!\!q} B_{k+1}(q) = \sum_{k=0}^n { n+1 \brack k+1 }_{\!\!q} B_k(q)
  \end{equation}
  which is a $q$-analogue of identity (\ref{sum-Stirling1-Bell}).
  Clearly, identity (\ref{sum-Stirling1-Bell}) can also be reobtained for $ s_n = n-1 $ and $ t_n = 1 $.
\end{examples}

\begin{thebibliography}{99}
 \bibitem{Carlitz}
  L. Carlitz,
  Fibonacci notes--3: $q$-Fibonacci numbers,
  \emph{Fibonacci Quart.} \textbf{12} (1974), 317--322.
 \bibitem{Comtet}
  L. Comtet,
  \emph{Advanced Combinatorics},
  Reidel, 1974.
 \bibitem{DamianiDAntonaNaldi}
  E. Damiani, O. D'Antona, and G. Naldi,
  On the connection constants,
  \emph{Studies in Appl. Math.} \textbf{85} (1991), 289--302.
 \bibitem{DAntonaMunarini}
  O. M. D'Antona and E. Munarini,
  A combinatorial interpretation of the connection constants for persistent sequences of polynomials,
  \emph{European J. Combin.} \textbf{26} (2005), 1105--1118.
 \bibitem{GrahamKnuthPatashnik}
  R. L. Graham, D. E. Knuth, and O. Patashnik,
  \emph{Concrete Mathematics},
  Addison-Wesley, 1989.
 \bibitem{Macdonald}
  I. G. Macdonald,
  \emph{Symmetric Functions and Hall Polynomials}, second ed.,
  Oxford University Press, 1995.
 \bibitem{MunariniGenFibo}
  E. Munarini,
  A combinatorial interpretation of the generalized Fibonacci numbers,
  \emph{Adv. in Appl. Math.} \textbf{19} (1998), 306--318.
 \bibitem{MunariniqFibo}
  E. Munarini,
  Generalized $q$-Fibonacci numbers,
  \emph{Fibonacci Quart.} \textbf{43} (2005), 234--242.
 \bibitem{Roman}
  S. Roman,
  \emph{The Umbral Calculus},
  Pure and Applied Mathematics Series, Vol.~111, Academic Press, 1984.
 \bibitem{RomanRota}
  S. M. Roman and G.-C. Rota,
  The umbral calculus,
  \emph{Adv. in Math.} \textbf{27} (1978), 95--188.
 \bibitem{Sloane}
  N. J. A. Sloane,
  \emph{The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}.
 \bibitem{ShapiroGetuWoanWoodson}
  L. W. Shapiro, S. Getu, W. J. Woan, and L. C. Woodson,
  The Riordan group,
  \emph{Discrete Appl. Math.} \textbf{34} (1991), 229--239.
 \bibitem{ShapiroSurvey}
  L. W. Shapiro,
  A survey of the Riordan group,
  Talk at a meeting of the American Mathematical Society,
  Richmond, Virginia, 1994.
 \bibitem{Shapiro}
  L. W. Shapiro,
  Bijections and the Riordan group,
  \emph{Theoret. Comput. Sci.} \textbf{307} (2003), 403--413.
 \bibitem{Sprugnoli}
  R. Sprugnoli,
  Riordan arrays and combinatorial sums,
  \emph{Discrete Math.} \textbf{132} (1994), 267--290.
 \bibitem{WangWang}
  W. Wang and T. Wang,
  Generalized Riordan arrays,
  \emph{Discrete Math.} \textbf{308} (2008), 6466--6500.
\end{thebibliography}

\bigskip

\hrule
\bigskip
\noindent
\emph{2000 Mathematics Subject Classification}: Primary: 05A19, Secondary: 05A15, 05A10, 11C08. \\
\emph{Keywords}: combinatorial sum, Riordan matrix, Sheffer matrix, connection constant,
generating series, differential equation.
\bigskip
\hrule
\bigskip
\noindent
(Concerned with sequences
\seqnum{A000045},
\seqnum{A000073},
\seqnum{A000078},
\seqnum{A000085},
\seqnum{A000108},
\seqnum{A000110},
\seqnum{A000255},
\seqnum{A000262},
\seqnum{A000932},
\seqnum{A000984},
\seqnum{A001591},
\seqnum{A001592},
\seqnum{A001764},
\seqnum{A002720},
\seqnum{A002793},
\seqnum{A004319},
\seqnum{A006629},
\seqnum{A006630},
\seqnum{A006631},
\seqnum{A007318},
\seqnum{A007405},
\seqnum{A008277},
\seqnum{A008287},
\seqnum{A025174},
\seqnum{A027907},
\seqnum{A035343},
\seqnum{A040027},
\seqnum{A049425},
\seqnum{A063260},
\seqnum{A063265},
\seqnum{A066178},
\seqnum{A079262},
\seqnum{A102594},
\seqnum{A102893},
\seqnum{A105287},
\seqnum{A122189},
\seqnum{A131689},
\seqnum{A132393},
\seqnum{A171890},
\seqnum{A213651},
\seqnum{A213652},
\seqnum{A230547},
\seqnum{A233657}, and
\seqnum{A236194}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  September 28 2016;
revised versions received  October 3 2016; July 6 2017; August 24 2017; August 25 2017.
Published in {\it Journal of Integer Sequences}, August 31 2017.

\bigskip
\hrule
\bigskip

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


\end{document}