CO3 Recurrence Relations for Counting Problems

How to construct recurrence relations for counting problems? When faced with a counting problem, instead of finding a direct answer, maybe find a recurrence relation that gives the answer in terms of earlier versions of the problem. Can use the recurrence relation to calculate specific instances, to generate data, and to find patterns. We can prove our patterns using induction. The method is illustrated through 4 concrete examples. Subscribe @Shahriari for in-depth math videos at the undergraduate level.#combinatorics 00:00 Introduction 00:36 The What and Why of recurrence relations 02:19 *In how many ways can you tile a 2x8 array using 1x2 dominoes?* 10:27 *How many sequences of length n are made up of 0, 4, and 7 in such a way that if both 4 and 7 are used, then the first 4 comes before the first 7?* 17:54 *If you draw 100 straight lines from one side of a square to another in such a way that each pair of lines intersects and no three lines go thru the same point, then how many regions are created on the square?* 29:11 Recap: Use a thought experiment to find a recurrence relation, generate data, find patterns, prove it using mathematical induction 29:42 Other techniques for recurrence relations 30:55 *In how many ways can you distribute 11 identical toys in 4 identical boxes?* Next Video: https://youtu.be/RWdBeuEK5SM A series of lectures on introductory Combinatorics. This full course is based on my book Shahriar Shahriari, An Invitation to Combinatorics, Cambridge University Press, 2022. DOI: https://doi.org/10.1017/9781108568708 For an annotated list of available videos for Combinatorics see https://pomona.box.com/s/by2ay2872avxaf2lzv20i2mqurlpvfpr YouTube Playlist: https://youtube.com/playlist?list=PLpcU2wNhmPYcUS3Mt3y8O2fwduWzco4xV Shahriar Shahriari is the William Polk Russell Professor of Mathematics at Pomona College in Claremont, CA USA Shahriari is a 2015 winner of the Mathematical Association of America's Haimo Award for Distinguished Teaching of Mathematics, and six time winner of Pomona College's Wig teaching award.