index.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

cyclotomic polynomials, 149
\medskip
$D$, \see derivative operator
Dating Game, 506
David, Florence Nightingale, 602, 609
Davis, Philip Jacob, 609
Davison, John Leslie, 307, 604, 609, 635
de Branges, Louis, 617
de Bruijn, Nicolaas Govert, 444, 447, 500, 609, 635, 636
\sub cycle, 500
de Finetti, Bruno, 24, 613
de Lagny, Thomas Fantet, 304, 621
de Moivre, Abraham, 297, 481, 609
Dedekind, Julius Wilhelm Richard, 136--137, 609
definite sums, analogous to definite integrals, 49--50
deg, 226, 232
degenerate hypergeometric series, 209--210, 216, 222, 247
derangements, 194--196
\sub generating function, 199--200
derivative operator, 47--49
\sub converting between $D$ and $\Delta$, 470--471
\sub converting between $D$ and $\vartheta$, 310
\sub with generating functions, 33, 333, 364--365
\sub with hypergeometric series, 219--221
descents, \see ascents
dgf: Dirichlet generating function, 370
dice, 381--384
\sub fair, 382, 417, 429
\sub loaded, 382, 429, 431
\sub nonstandard, 431
\sub pgf for, 399--400
\sub probability of doubles, 427
\sub supposedly fair, 392
Dickson, Leonard Eugene, 510, 609
Dieudonn\'e, Jean Alexandre, 523
difference operator, 47--55, 241
\sub converting between $D$ and $\Delta$, 470--471
\sub $n$th difference, 187--192, 280--281
\sub $n$th difference of product, 571
differentiably finite power series, 374, 380
differential operators, \see derivative operator, theta operator
difficulty measure for summation, 181
Dijkstra, Edsger Wybe, 173, 609, 635
dimers and dimes, 320, \see dominoes and change
diphages, 434, 438
Dirichlet, Peter Gustav Lejeune, 370, 610, 633
\sub box principle, 95, 130, 512
\sub generating functions, 370--371, 373, 432, 451
\sub probability generating functions, 432
discrepancy, 88--89, 97
\sub and continued fractions, 319, 492, 602
\sub asymptotics of, 492, 495
discrete probability, 381--438
\sub defined, 381
disease, 333
distribution,
\sub of fractional parts, 87
\sub of primes, 111
\sub of probabilities, \see probability distributions
\sub of things into groups, 83--85
distributive law, 30, 35, 60, 64
\sub for gcd and lcm, 145
\sub for mod, 83
divergent sums, 57, 60
\sub considered useful, 346--348, 451
\sub illegitimate, 504, 532
divide and conquer, 79
divides exactly,  146
\sub in binomial coefficients, 245
\sub in factorials, 112--114, 146
divisibility, 102--105
\sub by~$3$, 147
\sub of polynomials, 225
Dixon, Alfred Cardew, 610, 634
\sub formula, 214
DNA, Martian, 377
Dodgson, Charles Lutwidge, \see Carroll
domino tilings, 320--327, 371, 379
\sub ordered pairs of, 375
Dorothy Gale, 581
double generating functions, \see super generating functions
double sums, 34--41, 246, 249
\sub considered useful, 46, 183--185
\sub faulty use of, 63, 65
\sub infinite, 61
\sub over divisors, 105
\sub telescoping, 255
doubloons, 436--437
doubly exponential recurrences, 97, 100, 101,~109
doubly infinite sums, 59, 98, 482--483
Dougall, John, 171, 610
downward generalization, 2, 95, 320--321
Doyle, Sir Arthur Conan, 162, 228--229, 405, 610
drones, 291
Drysdale, Robert Lewis (Scot), III, 632
du Bois-Reymond, Paul David Gustav, 440, 610, 617
duality, 69
\sub between $n\choose k$ and $1/n{n-1\choose k}$, 530
\sub between factorial and Gamma functions, 211
\sub between floors and ceilings, 68--69, 96
\sub between gcd and lcm, 107
\sub between rising and falling powers, 63
\sub between Stirling numbers of different kinds, 267
Dubner, Harvey, 610, 631, 633
Dudeney, Henry Ernest, 610, 633
Dunkel, Otto, 614, 633
Dunn, Angela Fox, 627, 635
Dunnington, Guy Waldo, 610
duplication formulas, 186, 244
Dupr\'e, Lyn Oppenheim, ix
Durst, Lincoln Kearney, viii
Dyson, Freeman John, 172, 239, 610, 615
\medskip
$e$ ($\approx2.71828$),
\sub as canonical constant, 70, 596
\sub representations of, 122, 150
$e_n$, \see Euclid numbers
$E$: expected value, 385--386
$E$: shift operator, 55, 188, 191
$E_n$, \see Euler numbers
Edwards, Anthony William Fairbank, 610
eeny-meeny-miny-mo, \see Josephus problem
efficiency, different notions of, 24, 133
egf: exponential generating function, 364
eggs, 158
Egyptian mathematics, 95, 150
\sub bibliography of, 608
Einstein, Albert, 72, 307
Eisele, Carolyn, 624--625
Eisenstein, Ferdinand Gotthold Max, 202, 610
Ekhad, Shalosh B, 546
elementary events, 381--382
Elkies, Noam David, 131, 610
ellipsis ($\cdots@$), 21
\sub advantage of, 21, 25, 50
\sub disadvantage of, 25
\sub elimination of, 108
empirical estimates, 391--393, 427
empty case,
\sub for spanning trees, 349, 565
\sub for Stirling numbers, 258
\sub for tilings, 320--321
\sub for Tower of Hanoi, 2
empty product, 48, 106, 111
empty sum, 24, 48
entier function, \see floor function
equality, one-way, 446--447, 489--490
equivalence relation, 124
Eratosthenes, sieve of, 111
Erd\'elyi, Arthur, 629, 636
Erd\H os, P\'al (= Paul), 418, 525, 548, 575, 610--611, 634, 636
error function, 166
errors, absolute versus relative, 452, 455
errors, locating our own, 183
Eswarathasan, Arulappah, 611, 635
Euclid (= {\textfont1=\teni \mathchardef\varsigma=294 $E%
{\buildrel\,\smash{\hbox{\gmathtext,}}\over{\upsilon}}%
  \kappa\lambda\epsilon\acute\iota\delta\eta\varsigma$}), 107--108, 147, 611
\sub algorithm, 103--104, 123, 303--304
\sub numbers, 108--109, 145, 147, 150, 151
Euler, Leonhard, i, vii, ix, 6, 48, 122, 132--134, 202, 205, 207, 210, %
  267, 277, 278, 286, 299, 301--303, 469, 471, 513, 529, 575, 603, %
  605, 609, 611--613, 629, 633--636
\sub constant ($\approx0.57722$), 278, 306--307, 319, 481,~596
\sub disproved conjecture, 131
\sub identity for continuants, 303, 312
\sub identity for hypergeometrics, 244
\sub numbers, 559, 570, 620; \also Eulerian numbers
\sub polynomials, 574
\sub pronunciation of name, 147
\sub summation formula, 469--475
\sub theorem, 133, 142, 147
\sub totient function, \see phi function
\sub triangle, 268, 316
Eulerian numbers, 267--271, 310, 316, 378, 574
\sub combinatorial interpretations, 267--268,~557
\sub generalized, 313
\sub generating function for, 351
\sub second-order, 270--271
\sub table of, 268
event, 382
eventually positive function, 442
exact cover, 376
exactly divides, 146
\sub in binomial coefficients, 245
\sub in factorials, 112--114, 146
excedances, 316
exercises, levels of, viii, 72--73, 95, 511
exp: exponential function, 455
expectation, \see expected value
expected value, 385--387
\sub using a pgf, 395
exponential function, discrete analog of, 54
exponential generating functions, 364--369, 421--422
exponential series, generalized, 200--202, 242, 364, 369
exponents, laws of, 52, 63
\medskip
$F$, \see hypergeometric functions
$F_n$, \see Fibonacci numbers
factorial expansion of binomial coefficients, 156, 211
factorial function, 111--115, 346--348
\sub approximation to, \see Stirling's approximation
\sub duplication formula, 244
\sub generalized to nonintegers, 192, 210--211, 213--214, 316
factorial powers, \see falling factorial powers, rising factorial powers
factorization into primes, 106--107, 110
factorization of summation conditions, 36
fair coins, 401, 430
fair dice, 382, 417
falling factorial powers, 47
\sub binomial theorem for, 245
\sub complex, 211
\sub difference of, 48, 53, 188
\sub negative, 52, 63, 188
\sub related to ordinary powers, 51, 262--263, 598
\sub related to rising powers, 63, 312
\sub summation of, 50--53
fans, ix, 193, 348
Farey, John, series, 118--119, 617
\sub consecutive elements of, 118--119, 150
\sub distribution of, 152
\sub enumeration of, 134, 137--139, 462--463
Faulhaber, Johann, 288, 613, 620
Feder, Tom\'as, 635
Feigenbaum, Joan, 632
Feller, William, 381, 613, 636
Fermat, Pierre de, 130, 131, 613
\sub numbers, 131--132, 145, 525
Fermat's Last Theorem, 130--131, 150, 524, 555
Fermat's theorem (= Fermat's Little Theorem), 131--133, 141--143, 149
\sub converse of, 132, 148
Fibonacci, Leonardo, 95, 292, 549, 613, 633, 634
\sub addition, 296--297, 317
\sub algorithm, 95, 101
\sub factorial, 492
\sub multiplication, 561
\sub number system, 296--297, 301, 307, 310, 318
\sub odd and even, 307--308
Fibonacci numbers, 290--301, 575
\sub and continuants, 302
\sub and sunflowers, 291
\sub closed forms for, 299--300, 331
\sub combinatorial interpretations of, 291--292, 302, 321, 549
\sub egf for, 570
\sub ordinary generating functions for, 297--300, 337--340, 351
\sub second-order, 375
\sub table of, 290, 293
Fibonomial coefficients, 318, 556
Fine, Henry Burchard, 625
Fine, Nathan Jacob, 603
Finetti, Bruno de, 24, 613
finite calculus, 47--56
finite state language, 405
Finkel, Raphael Ari, 628
Fisher, Michael Ellis, 613, 636
Fisher, Sir Ronald Aylmer, 613, 636
fixed points, 12, 393--394
\sub pgf for, 400--401, 428
flipping coins, 401--410, 430--432, 437--438
floor function, 67--69
\sub converted to ceiling, 68, 96
\sub graph of, 68
Floyd, Robert W, 634, 635
food, \see candy, cheese, eggs, pizza, sherry
football, 182
football victory problem, 193--196, 199--200, 428
\sub generalized, 429
\sub mean and variance, 393--394, 400--401
Forcadel, Pierre, 613, 634
formal power series, 206, 331, 348, 532
FORTRAN, 446
Fourier, Jean Baptiste Joseph, 22, 613
\sub series, 495
fractional parts, 70
\sub in Euler's summation formula, 470
\sub in polynomials, 100
\sub related to mod, 83
\sub uniformly distributed, 87
fractions, 116--123
\sub basic, 134, 138
\sub continued, 301, 304--309, 319, 564
\sub partial, \see partial fraction expansions
\sub unit, 95, 150
\sub unreduced, 134--135, 151
Fraenkel, Aviezri S, 515, 563, 613--614, 633
Frame, James Sutherland, 614, 633
Francesca, Piero della, 614, 635
Franel, J\'erome, 614
\sub number, 549
Fraser, Alexander Yule, 2, 604
Frazer, William Donald, 614, 634
Fredman, Michael Lawrence, 513, 614
free variables, 22
Fre{\u\i}man, Grigori{\u\i} Abelevich, 608
friendly monster, 545
frisbees, 434--435, 437
Frye, Roger Edward, 131
Fundamental Theorem of Algebra, 207
Fundamental Theorem of Arithmetic, 106--107
Fundamental Theorem of Calculus, 48
Fuss, Nicola{\u\i} Ivanovich, 361, 614
\sub Fuss--Catalan numbers, 361
Fuss, Paul Heinrich von [= Fus, Pavel Nikolaeich], 611--612
\medskip
Gale, Dorothy, 581
games, \see bowling, cards, cribbage, dice, Penny~ante, sports
Gamma function, 210--214, 609
\sub duplication formula for, 528
\sub Stirling's approximation for, 482
gaps between primes, 150--151, 525
Gardner, Martin, 614, 634, 636
Garfunkel, Jack, 614, 636
Gasper, George, Jr., 223, 614
Gau{\ss} (= Gauss), Karl (= Carl) Friedrich, vii, 6, 7, 123, 205, 207, 212, %
 501, 510, 529, 610, 615, 633, 634
\sub hypergeometric series, 207
\sub identity for hypergeometrics, 222, 247, 539
\sub trick, 6, 30, 112, 313
gcd, 103, \see greatest common divisor
generalization, 11, 13, 16
\sub downward, 2, 95, 320--321
generalized binomial coefficients, 211, 318, 530
generalized binomial series, 200--204, 243, 252,~363
generalized exponential series, 200--202, 242, 364, 369
generalized factorial function, 192, 210--211, 213--214, 316
generalized harmonic numbers, 277, 283, 286,~370\kern-3pt
generalized Stirling numbers, 271--272, 311, 316, 319, 598
generating functions, 196--204, 297--300, 320--380
\sub composition of, 428
\sub Dirichlet, 370--371, 373, 432, 451
\sub exponential, 364--369, 421--422
\sub for Bernoulli numbers, 285, 351, 365
\sub for convolutions, 197, 333--334, 353--364, 369,~421
\sub for Eulerian numbers, 351, 353
\sub for Fibonacci numbers, 297--300, 337--340, 351, 570
\sub for harmonic numbers, 351--352
\sub for minima, 377
\sub for probabilities, 394--401
\sub for simple sequences, 335
\sub for special numbers, 351--353
\sub for spectra, 307, 319
\sub for Stirling numbers, 351--352, 559
\sub Newtonian, 378
\sub of generating functions, 351, 353, 421
\sub super, 353, 421
\sub table of manipulations, 334
Genocchi, Angelo, 615
\sub numbers, 551, 574
geometric progression, 32
\sub floored, 114
\sub generalized, 205--206
\sub sum of, 32--33, 54
Gessel, Ira Martin, 270, 615, 634
Gibbs, Josiah Willard, 630
Gilbert, William Schwenck, 444
Ginsburg, Jekuthiel, 615
Glaisher, James Whitbread Lee, 615, 636
\sub constant ($\approx1.28243$), 595
God, 1, 307, 521
Goldbach, Christian, 611--612
\sub theorem, 66
golden ratio, 299, \see phi
golf, 431
Golomb, Solomon Wolf, 460, 507, 615, 629, 633
\sub digit-count sum, 460--462, 490~(exercise~22), 494
\sub self-describing sequence, 66, 495
Good, Irving John, 615, 634
Goodfellow, Geoffrey Scott, 628
Gopinath, Bhaskarpillai, 501, 621
Gordon, Peter Stuart, ix
Gosper, Ralph William, Jr., 224, 564, 615, 634
\sub algorithm, 224--227
\sub algorithm, examples, 227--229, 245, 247--248, 253--254, 534
Gosper-Zeilberger algorithm, 229--241, 319
\sub examples, 254--255, 547
\sub summary, 233
goto, considered harmful, 173
Gottschalk, Walter Helbig, vii
graffiti, vii, ix, 59, 637
Graham, Cheryl, ix
Graham, Ronald Lewis, iii, iv, vi, ix, %
 102, 506, 608--609, 611, 615--616, 629, 632, 633, 635
Grandi, Luigi Guido, 58, 616
Granville, Andrew James, 548
graph theory, \see spanning trees
graphs of functions,
\sub $1/x$, 262--263
\sub $e^{-x^2\!/10}$, 483
\sub Bernoulli polynomials, 473
\sub floor and ceiling, 68
\sub hyperbola, 440
\sub partial sums of a sequence, 345--346
Graves, William Henson, 632
gravity, center of, 273--274, 309
Gray, Frank, code, 497
greatest common divisor, 92, 103--104, 107, 145
greatest integer function, \see floor function
greatest lower bound, 65
greed, 74, 387--388; \also rewards
greedy algorithm, 101, 295
Green, Research Sink, 607
Greene, Daniel Hill, 616
Greitzer, Samuel Louis, 616, 633
Gross, Oliver Alfred, 616, 635
Gr\"unbaum, Branko, 498, 616
Grundy, Patrick Michael, 627, 633
Guibas, Leonidas Ioannis (= Leo John), 590, 616, 632, 636
Guy, Richard Kenneth, 523, 525, 616
\medskip
$H_n$, \see harmonic numbers
Haar, Alfr\'ed, vii
Hacker's Dictionary, 124, 628
Haiman, Mark, 632
H{\aa}land, Inger Johanne, 616, 633
half-open interval, 73--74
Hall, Marshall, Jr., 616
Halmos, Paul Richard, v, vi, 616--617
Halphen, Georges Henri, 305, 617
halving, 79, 186--187
Hamburger, Hans Ludwig, 591, 617
Hammersley, John Michael, v, 617, 636
Hanoi, Tower of, 1--4, 26--27, 109, 146
\sub variations on, 17--20
Hansen, Eldon Robert, 42, 617
Hardy, Godfrey Harold, 111, 442--443, 617, 633,~636
harmonic numbers, 29, 272--282
\sub analogous to logarithms, 53
\sub asymptotics of, 276--278, 452, 480--481, 491
\sub complex, 311, 316
\sub divisibility of, 311, 314, 319
\sub generalized, 277, 283, 286, 370
\sub generating function for, 351--352
\sub second-order, 277, 280, 311, 550--552
\sub sums of, 41, 313, 316, 354--355
\sub sums using summation by parts, 56, 279--282, 312
\sub table of, 273
harmonic series, divergence of, 62, 275--276
Harry, Matthew Arnold, double sum, 249
hashing, 411--426, 430
hats, \see football victory problem
hcf, 103, \see greatest common divisor
Heath-Brown, David Rodney, 629
Heiberg, Johan Ludvig, 611
Heisenberg, Werner Karl, 481
Helmbold, David Paul, 632
Henrici, Peter Karl Eugen, 332, 545, 602, 617, 634, 636
Hermite, Charles, 538, 555, 617, 628, 634
herring, red, 497
Herstein, Israel Nathan, 8, 618
hexagon property, 155--156, 242, 251
highest common factor, \see greatest common divisor
Hillman, Abraham P, 618, 634
Hoare, Charles Antony Richard, 28, 73, 618, 620
Hofstadter, Douglas Richard, 633
Hoggatt, Verner Emil, Jr., 618, 622, 634
Holden, Edward Singleton, 624
Holmboe, Berndt Michael, 604
Holmes, Thomas Sherlock Scott, 162, 228--229
holomorphic functions, 196
homogeneous linear equations, 239, 543
horses, 17, 18, 468, 503
Hsu, Lee-Tsch (= Lietz = Leetch) Ching-Siur, 618, 634
Hurwitz, Adolf, 635
hyperbola, 440
hyperbolic functions, 285--286
hyperfactorial, 243, 491
hypergeometric series, 204--223
\sub confluent, 206, 245
\sub contiguous, 529
\sub degenerate, 209--210, 216, 222, 247
\sub differential equation for, 219--221
\sub Gaussian, 207
\sub partial sums of, 165--166, 223--230, 224, 245
\sub transformations of, 216--223, 247, 253
hypergeometric terms, 224, 243, 245, 527, 575
\sub similar, 541