John Trangenstein : Math 124 Combinatorics
Class hours: MWF 8:45-9:35 Physics 119
Office hours: MWF 1:00 - 2:00 Physics 029C
Course grade depends on:
- Homework (25%)
- 2 Midterms (25% each)
- Final project (25%)
First Midterm : October 2
Second Midterm : November 16
midterm2 answers
Scores are 84, 66, 60, 47, 46
Homework:
Answers to Selected Exercises
- due November 16
- 3, p. 614
- 4, p. 614
- 8, p. 627
- 9, p. 627
- 1, p. 637
- 3, p. 637
- 10, p. 637
- 5, p. 653
- 1, p. 662
- 2, p. 662
- due November 9
- 8, p. 566
- 3, p. 578
- 6, p. 578
- 8, p. 579
- 6, p. 589
- 11, p. 589
- 20, p. 589
- 1, p. 603
- 2, p. 603
- 3, p. 603
- due November 2
- 4, p. 494
- 1, p. 509
- 4, p. 509
- 4, p. 511
- 10, p. 511
- 1, p. 522
- 2, p. 522
- 1, p. 543
- 9, p. 544
- 12, p. 544
- due October 26
- 2, p. 469
- 12, p. 469 (K_{1,3} is in figure 8.15 on p. 454)
- 13, p. 469 (Z_4 is a circuit with 4 vertices)
- 23, p. 469
- 1, p. 478
- 11, p. 478
- 22, p. 479
- 23, p. 479
- 7, p. 486
- 10, p. 486
- 18, p. 486
- due October 19
- 3, p. 447
- 14, p. 447
- 20, p. 448
- 5, p. 455
- 11, p. 456
- 20, p. 457
- 11, p. 461
- 13, p. 461
- due October 14
- 8, p. 380
- 12, p. 380
- 15, p. 381
- 7, p. 396
- 15, p. 397 (see Knuth, Fundamental Algorithms, The Art of Computer
Programming Vol 1 (second edition), p. 531 answer to exercise 4 of
section 2.2.1. Let S represent placing an item on the stack, and X
represent taking an item off the stack. There are binom{2n}{n}
sequences of S's and X's with n of each. An inadmissible sequence has
some point where the number of X's from the start outnumber the S's.
In an inadmissible sequence, locate the first X for which the X's
outnumber the S's. Then in the partial sequence leading up to and
including this X, replace all X's by S and all S's by X. The result
is a sequence with n+1 S's and n-1 X's. Conversely, for every sequence
of the latter type we can reverse the process and find the inadmissible
sequence of the former type that leads to it. This correspondence shows
that the number of inadmissible sequences is binom{2n}{n-1}.
Thus the number of admissible permutations is
binom{2n}{n} - binom{2n}{n-1} = binom{2n}{n}/(n+1). This is a
Catalan number - see Roberts and Tesman p. 386. Also see
Atkinson paper
and
Wikipedia)
- 11, p. 422
- 14, p. 422
- 18, p. 422
- 28, p. 423
- 38, p. 425
- 10, p. 433
- 13, p. 434
- 34, p. 435
- 36, p. 435
- due October 7 (Wednesday)
- 13, p. 58
- 16, p. 58
- 17, p. 58
- 22, p. 58
- 13, p. 356
- 17, p. 356
- 25, p. 357 (Here n is the length of the DNA sequence in each case;
thus the problem is asking you to count the number of derangements for
each; if n were a variable, the problem would be solved more easily by
the principle of inclusion/exclusion)
- 29, p. 358 (Hint on d: given n nonnegative, first prove by induction
that for all k greater than or equal to 2 that
F_{n+k} = F_{k-1} F_{n+1} + F_{k-2} F_n)
- 17, p. 367
- 27, p. 367
- due September 28
- 1 b,c,d,k,m p. 309
- 8, p. 311
- 18, p. 319
- 19, p. 319
- 6 a,c,f,i, p. 327
- 8, p. 333
- due September 21
- 24, p. 216
- 27, p. 216
- 30, p. 216
- 7, p. 295
- 10, p. 295
- 13, p. 296
- 4, p. 301
- 11, p. 302
- 15, p. 302
- due September 14
- 3.2 p. 140 #11
- 3.3 p. 166 #4
- 3.3 p. 167 #12 (omega defined in example 3.16 p. 148, alpha defined in example 3.17 p. 149)
- 3.3 p. 169 #21
- 3.3 p. 169 #26
- 3.4 p. 180 #1
- 3.4 p. 180 #2
- 3.4 p. 184 #13
- 3.5 p. 198 #1
- 3.5 p. 198 #2
- 3.5 p. 198 #7
- 3.5 p. 198 #11
- 3.5 p. 198 #12
- 3.5 p. 199 #16
- 3.5 p. 199 #18
- due September 7
- 2.7 p. 39 #14
- 2.7 p. 39 #15
- 2.7 p. 40 #19 (a or b)
- 2.8 p. 46 #8
- 2.8 p. 46 #10
- 2.9 p. 51 #7
- 2.14 p. 72 #3
- 2.14 p. 72 #5
- 2.14 p. 72 #16
- 2.19 p. 108 #7
- 2.19 p. 108 #10
- 2.19 p. 109 #25
- 3.1 p.132 #20
- 3.1 p.132 #24
- due September 7
- 1. p. 11 #8
- 2.1 p. 22 #2
- 2.1 p. 22 #8
- 2.1 p. 22 #12
- 2.2 p. 25 #3
- 2.2 p. 25 #5
- 2.2 p. 25 #6
- 2.3 p. 27 #8
- 2.5 p. 33 #6
SYLLABUS:
- Chapter 1: what is combinatorics 8/24
- Chapter 2: Basic counting rules
- Chapter 3: Introduction to graph theory
Here is the JGraphEd applet: click on help to learn how to use it.
"Load graph" and "Save graph" under "File" will not work in the applet.
JGraphEd user information
graph software
- Chapter 5: Generating Functions
- 5.1 Series 9/16
The maple command "series(1/((1-x)*(1-x^2)*(1-x^3)),x=0,15);"
will provide the Taylor expansion of the function around x=0 with
remainder term O(x^15).
The
maple worksheet for series
contains maple commands for computing power series of functions and
plotting.
- 5.2 Operating on Series 9/18
- 5.3 Applications to Counting 9/18
- 5.4 Binomial Theorem 9/21
- 5.5 Exponential Generating Functions 9/21
- 2.10 occupancy problems 9/23
- 5.6 Probability Generating Functions 9/25
- Chapter 6: Recurrence relations
- 6.1 Examples 9/25
- 6.2 Characteristic Roots 9/28
- 6.3 Solving Recurrences 9/28
- 6.4 Recurrences Involving Convolutions 9/30
- Chapter 7: Inclusion and Exclusion
- 7.1 Principle and Applications 10/7
- 7.2 Number of Objects Having Exactly m Properties 10/7
- Chapter 8: Polya Theory of Counting
- 8.1 Equivalence Relations 10/9
- 8.2 Permutation Groups 10/9
- 8.3 Burnside's Lemma 10/12
- 8.4 Distinct Colorings 10/12-14
- 8.5 Cycle Index 10/14
- 8.6 Polya's Theorem 10/16-19
- Chapter 9: Combinatorial design
- 9.1 Block Designs 10/21
- 9.2 Latin Squares 10/21
- 9.3 Finite Fields and Families of Latin Squares 10/23
- 9.4 Balanced Incomplete Block Designs 10/26
- Chapter 10: Coding Theory
- 10.1 Information Transmissions 10/28
- 10.2 Encoding and Decoding 10/28
- 10.3 Error-Correcting Codes 10/30
- 10.4 Linear Codes 10/30, 11/2-4
- 10.5 Use of Block Designs to Find Error-Correcting Codes 11/6
- Chapter 11: Existence Problems in Graph Theory
- 11.1 Depth-First Search 11/9
- 11.2 One-Way Street Problem 11/11
- 11.3 Eulerian Chains and Paths 11/13
Koningsberg bridge map
- 11.4 Applications 11/13
- 11.5 Hamiltonian Chains and Paths
- 11.6 Applications
Publically Available Combinatorics Software
Return to: John A. Trangenstein *
Last modified: 26 August 2009