index.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

R\=am\=anujan Aiya\.ng\=ar, Sr\=\i niv\=asa, 330
Ramar\'e, Olivier, 548
Ramshaw, Lyle Harold, 73, 632, 634, 636
random constant, 399
random variables, 383--386; \also independent random variables
Raney, George Neal, 359, 362, 626, 635
\sub lemma, 359--360
\sub lemma, generalized, 362, 372
\sub sequences, 360--361
Rao, Dekkata Rameswar, 626, 633
rational functions, 207--208, 224--226, 338, 527
rational generating functions, 338--346
\sub expansion theorems for, 340--341
Rayleigh, John William Strutt, 3rd Baron, 77,~626
Read, Ronald Cedric, 625
real part, 64, 212, 451
reciprocity law, 94
Recorde, Robert, 446, 626
recurrences, 1--20
\sub and sums, 25--29
\sub doubly exponential, 97, 100, 101, 109
\sub floor/ceiling, 78--81
\sub implicit, 136--138, 193--194, 284
\sub periodic, 20, 179, 498
\sub solving, 337--350
\sub unfolding, 6, 100, 159--160, 312
\sub unfolding asymptotically, 456
referee, 175
reference books, 42, 223, 616, 619
reflected light rays, 291--292
reflected polynomials, 339
reflection law for hypergeometrics, 217, 247, 539
regions, 4--8, 17, 19
Reich, Simeon, 626, 636
Reingold, Edward Martin, 70
relative error, 452, 455
relatively prime integers, 108, 115--123
remainder after division, 81--82
remainder in Euler's summation formula, 471, 474--475, 479--480
Renz, Peter Lewis, viii
repertoire method, 14--15, 19, 250
\sub for Fibonacci-like recurrences, 312, 314, 372
\sub for sums, 26, 44--45, 63
replicative function, 100
repunit primes, 516
residue calculus, 495
residue number system, 126--129, 144
retrieving information, 411--413
rewards, monetary, ix, 256, 497, 525, 575
Rham, Georges de, 626, 635
Ribenboim, Paolo, 555, 626, 634
Rice, Stephan Oswald, 626
Rice University, ix
Riemann, Georg Friedrich Bernhard, 205, 626, 633
\sub hypothesis, 526
Riemann's zeta function, 65, 595
\sub as generalized harmonic number, 277--278, 286
\sub as infinite product, 371
\sub as power series, 601
\sub dgf's involving, 370--371, 373, 463, 566, 569
\sub evaluated at integers, 238, 286, 571, 595, 597
rising factorial powers, 48
\sub binomial theorem for, 245
\sub complex, 211
\sub negative, 63
\sub related to falling powers, 63, 312
\sub related to ordinary powers, 263, 598
Roberts, Samuel, 626, 633
rocky road, 36, 37
R{\o}dseth, {\O}ystein Johan, 626, 634
Rolletschek, Heinrich Franz, 514
roots of unity, 149, 204, 375, 574, 598
\sub fifth, 553
\sub modulo $m$, 128--129
Roscoe, Andrew William, 620
Rosser, John Barkley, 111, 626
Rota, Gian-Carlo, 516, 626
roulette wheel, 74--76, 453
rounding to nearest integer, 95, 195, 300, 344,~491
\sub unbiased, 507
Roy, Ranjan, 626, 634
rubber band, 274--275, 278, 312, 493
ruler function, 113, 146, 148
running time, 413, 425--426
\sub $O$-notation for, abused, 447--448
Ruzsa, Imre Zolt\'an, 611
\medskip
Saalsch\"utz, Louis, 214, 627, 634
\sub identity, 214--215, 234--235, 529, 531
Saltykov, Al'bert Ivanovich, 463, 627
sample mean and variance, 391--393, 427
sample third cumulant, 429
samplesort, 354
sandwiching, 157, 165
S\'ark\"ozy, Andr\'as, 548, 627
Sawyer, Walter Warwick, 207, 627
Sch\"affer, Alejandro Alberto, 632
Schinzel, Andrzej, 525
Schl\"omilch, Oscar Xaver, 627
Schmidt, Asmus Lorenzen, 634
Schoenfeld, Lowell, 111, 626
Sch\"onheim, Johanen, 608
Schr\"oder, Ernst, 627, 635
Schr\"odinger, Erwin, 430
Schr\"oter, Heinrich Eduard, 627, 635
Sch\"utzenberger, Marcel Paul, 636
science and art, 234
Scorer, Richard Segar, 627, 633
searching a table, 411--413
Seaver, George Thomas (= 41), "!Baseball" 8, 21, 94, 105, 106, 343
secant numbers, 317, 559, 570, 620
second-order Eulerian numbers, 270--271
second-order Fibonacci numbers, 375
second-order harmonic numbers, 277, 280, 311, 550--552
Sedgewick, Robert, 632
Sedl\'a\v cek, Ji\v r{\'\i}, 627, 635
self-certifying algorithms, 104
self-describing sequence, 66, 495
"self reference", 59, 95, 531--540, 616, 653
set inclusion in $O$-notation, 446--447, 490
Shallit, Jeffrey Outlaw, 627, 635
Sharkansky, Stefan Michael, 632
Sharp, Robert Thomas, 273, 627
sherry, 433
shift operator, 55, 240
\sub binomial theorems for, 188, 191
Shiloach, Joseph (= Yossi), 632
Shor, Peter Williston, 633
Sicherman, George Leprechaun, 636
sideways addition, 12, 114, 146, 250, 552
Sierpi\'nski, Wac{\l}aw, 87, 627, 634
sieve of Eratosthenes, 111
Sigma-notation, 22--25
\sub ambiguity of, 245
signum function, 502
Silverman, David L, 627, 635
similar hypergeometric terms, 541
skepticism, 71
Skiena, Steven Sol, 548
Sloane, Neil James Alexander, 42, 341, 464, 604, 628, 633
Slowinski, David Allen, 109
small cases, 2, 5, 9, 155, 320--321; \also empty~case
Smith, Cedric Austen Bardell, 627, 633
Snowwalker, Luke, 435
Solov'ev, Aleksandr Danilovitch, 408, 628
solution, 3, 337
sorting,
\sub asymptotic efficiency of, 447--449
\sub bubblesort, 448
\sub merge sort, 79, 175
\sub possible outcomes, 378
\sub quicksort, 28--29, 54
\sub samplesort, 354
spanning trees,
\sub of complete graphs, 368--369
\sub of fans, 348--350, 356
\sub of wheels, 374
Spec, \see spectra
special numbers, 257--319
spectra, 77--78, 96, 97, 99, 101
\sub generating functions for, 307, 319
spinning coins, 401
spiral function, 99
Spohn, William Gideon, Jr., 628
Sports, \see baseball, football, frisbees, golf, tennis
Sprugnoli, Renzo, 564
square pyramidal numbers, 42
square root,
\sub of $1$ (mod $m$), 128--129
\sub of $2$, 100
\sub of $3$, 378
\sub of $-1$, 22
squarefree, 145, 151, 373, 525, 548
squares, sum of consecutive, 41--46, 51, 180, 245, 269, 284, 288, 367, 444, 470
stack size, 360--361
stacking bricks, 313, 374
stacking cards, 273--274, 278, 309
Stallman, Richard Matthew, 628
standard deviation, 388, 390--394
Stanford University, v, vii, ix, 427, 458, 632, 634, \cpage
Stanley, Richard Peter, 270, 534, 615, 628, 635,~636
Staudt, Karl Georg Christian von, 628, 635
Steele, Guy Lewis, Jr., 628
Stegun, Irene Anne, 42, 604
Stein, Sherman Kopald, 633
Steiner, Jacob, 5, 628, 633
Steinhaus, Hugo Dyonizy, 636
Stengel, Charles Dillon (= Casey), "!Baseball" 42
step functions, 87
Stern, Moriz Abraham, 116, 628
Stern--Brocot number system, 119--123
\sub related to continued fractions, 306
\sub representation of $\sqrt3$, 572
\sub representation of $\gamma$, 306
\sub representation of $\pi$, 146
\sub representation of $\phi$, 550
\sub representation of $e$, 122, 150
\sub simplest rational approximations from, 122--123, 146, 519
Stern--Brocot tree, 116--123, 148, 525
\sub largest denominators in, 319
\sub related to continued fractions, 305--306
Stern--Brocot wreath, 515
Stewart, Bonnie Madison, 614, 633
Stickelberger, Ludwig, 628, 633
Stieltjes, Thomas Jan, 617, 628, 633
 \sub constants, 595, 601
Stirling, James, 192, 195, 210, 257, 258, 297, 481, 628
\sub approximation, 112, 452, 481--482, 491, 496
\sub approximation, perturbed, 454--455
\sub constant, 481, 485--489
\sub polynomials, 271--272, 290, 311, 317, 352
\sub triangles, 258, 259, 267
Stirling numbers, 257--267
\sub as sums of products, 570
\sub asymptotics of, 495, 602
\sub combinatorial interpretations, 258--262
\sub convolution formulas, 272, 290
\sub duality of, 267
\sub generalized, 271--272, 311, 316, 319, 598
\sub generating functions for, 351--352, 559
\sub identities for, 264--265, 269, 272, 290, 311, 317, 378
\sub inversion formulas for, 310
\sub of the first kind, 259
\sub of the second kind, 258
\sub related to Bernoulli numbers, 289--290, 317~(exercise~76)
\sub table of, 258, 259, 267
Stone, Marshall Harvey, vi
Straus, Ernst Gabor, 564, 611, 624
Strehl, Karl Ernst Volker, 549, 629, 634
subfactorial, 194--196, 250
summand, 22
summation, 21--66
\sub asymptotic, 87--89, 466--496
\sub by parts, 54--56, 63, 279
\sub changing the index of, 30--31, 39
\sub definite, 49--50, 229--241
\sub difficulty measure for, 181
\sub factors, 27--29, 64, 236, 248, 275, 543
\sub in hypergeometric terms, 224--229
\sub indefinite, \see indefinite summation
\sub infinite, 56--62, 64
\sub interchanging the order of, 34--41, 105, 136, 183, 185, 546
\sub mechanical, 229--241
\sub on the upper index, 160--161, 175--176
\sub over divisors, 104--105, 135--137, 141, 370
\sub over triangular arrays, 36--41
\sub parallel, 159, 174, 208--210
sums, 21--66; \also summation
\sub absolutely convergent, 60--62, 64
\sub and recurrences, 25--29
\sub approximation of, by integrals, 45, 276--277, 469--475
\sub divergent, \see divergent sums
\sub double, \see double sums
\sub doubly infinite, 59, 98, 482--483
\sub empty, 24, 48
\sub floor/ceiling, 86--94
\sub formal, 321; \also formal power series
\sub hypergeometric, \see hypergeometric series
\sub infinite, 56--62, 64
\sub multiple, 34--41, 61; \also double sums
\sub notations for, 21--25
\sub of consecutive cubes, 51, 63, 283, 289, 367
\sub of consecutive integers, 6, 44, 65
\sub of consecutive $m$th powers, 42, 283--285, 288--290, 366--368
\sub of consecutive squares, 41--46, 51, 180, 245, 269, 284, 288, 367, 444, 470
\sub of harmonic numbers, 41, 56, 279--282, 312--313, 316, 354--355
\sub paradoxical, 57
\sub tails of, 466--469, 488--489, 492
Sun Ts\u u [= S\=unz\u{\i}, Master Sun], 126
sunflower, 291
super generating functions, 353, 421
superfactorials, 149, 243
Swanson, Ellen Esther, viii
Sweeney, Dura Warren, 629
Swinden, Benjamin Alfred, 633
Sylvester, James Joseph, 133, 629, 633
symmetry identities,
\sub for binomial coefficients, 156--157, 183
\sub for continuants, 303
\sub for Eulerian numbers, 268
Szegedy, M\'ari\'o, 525, 608, 629
Szeg\H{o}, G\'abor, 625, 636
\medskip
$T_n$, \see tangent numbers
tail exchange, 466--469, 486--489
tail inequalities, 428, 430
tail of a sum, 452--455
tale of a sum, \see squares
tangent function, 287, 317
tangent numbers, 287, 312, 317, 620
Tanny, Stephen Michael, 629, 635
Tartaglia, Nicol\`o, triangle, 155
Taylor, Brook, series, 163, 191, 287, 396, 470--471
telescoping, 50, 232, 236, 255
tennis, 432--433
term, 21
\sub hypergeometric, 224, 243, 245, 527, 575
term ratio, 207--209, 211--212, 224--225
\TeX, 219, 432, \cpage
Thackeray, Henry St.~John, 618
Theisinger, Ludwig, 629, 634
theory of numbers, 102--152
theory of probability, 381--438
theta functions, 483, 524
theta operator, 219--221, 347
\sub converting between $D$ and $\vartheta$, 310
Thiele, Thorvald Nicolai, 397, 398, 629
thinking, 503
\sub big, 2, 441, 458, 483, 486
\sub not at all, 56, 230, 503
\sub small, \see downward generalization, small cases
three-dots ($\cdots@$) notation, 21
\sub advantage of, 21, 25, 50
\sub disadvantage of, 25
\sub elimination of, 108
tilings, \see domino tilings
Titchmarsh, Edward Charles, 629, 636
Todd, Horace, 501
Toledo, Ohio, 73
Tong, Christopher Hing, 632
totient function, 133--135
\sub dgf for, 371
\sub divisibility by, 151
\sub summation of, 137--144, 150, 462--463
Toto, 581
tournament, 432--433
Tower of Brahma, 1, 4, 278
Tower of Hanoi, 1--4, 26--27, 109, 146
\sub variations on, 17--20
Trabb Pardo, Luis Isidoro, 632
transitive law, 124
\sub failure of, 410
traps, 154, 157, 183, 222, 542
trees,
\sub 2-3 trees, 636
\sub binary, 117
\sub of bees, 291
\sub spanning, 348--350, 356, 368--369, 374
\sub Stern--Brocot, \see Stern--Brocot tree
triangular array, summation over, 36--41
triangular numbers, 6, 155, 195--196, 260, 380
triangulation, 374
Tricomi, Francesco Giacomo Filippo, 629, 636
tridiagonal matrix, 319
trigonometric functions,
\sub related to Bernoulli numbers, 286--287, 317
\sub related to probabilities, 435, 437
\sub related to tilings, 379
trinomial coefficients, 168, 171, 255, 571
\sub middle, 490
trinomial theorem, 168
triphages, 434
trivial, clarified, 129, 417--418, 618
Tur\'an, Paul, 636
typefaces, viii--ix, \cpage
\medskip
Uchimura, Keisuke, 605, 635
unbiased estimate, 392, 429
unbiased rounding, 507
uncertainty principle, 481
undetermined coefficients, 529
unexpected sum, 167, 215--216, 236, 247
unfolding a recurrence, 6, 100, 159--160, 312
\sub asymptotically, 456
Ungar, Peter, 629
uniform distribution, 395--396, 418--419
uniformity, deviation from, 152; \also discrepancy
unique factorization, 106--107, 147
unit, 147
unit fractions, 95, 101, 150
unwinding a recurrence, \see unfolding a recurrence
up-down permutations, 377
upper index of binomial coefficient, 154
upper negation, 164--165
upper parameters of hypergeometric series, 205
upper summation, 160--161, 176
useless identity, 223, 254
Uspensky, James Victor, 615, 629, 633
\medskip
$V$: variance, 387--398, 419--425
van der Poorten, Alfred Jacobus, 629
Vandermonde, Alexandre Th\'eophile, 169, 629,~634\kern-6pt
Vandermonde's convolution, 169--170
\sub as a hypergeometric series, 211--213
\sub combinatorial interpretation, 169--170
\sub derived mechanically, 234
\sub derived from generating functions, 198
\sub generalized, 201--202, 218--219, 248
\sub with half-integers, 187
vanilla, 36
Vardi, Ilan, 525, 548, 603, 620, 629, 633, 636
variance of a probability distribution, 387--398, 419--425
\sub infinite, 428, 587
Veech, William Austin, 514
Venn, John, 498, 630, 633
\sub diagram, 17, 20
venture capitalists, 493--494
violin string, 29
vocabulary, 75
Voltaire, de (= Arouet, Fran\c{c}ois Marie), 450
von Staudt, Karl Georg Christian, 628, 635
Vyssotsky, Victor Alexander, 548
\medskip
Wall, Charles Robert, 607, 635
Wallis, John, 630, 635
Wapner, Joseph Albert, 43
war, 8, 16, 85, 434
Waring, Edward, 630, 635
Waterhouse, William Charles, 630, 635
Watson, John Hamish, 229, 405
Waugh, Frederick Vail, 630, 635
Weaver, Warren, 630
Weber, Heinrich, 630
Weisner, Louis, 516, 630
Wermuth, Edgar Martin Emil, 603, 630
Weyl, Claus Hugo Hermann, 87, 630
Wham-O, 435, 443
wheel, 74, 374
\sub big, 75
\sub of Fortune, 453
Whidden, Samuel Blackwell, viii
Whipple, Francis John Welsh, 630, 634
\sub identity, 253
Whitehead, Alfred North, 91, 503, 603, 630
Wiles, Andrew John, 131
Wilf, Herbert Saul, 81, 240, 241, 514, 549, 575, 620, 624, 630--631, 634
Williams, Hugh Cowie, 631, 633
Wilquin, Denys, 634
Wilson, Sir John, theorem, 132--133, 148, 516, 609
Wilson, Martha, 148
wine, 433
Witty, Carl Roger, 509
Wolstenholme, Joseph, 631, 635
\sub theorem, 554
Wood, Derick, 631, 633
Woods, Donald Roy, 628
Woolf, William Blauvelt, viii
worm,
\sub and apple, 430
\sub on rubber band, 274--275, 278, 312, 493
Worpitzky, Julius Daniel Theodor, 631
\sub identity, 269
wreath, 515
Wrench, John William, Jr., 600, 606, 636
Wright, Sir Edward Maitland, 111, 617, 631, 633
Wythoff (= Wijthoff), Willem Abraham, 614
\medskip
Yao, Andrew Chi-Chih, ix, 632
Yao, Foong Frances, ix, 632
Ya\'o, Q\'{\i}, 622
Youngman, Henry (= Henny), 175
\medskip
zag, \see zig
Zagier, Don Bernard, 238
Zapf, Hermann, viii, 620, \cpage
Zave, Derek Alan, 631, 635
Zeckendorf, Edouard, 631
\sub theorem, 295--296, 563
Zeilberger, Doron, ix, 229--231, 238, 240, 241, 631, 634
zero, not considered harmful, 24--25, 159
\sub strongly, 24--25
zeta function, 65, 595
\sub and the Riemann hypothesis, 526
\sub as generalized harmonic number, 277--278, 286
\sub as infinite product, 371
\sub as power series, 601
\sub dgf's involving, 370--371, 373, 463, 566, 569
\sub evaluated at integers, 238, 286, 571, 595, 597
Zhu Shijie, \see Chu Shih-Chieh
zig, 7--8, 19
zig-zag, 19
Zipf, George Kingsley, law, 419
\eject % omit this if last column doesn't nearly fill the page
\bye