Bonus problem: Prove that the Petersen graph does not have a Hamilton cycle.
Eighth homework assignment:
(due Wednesday, November 3)
Section 11.1 #3,9
Section 11.3 #1,21,22,23,35
Section 11.4 #21,23
Bonus problem: Each edge of the complete graph with 11 vertices is colored either red or blue.
Let G be the graph consisting of all red edges, and let H be the graph consisting of all blue edges.
Prove that at least one of these two graphs is not planar.
Seventh homework assignment:
(due Wednesday, October 27)
Section 10.2 #1,9,23
Section 10.5 #1,4,6,8,10
Bonus problem: Let F_n be the nth Fibonacci number. Prove that for all n >= 0, we have
Bonus problem: Show that the coefficient of x^a*y^b in the power series expansion of xy/((1-x)(1-y)(1-xy)) is min(a,b).
Fourth homework assignment:
(due Monday, September 27)
Section 5.3 #2,4,6,8,13,16
Section 4.1 #2b,14,26
Bonus problem: For n a positive integer and t a real number, define the "falling factorial" function (t)_n by
(t)_n = t(t-1)...(t-n+1). Prove that t^n = S(n,1)*(t)_1 + S(n,2)*(t)_2 + ... + S(n,n)*(t)_n, where the numbers
S(n,k) are Stirling numbers of the second kind.
Third homework assignment:
(due Wednesday, September 15)
Section 8.1 #3,5,6,12,16,30
Section 8.3 #5,9,12
Bonus problem #1: In Bristol, 90% of the citizens drink tea; 80% drink coffee; 70% drink whiskey; and 60% drink gin.
No one drinks all four beverages. What percentage of Bristol's citizens drink liquor?
Bonus problem #2: Select n points on a circle and draw the lines connecting each pair of points. Assume that the points are chosen
in such a way that no 3 of these lines meet in a single point. Into how many regions do these lines divide the interior of the circle?
Second homework assignment:
(due Wednesday, September 8)
Section 1.4 #4,15,20
Section 1.5 #9
Section 1.6 #15,20,27,30
Bonus problem: Show that the number of ordered selections, without repetition, from a set of n objects is [e * n!],
where e is the base of the natural logarithm and [ ] denotes the greatest integer function.
First homework assignment:
(due Monday, August 30)
Section 1.1/1.2 #8,15,27
Section 1.3 #4,12,13,26,30
Bonus problem: Find a recursive algorithm for calculating multinomial coefficients.
Course outline:
This course will focus on elementary combinatorial techniques used
for discrete problem solving, including counting methods, linear
recurrences, graphs and networks, and related algorithms. It is useful
for all sorts of theoretical and applied mathematics, as well as for
computer science.
Topics to be covered will include permutations and combinations, the pigeon-hole principle, induction,
combinatorial probability, binomial and multinomial coefficients, the
inclusion-exclusion principle, linear recurrences, generating functions,
graph isomorphism, connectivity, Euler trails and Hamilton cycles, the traveling salesman problem,
planarity, matchings, search algorithms, shortest paths, and spanning tree algorithms.
Exams:
There will be three in-class midterm exams and an in-class final exam. These will be announced at least one week in advance.
Homework:
Homework will be assigned on a regular basis, and will generally be due in class on Mondays.
There will be some reading assignments as well.
Grading Policy:
Homework will account for 10% of your course
grade, each miderm 20%, and the final exam 30%.
Collaboration:
On the homework sets, collaboration is both allowed
and encouraged. However, you must write up yourself and understand your own
homework solutions. Any academic dishonesty on the midterm or final exams, if detected,
will result in a score of zero for that exam.
Miscellany:
If at any point during the semester you feel
unsatisfied with some aspect of the course, please come talk to me
about it! I have no problem making adjustments mid-stream if
necessary. This course is supposed to be challenging, stimulating, and fun.
This page was last modified on December 8, 2004 by
Matt Baker.