FALL 1995, Call #94184

       Concrete Mathematics  CIS/CE 290F (New Course)

                       J. Yellin, x2195, yellin@cse.ucsc.edu

Course  Description:   Combinatorial mathematics, including
summation methods, binomial coefficients, combinatorial
sequences(Fibonacci, Stirling, Eulerian, Harmonic, Bernoulli
numbers), generating functions and their  uses, bernoulli  
processes and other topics in discrete probability.  Oriented
toward problem solving applications on the graduate level, mainly
in computer science.

Prerequisites: Calculus, discrete mathematics.

Text: Concrete Mathematics,  Graham, Knuth, and Patashnik
(Addison-Wesley, 1989) (GKP)

Meetings: MWF 1230-145, Appl. Sci. 169

Weekly Schedule of Topics

1. Sums and recurrences, multiple summation.
Reading: GKP, pp. 21-40
2. Sums II.  Infinite sums, general summation methods.
Reading: GKP, pp. 41-61
3. Binomial coefficients, identities, manipulating binomial
coefficients, related summations.
Reading: GKP, pp. 153-195.
4. Binomial coefficients II.  Generating functions,
hypergeometric functions and transformations.
Reading: GKP, pp. 196-229.
5. Sequences of number theory.  Stirling, Eulerian, Harmonic
Numbers
Reading: GKP, pp. 243-264.
6. Sequences II.  Harmonic sums, Bernoulli numbers,
Fibonacci numbers, continuants.
Reading: GKP, pp. 265-294.
7. Generating Functions.  Basic tools and methods,
recurrences.
Reading: GKP, pp. 306-335.
8. Generating Functions II. Particular examples,
convolutions, exponential generators, Dirichlet series.
Reading: GKP, pp. 336-356.
9.  Discrete Probability.  Probability generating functions.
Reading: GKP, pp. 367-386.
10. Discrete Probability II. Coin flip problems, hashing.
Reading: GKP, pp. 387-412.