chap6.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

For example, eleven permutations of $\{1,2,3,4\}$ have two ascents:
\begindisplay\advance\abovedisplayskip-2pt\advance\belowdisplayskip-2pt%
\openup-2pt
&1324\,,\quad 
1423\,,\quad 
2314\,,\quad
2413\,,\quad 
3412\,;\cr
&1243\,,\quad 
1342\,,\quad 
2341\,;\qquad 
2134\,,\quad
3124\,,\quad 
4123\,.
\enddisplay
(The first row lists the permutations with $\pi_1<\pi_2>\pi_3<\pi_4$; the
second row lists those with $\pi_1<\pi_2<\pi_3>\pi_4$ and
$\pi_1>\pi_2<\pi_3<\pi_4$.) Hence ${4\euler2}=11$. Table~|euler-triangle|
lists the smallest Eulerian numbers; notice that the trademark sequence
is $1$,~$11$,~$11$,~$1$ this time. There can be at most $n-1$~ascents,
when $n>0$, so we have ${n\euler n}=\[n=0]$ on the diagonal of the triangle.

\topinsert
\setbox0=\hbox{$\biggr>$}
\def\\#1{\displaystyle{n\euler#1}\kern-\wd0}
\table Euler's triangle.\tabref|euler-triangle|
\offinterlineskip
\halign to\hsize{\strut$\hfil#$\quad&\vrule#\kern-5pt\tabskip10pt plus 100pt&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$\tabskip\wd0\cr
\omit&height 3pt\cr
n &&\\0&\\1&\\2&\\3&\\4&\\5&\\6&\\7&\\8&\\9\cr
\omit&height 2pt\cr
\noalign{\hrule width\hsize}
\omit&height 3pt\cr
0 && 1 \cr
1 && 1 & 0 \cr
2 && 1 & 1 & 0 \cr
3 && 1 & 4 & 1 & 0 \cr
4 && 1 & 11 & 11 & 1 & 0 \cr
5 && 1 & 26 & 66 & 26 & 1 & 0 \cr
6 && 1 & 57 & 302 & 302 & 57 & 1 & 0 \cr
7 && 1 & 120 & 1191 & 2416 & 1191 & 120 & 1 & 0\kern-.5em \cr
8 && 1 & 247 & 4293 & 15619 & 15619 & 4293 & 247 & 1\kern-.5em & 0 \cr
9 && 1 & 502 & 14608 & 88234 & 156190 & 88234 & 14608 & \kern.5em502\kern-.5em
 & \ 1 & 0 \ \cr
\omit&height 2pt\cr}
\hrule width\hsize height.5pt
\kern4pt
\endinsert

"Euler's triangle", like Pascal's, is symmetric between left and right.
But in this case the symmetry law is slightly different:
\begindisplay
{n\euler k}={n\euler n-1-k}\,,\qquad\hbox{integer $n>0$};
\eqno\eqref|eulerian-sym|
\enddisplay
The permutation $\pi_1\pi_2\ldots\pi_n$ has~$n-1-k$ ascents if and only if
its ``reflection'' $\pi_n\ldots\pi_2\pi_1$ has $k$ ascents.

Let's try to find a recurrence for $n\euler k$. Each permutation
$\rho=\rho_1\ldots\rho_{n-1}$ of $\{1,\ldots,n-1\}$ leads to $n$ permutations
of $\{1,2,\ldots,n\}$ if we insert the new element~$n$ in all possible ways.
Suppose we put $n$ in position~$j$, obtaining the permutation
$\pi=\rho_1\ldots\rho_{j-1}\,n\,\rho_j\ldots\rho_{n-1}$. The number of
ascents in $\pi$ is the same as the number in $\rho$,
if $j=1$ or if $\rho_{j-1}<\rho_j$; it's
one greater than the number in~$\rho$, if
$\rho_{j-1}>\rho_j$ or if $j=n$.
Therefore $\pi$ has $k$ ascents
in a total of $(k+1){n-1\euler k}$ ways from permutations $\rho$ that
have $k$~ascents, plus a total of $\bigl((n-2)-(k-1)+1\bigr){n-1\euler k-1}$ ways
from permutations $\rho$ that have $k-1$ ascents. The desired recurrence is
\begindisplay
{n\euler k}=(k+1){n-1\euler k}+(n-k){n-1\euler k-1}\,,\quad
\hbox{integer $n>0$}.
\eqno\eqref|eulerian-rec|
\enddisplay
Once again we start the recurrence off by setting
\begindisplay \postdisplaypenalty=10000
{0\euler k}=\[k=0]\,,\qquad\hbox{integer $k$},
\eqno
\enddisplay
and we will assume that ${n\euler k}=0$ when $k<0$.

"Eulerian numbers" are useful primarily because they provide an unusual
connection between ordinary powers and consecutive binomial coefficients:
\begindisplay
x^n=\sum_k{n\euler k}{x+k\choose n}\,,\qquad\hbox{integer $n\ge0$}.
\eqno\eqref|expand-ord-to-consec|
\enddisplay
(This is called ``"Worpitzky"'s identity'' [|worpitzky|].)
\g Western scholars have recently learned of a significant Chinese
\looseness=-1
book by "Li" Shan-Lan~[|li-shan-lan|; |martzloff|, pages\kern-.5em\null\par
320--325],
published in 1867, which contains
the first known appearance of formula~\eq(|expand-ord-to-consec|).\g
For example, we have
\begindisplay \openup5pt \tightplus
x^2&={x\choose2}+{x+1\choose2}\,,\cr
x^3&={x\choose3}+4{x+1\choose3}+{x+2\choose3}\,,\cr
x^4&={x\choose4}+11{x+1\choose4}+11{x+2\choose4}+{x+3\choose4}\,,\cr
\enddisplay
and so on. It's easy to prove \eq(|expand-ord-to-consec|) by
induction (exercise |prove-eulerian-expansion|).

Incidentally, \thiseq\ gives us yet another way to obtain the sum of the
"!sum of consecutive squares"
first~$n$~squares: We have $k^2={2\euler0}{k\choose2}+{2\euler1}{k+1\choose2}
 ={k\choose2}+{k+1\choose2}$, hence
\begindisplay \let\displaystyle=\textstyle \openup7pt
1^2+2^2+\cdots+n^2&=\bigl({1\choose2}+{\2\choose2}+\cdots+{n\choose2}\bigr)
+\bigl({\2\choose2}+{3\choose2}+\cdots+{n+1\choose2}\bigr)\cr
&={n+1\choose3}+{n+\2\choose3}={1\over6}(n+1)n\bigl((n-1)+(n+2)\bigr)\,.
\enddisplay

The Eulerian recurrence \eq(|eulerian-rec|) is a bit more complicated than
the Stirling recurrences \eq(|stirl2-rec|) and \eq(|stirl1-rec|), so
we don't expect the numbers $n\euler k$ to satisfy as many simple identities.
Still, there are a few:
\begindisplay \openup5pt
{n\euler m}&=\sum_{k=0}^m{n+1\choose k}(m+1-k)^n(-1)^k\,;
\eqno\eqref|eulerian-expansion|\cr
m!\,{n\brace m}&=\sum_k{n\euler k}{k\choose n-m}\,;
\eqno\eqref|expand-stirling-to-eulerian|\cr
{n\euler m}&=\sum_k{n\brace k}{n-k\choose m}(-1)^{n-k-m}\,k!\,.
\eqno\eqref|expand-eulerian-to-stirling|\cr
\enddisplay
If we multiply \eq(|expand-stirling-to-eulerian|) by $z^{n-m}$ and sum on~$m$,
we get $\sum_m{n\brace m}m!\,z^{n-m}
=\sum_k{n\euler k}(z+1)^k$.
Replacing $z$ by $z-1$ and equating coefficients of $z^k$ gives
\eq(|expand-eulerian-to-stirling|). Thus the last two of these identities
are essentially equivalent. The first identity,
\eq(|eulerian-expansion|), gives us special values
when $m$ is small:
\begindisplay \postdisplaypenalty=-150 \tightplus
{n\euler0}=1\,;\quad{n\euler1}=2^n-n-1\,;
\quad{n\euler2}=3^n-(n+1)2^n+{n+1\choose2}\,.
\enddisplay

\topinsert
\setbox0=\hbox{$\biggr>\mskip-7mu\biggr>$}
\def\\#1{\displaystyle{\Euler n#1}\kern-\wd0}
\table Second-order Eulerian triangle.\tabref|euler2-triangle|
\offinterlineskip
\halign to\hsize{\strut$\hfil#$\quad&\vrule#\kern-5pt\tabskip10pt plus 100pt&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$\tabskip\wd0\cr
\omit&height 3pt\cr
n &&\\0&\ \\1&\\2&\\3&\\4&\\5&\kern-.3em\\6\kern.3em&\\7&\ \\8\cr
\omit&height 2pt\cr
\noalign{\hrule width\hsize}
\omit&height 3pt\cr
0 && 1 \cr
1 && 1 & 0 \cr
2 && 1 & 2 & 0 \cr
3 && 1 & 8 & 6 & 0 \cr
4 && 1 & 22 & 58 & 24 & 0 \cr
5 && 1 & 52 & 328 & 444 & 120 & 0 \cr
6 && 1 & 114 & 1452 & 4400 & 3708 & 720 & 0 \cr
7 && 1 & 240 & 5610 & 32120 & 58140 & 33984 & 5040 & 0\kern-1em \cr
8 && 1 & 494 & \!19950 & \!195800 & \!644020 & \!785304 & \!341136 &
 \!40320\kern-1em & 0 \cr
\omit&height 2pt\cr}
\hrule width\hsize height.5pt
\kern4pt
\endinsert

We needn't dwell further on Eulerian numbers here; it's usually sufficient
simply to know that they exist, and to have a list of basic identities
to fall back on when the need arises. However, before we leave this topic,
we should take note of yet another triangular pattern of coefficients,
shown in Table~|euler2-triangle|.
We call these ``second-order Eulerian numbers'' $\Euler nk$, because
"!Eulerian numbers, second order" \tabref|nn:euler2|%
they satisfy a recurrence similar to \eq(|eulerian-rec|) but with
$n$ replaced by $2n-1$ in one place:
\begindisplay
\Euler nk=(k+1)\Euler{n-1}k+(2n-1-k)\Euler{n-1}{k-1}\,.
\eqno\eqref|eulerian2-rec|
\enddisplay
These numbers have a curious combinatorial interpretation, first noticed
by "Gessel" and "Stanley"~[|gessel-stanley|]:
If we form permutations of the multiset $\{1,1,\allowbreak
2,2,\allowbreak\ldots,n,n\}$ with
the special property that all numbers between the two occurrences of~$m$
are greater than~$m$, for $1\le m\le n$, then $\Euler nk$ is the
number of such permutations that have $k$ ascents.
For example, there are eight suitable
single-ascent permutations of $\{1,1,2,2,3,3\}$:
\begindisplay
113322,\;
133221,\;
221331,\;
221133,\;
223311,\;
233211,\;
331122,\;
331221.
\enddisplay
Thus $\Euler31=8$. The multiset $\{1,1,2,2,\ldots,n,n\}$ has a total of
\begindisplay
\sum_k\Euler nk=(2n-1)(2n-3)\ldots(1)={(2n)\_n\over2^n}
\eqno
\enddisplay
suitable permutations,
"!product of odd numbers"
because the two appearances of $n$ must be adjacent and there are $2n-1$
places to insert them within a permutation for $n-1$.
For example, when $n=3$ the permutation $1221$ has five insertion points,
yielding $331221$, $133221$, $123321$, $122331$, and $122133$.
Recurrence \eq(|eulerian2-rec|) can be
proved by extending the argument we used for ordinary Eulerian numbers.

Second-order Eulerian numbers are important chiefly because of their connection
with Stirling numbers~[|ginsburg|]: We have, by induction on~$n$,
\begindisplay \openup4pt
{x\brace x-n}&=\sum_k\Euler nk{x+n-1-k\choose2n}\,,
}\hfill{&\qquad\hbox{integer $n\ge0$;}\eqno\eqref|gen-st2|\cr
{x\brack@x-n@}&=\sum_k\Euler nk{x+k\choose2n}\,,
}\hfill{&\qquad\hbox{integer $n\ge0$.}\eqno\eqref|gen-st1|\cr
\enddisplay
For example,
\begindisplay \openup4pt
&{x\brace x{-}1}={x\choose2}\,,}\hfill{\qquad
&{x\brack x{-}1}={x\choose2}\,;\cr
&{x\brace x{-}2}={x{+}1\choose4}+2{x\choose4}\,,}\hfill{\qquad
&{x\brack x{-}2}={x\choose4}+2{x{+}1\choose4}\,;\cr
&{x\brace x{-}3}={x{+2}\choose6}+8{x{+}1\choose6}+6{x\choose6}\,,}\hidewidth{\cr
&&{x\brack x{-}3}={x\choose6}+8{x{+}1\choose6}+6{x{+}2\choose6}\,.
}\hidewidth{\cr
\enddisplay
(We already encountered the case $n=1$ in \eq(|stirl-nn-1|).)
These identities hold whenever $x$ is an integer and $n$ is a nonnegative
integer. Since the right-hand sides are polynomials in~$x$, we can use
\eq(|gen-st2|) and \eq(|gen-st1|)
to define Stirling numbers $x\brace x-n$ and $x\brack x-n$
"!Stirling numbers, generalized"
for arbitrary real (or complex) values of~$x$.

\smallskip
If $n>0$, these polynomials $x\brace x-n$ and $x\brack x-n$ are zero when
$x=0$, $x=1$, \dots, and~$x=n$; therefore they are divisible by
$(x-0)$, $(x-1)$, \dots, and~$(x-n)$. It's interesting to look at what's left
after these known factors are divided out. We define
"!Bernoulli numbers, generalized, \string\see Stirling polynomials"
the {\it"Stirling polynomials"\/} $\sigma_n(x)$ by the rule
\begindisplay
\sigma_n(x)={x\brack x-n}\,\big/\,\bigl(x(x-1)\ldots(x-n)\bigr)\,.
\eqno\eqref|stirl-poly-def|
\enddisplay
(The degree of $\sigma_n(x)$ is $n-1$.) The first few cases are
\g\hbadness=2000\vskip18pt So $1/x$ is a \hbox{polynomial}?
\medskip(Sorry about that.)\g
\begindisplay \openup1pt
\sigma_0(x)&=1/x\,;\cr
\sigma_1(x)&=1/2\,;\cr
\sigma_2(x)&=(3x-1)/24\,;\cr
\sigma_3(x)&=(x^2-x)/48\,;\cr
\sigma_4(x)&=(15x^3-30x^2+5x+2)/5760\,.\cr
\enddisplay
They can be computed via the second-order Eulerian numbers; for example,
\begindisplay
\sigma_3(x)&=\bigl((x{-}4)(x{-}5)+8(x{-}4)(x{+}1)+6(x{+}2)(x{+}1)\bigr)/6!\,.
\enddisplay

\topinsert
\table Stirling convolution formulas.\tabref|stirling-convolutions|
\begindisplay\abovedisplayskip=-2pt \belowdisplayskip=5pt \openup2pt%
 \advance\baselineskip0pt plus .5pt  \advance\lineskip0pt plus .5pt
rs\sum_{k=0}^n\sigma_k(r+tk)\,\sigma_{n-k}(s+t(n-k))&=(r+s)@\sigma_n(r+s+tn)
 \eqno\eqref|st-conv-2a|\cr
s\sum_{k=0}^n \,k@\sigma_k(r+tk)\,\sigma_{n-k}(s+t(n-k))&=n@\sigma_n(r+s+tn)
 \eqno\cr
\noalign{\vskip1pt}
{n\brace m}\hskip4em&\hskip-4em
 =(-1)^{n-m+1}{n!\over(m-1)!}\sigma_{n-m}(-m)\eqno\eqref|s2-to-sigma|\cr
\noalign{\vskip3pt}
{n\brack@m@}\hskip4em&\hskip-4em
 ={n!\over(m-1)!}\sigma_{n-m}(n)\eqno\eqref|s1-to-sigma|\cr
\enddisplay
\kern2pt
\hrule width\hsize height.5pt
\kern4pt
\endinsert

It turns out that these polynomials satisfy two very pretty identities:
\begindisplay
\left(ze^z\over e^z-1\right)^{\!x}&=x\sum_{n\ge0}\sigma_n(x)\,z^n\,;
\eqno\eqref|stirl-poly-gf|\cr
\left({1\over z}\ln{1\over1-z}\right)^{\!x}&=x\sum_{n\ge0}\sigma_n(x+n)\,z^n\,.
\eqno\cr
\enddisplay
And in general, if $\Sscr_t(z)$ is the power series that satisfies
\begindisplay
\ln\bigl(1-z@\Sscr_t(z)^{t-1}\bigr)=-z@\Sscr_t(z)^t\,,
\eqno\eqref|t-series-stirl|
\enddisplay
then