Scribd
Upload
108 views

Syllabus PDF

Jon Butler

Uploaded by

Ritesh Khatri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
108 views

Syllabus PDF

Jon Butler

Uploaded by

Ritesh Khatri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

COMBINATORIAL MATHEMATICS

Instructor: Jon T. Butler, Naval Postgraduate School, Monterey, CA USA

Time: Three Day Course

Objective: To give students the ability to solve enumeration problems, including the
counting of steps in a program (time of execution) and the counting of objects commonly
found in research problems, such as graphs and trees. Asymptotics will be covered,
allowing the student to convert complex expressions (common to many enumeration
problems) into simple approximations.

Time Day #1 Day #2 Day #3


1000-1050 Lecture #1: Introduction, Lecture #6: Ordinary Lecture #11: Recurrence
combinations and permu- generating functions. How relations - Using generating
tations, Pascal’s triangle, to use. functions to solve.
1100-1150 Lecture #2: Circular Lecture #7: Generating Lecture #12: Inclusion
permutations. Choice with function example - trees /exclusion. Derrangements.
repetition.
1150-1300 Lunch Lunch Lunch
1300-1450 Exercise #1 Exercise #2 Exercise #3
1400-1450 Lecture #3: Combinational Lecture #8: Exponential Lecture #13: Asymptotic
identities generating functions. approximations -
1500-1550 Lecture #4: Distribution of Lecture #9: Distributing Lecture #14: Asymptotic
objects to cells ((non)/dis- nondistinct objects into non- approximations - Finding
tinct objects (non)distinct distinct cells. Stirling’s simple closed form
cells). numbers. solutions.
1600-1650 Lecture #5: Pigeonhole Lecture #10: Partitions of Lecture #15: Example of
principle. integers. asymptotic approximations

Notes: Lecture notes will be handed out.

References:

[1] C. L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, 1968. Although 30


years old, this is a very good textbook.

[2] J. Riordan, An Introduction to Combinatorial Analysis, McGraw-Hill, 1958. Classic text,


advanced and formal.

[3] A. Tucker, Applied Combinatorics, John Wiley & Sons, 1984. Easy to read - many
examples.
[4] E. A. Bender and S. G. Williamson, Foundations of Applied Combinatorics, Addison-Wesley
Publishing Co., 1991. Good text that was not well typeset.

[4] R. P. Grimaldi, Discrete and Combinatorial Mathematics, Addison-Wesley Publishing Co.,


1994. Easy to read and covers other topics - logic, set theory, relations, functions, finite
state machines, graph theory, modern algebra, and switching theory.

[5] N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973. A list of integer
sequences. This is a valuable reference when you have the question “Has anyone derived
this sequence before?” It contains about 2300 sequences.

[6] N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press,
San Diego, 1995. Updated version of the above. It contains 5487 sequences.

[7] N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, online version -
http://www.research.att.com/~njas/sequences/index.html. This version contains over 25,000
sequences.

Instructor:
Jon T. Butler, Professor
Department of Electrical and Computer Engineering
Naval Postgraduate School, Code EC/Bu
Monterey, CA 93943-5121 U.S.A.
408-656-3299 (O) 408-656-2760 (FAX)
E-mail: [email protected]
Homepage: http://dubhe.cc.nps.navy/mil/~butler

You might also like