271 pdfsam Graham, Knuth, Patashnik Concrete Mathematics

6.2 EULERIAN NUMBERS 257 Second-order Eulerian numbers are important chiefly because of their connection with Stirling...

0 downloads 99 Views 26KB Size
6.2 EULERIAN

NUMBERS 257

Second-order Eulerian numbers are important chiefly because of their connection with Stirling numbers [119]: We have, by induction on n, {x"n}

=

&(($~+n~lyk).

integern30;

[x”n] = g(~))(“~k) 7

integer n 3 0.

(6.43)

(6.44)

For example, {Zl}

= (1))

[x:1]

=

(1);

{z2} = (7’) +2(g) [x:2] = (:)+2(y); (,r,} = (“:‘) +8(y) +6(d) [xx3] = (1) +8(x;‘) +6(x12). (We already encountered the case n = 1 in (6.7).) 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 (6.43) and (6.44) to define Stirling numbers { .“,} and [,Tn] for arbitrary real (or complex) values of x. If n > 0, these polynomials { .“,} and [,“J are zero when x = 0, x = 1, . . . , and x = n; therefore they are divisible by (x-O), (x-l), . . . , and (x-n). It’s interesting to look at what’s left after these known factors are divided out. We define the Stirling polynomials o,(x) by the rule

[1

&l(x) = .", /(X(X-l)...(X-TX)).

(6.45)

(The degree of o,(x) is n - 1.) The first few cases are So l/x isa

q)(x) = l/x;

polynomial?

CT,(x)

(Sorry about that.)

02(x) = (3x-1)/24;

= l/2;

q(x) = (x2 -x)/48; Q(X) = (15x3 -30x2+5x+2)/5760. They can be computed via the second-order Eulerian numbers; for example, CQ(X) = ((~-4)(x-5)+8(x+1)(x-4)

+6(x+2)(x+1))/&