# 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...

#### Recommend Documents

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

5.3 TRICKS OF THE TRADE 187 Identity (5.35) has an amusing corollary. Let r = in, and take the sum over all integers k.

5.3 TRICKS OF THE TRADE 191 is a polynomial in k of degree n, with leading coefficient (-1 )“s”/n!. Therefore (5.43) is

198 BINOMIAL COEFFICIENTS Generating functions give us powerful ways to discover and/or prove identities. For example,

5.5 HYPERGEOMETRIC FUNCTIONS 209 looks like in hypergeometric notation. We need to write the sum as an infinite series

212 BINOMIAL COEFFICIENTS into to but disappear from t,he term ratio. Using such tricks we can predict without further

5.6 HYPERGEOMETRIC TRANSFORMATIONS 217 to the hypergeometric (~)(A2 l-1)) The hypergeometric database should really

5.6 HYPERGEOMETRIC TRANSFORMATIONS 219 Notice that when z = 1 this reduces to Vandermonde’s convolution, (5.93). Dif

5.7 PARTIAL HYPERGEOMETRIC SUMS 229 We also computed 1 kzk 6k in Chapter 2. This summand is zero when k = 0, so we get

242 BINOMIAL COEFFICIENTS Research problems 95 Let q(n) be the smallest odd prime factor of the middle binomial coeffic

252 SPECIAL NUMBERS We can remember when to stick the (-l)“pk factor into a formula like (6.12) because there’s a nat

6.3 HARMONIC NUMBERS 261 Metric units make this problem more scientific. the finish; so W is now 2 cm from the starti

6.5 BERNOULLI NUMBERS = o~,~(m~l)k~,(~~~k)Bj--r+(m+l)A = o~m~(m~l)o~~~i(m~~~k)~~+~~+~~A .. [m-k=Ol+(m+l)A = nm” + (

6.7 CONTINUANTS 293 Well, y must be irrational, because of a little-known Einsteinian assertion: “God does not throw hu

6 EXERCISES 301 53 Find a closed form for tkm,O (E)-‘(-l)kHk, when 0 6 m < n. Hint: Exercise 5.42 has the sum without t

6 EXERCISES 305 89 Develop a general theory of the solutions to the two-parameter recurrence = (an+ @+y) +(a’n+/3’k+y’)

7.1 DOMINO THEORY AND CHANGE 313 for some k and m; hence 2k + k + 3m = 6. In other words, k + m = 2. If we use no verti

7.1 DOMINO THEORY AND CHANGE 315 How many pennies are there, really? If n is greater than, say, 10”) I bet that P, = 0

324 GENERATING FUNCTIONS Fortunately the problem is easy to fix, since we can add [n = 11 to the right; this adds 1 whe

7.3 SOLVING RECURRENCES 325 also has nice coefficients, + . . . + al P? * (7.27) We will show that every rational f

7.5 Beta use it’s so CONVOLUTIONS This seems almost too good to be true. But it checks, at least when n = 2: harmonic

344 GENERATING FUNCTIONS Step 3 is also easy. We solve for C(z) by the quadratic formula: C(z) = 1*di-=G 22 But shou

348 GENERATING FUNCTIONS Notice that these are not easy questions. In the ordinary Catalan case (m = 2), we solved (7.6

7.6 EXPONENTIAL GENERATING FUNCTIONS 353 And the latter sumI is a geometric progression, so there’s a closed form S(z,n