Applied Combinatorics, SF2715

Preliminary Lecture Plan 2011

. The schedule will be filled in with details as the course progresses
No	Time	Room	Content	Text	Exercises
Part I: Enumeration
1	23/3, 8-10	D41	Introduction, enumeration	2:1-7	2:3,7,12
2	25/3, 8-10	D41	Binomial identities, Selection problems, generating functions	3:1-3,7 + HHM1	HHM1: 2,3,4,6,8 Notes I: 1-7
3	29/3, 13-15	D34	Recursions, Fibonacci numbers, avoiding subwords	3.7,4:1-2 + Notes I	3:3acde; 4:1,2d,5,9a(ii),12 Notes I: 8-14
4	31/3, 13-15	E35	Ordinary generating functions, Catalan numbers	4:3,5 + W	Notes I: 15-21 W:1bf,3bgi,5abe
5	1/4, 8-10	D41	Exponential generating functions	W + G1	W:6cd,8a,9 G1:1ace,2ace,3ad,4a
Part II: Permutations and Partitions
6	5/4, 13-15	E35	Catalan numbers, Permutations, derangements	3.5-6,4.4 + Notes 2	Notes 2:1-9 + 3:8,10, 14
7	7/4, 13-15	E36	Set partitions, Bell numbers Stirling numbers	3.11,4.5,5.3	Notes 2:10-15 3:20; 4:12,13,16,18; 5:2,3,5
8	12/4, 13-15	E35	Integer partitions	13.1-2 (3)+ AE	13:3,5,6 + Notes 2:16-18 AE:4,78
9	15/4, 10-12	StudioC	Robinsson-Schenstedt-Knuth Correspondence	13.4	Notes 2:19-22
Part III: Graph Theory
10	27/4, 13-15	StudioC	Trees, Adjacency matrix, Matrix-Tree Theorem, Cayley's theorem	11.2 + HHM2 + (AZ)	HHM2: 1,2,3,4,7
11	29/4, 10-12	StudioC	Min'l spanning trees, Hamiltonian graphs	11:3,5-7	11:2,4,6,12 Notes 3: 1-7
12	3/5, 13-15	E51	Flows in networks	11:8-9 + Notes 3	Notes 3: 8-12
Part IV: Enumeration under group action
13	5/5, 13-15	D41	Automophisms, Burnside's Lemma	Notes 4 14:1-2,15:1-2	15:1; Notes 4:1-5
14	11/5, 13-15	D41	Cycle index	Notes 4 15:3-4	15:2,4,5; Notes 4: 6-10
Part V: Error correcting codes and elections
15	13/5, 10-12	E32	Error correcting codes, Shannon's theorem	17:1-4	Notes 5:1-5
16	16/5, 10-12	StudioC	Linear codes, perfect codes	17:5-6	17:1 + Notes 5: 6-12
17	17/5, 13-15	E53	Mathematics of elections: Proportionality and Arrow's theorem	Valmatematik + 12.9 (not the proof of Arrow)
18	19/5, 13-15	E36	Repetition

TBA - To Be Announced
Last updated 2011-05-17.