Recurrences and Miscellaneous Counting

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. There is a staircase with ten steps, and you climb it taking one step or two steps at a time. In how many ways can you reach the top? Many students start listing every way, and soon the page is full and the count is still wrong! So, hold that thought. By the end of this video, you will get it with one short list of numbers. First, two quick counting ideas, then the big one: building a count from smaller counts. Questions like these do come up in JEE, so let's begin.

0:36League or knockout: count the right thing

Alright, first idea. Ten teams play a league, and each pair of teams meets exactly once. How many matches are played? Each team plays nine others, so ten times nine, ninety, right? No, no, careful! Ten times nine counts team one against team two, and then team two against team one, as two matches. But that is the same match! The order does not matter. So one match is just one pair of teams, chosen from ten. Ten C two: the small ten at the top left, capital C for combinations, and the small two at the bottom right. Ten times nine, over two: forty five matches. Clear? Now, a knockout with sixteen teams. Lose one match, and you are out. The key fact: every match eliminates exactly one team, no more, no less. So tell me: how many teams must be eliminated before we have a champion? Fifteen, exactly! Sixteen teams and one champion, so fifteen teams must go out. One match for each of them, so fifteen matches. No chart, no adding, just one line. That is a topper's trick. Got it?

1:46Matrices of zeros and ones

Second idea. Take a three by three matrix; the cross on screen is read as by, so three rows and three columns. Every entry is zero or one, and there are nine places to fill. With me? First question: exactly two ones in each row. Look at just one row. It has three places. In how many ways can it hold exactly two ones? Three ways, yes! Choose which two of the three places get the ones: three C two, that is three. The last place gets the zero. Right? And the rows? Each row chooses on its own. So multiply. Here the cross means times: three times three times three, three to the power three. Twenty seven matrices. Okay? Now the second question looks almost the same: exactly two ones in the whole matrix, in total. Same answer, twenty seven, right? Oh no, careful! Read the question again. Now there are only two ones in all nine places. So just choose two places out of nine: nine C two, nine times eight, over two, thirty six. In each row, or in total: one small phrase changes the whole method. Clear?

3:00Recurrences: build from smaller cases

Now, the big idea. Some counts are hard in one shot, so first we name the count. On screen, w with a small n at the bottom right, read as w n, is the number of ways for size n. W for ways. Okay? Now the trick. Don't look at the start; look at the end. Split everything by the last move, or by how it ends. Now tell me: if you remove that last move, what is left? Yes, exactly! The same problem, only smaller. And the count for that smaller problem is one we can find first. Right? So w n is built from w n minus one, w n minus two, and so on; the three dots mean and so on. Counts you already have. Such a rule is called a recurrence. With me? And every recurrence needs a starting point. Find the first one or two values by hand, carefully. Then build the list upward. If the start values are wrong, every value after them is wrong too. Got it?

4:02Example 1: ways to climb 10 steps, 1 or 2 at a time

Remember our staircase? Let's finish it. In how many ways can one climb ten steps, taking one or two steps at a time? One step and then two is different from two and then one, so the order of the moves matters. Pause the video, and try it first. Done? Okay, let's check. Let w n be the number of ways to climb n steps. Now use our trick: look at the very last move. What can it be? Correct! Either one step, from step n minus one, or two steps, from step n minus two. Nothing else is possible. Right? So every way to reach step n is a way to reach n minus one, then one step, or a way to reach n minus two, then two steps at once. w n equals w n minus one, plus w n minus two. Each value is the sum of the two before it. Okay? Now the start values. How many ways for one step, and how many ways for two steps? One step: just one way, so w one is one. Two steps: one step and then one more, or two steps at once. Two ways! If you said one way, careful: start values are where most slips happen. Clear? Now just build upward. One plus two is three. Two plus three is five. Then eight, thirteen, twenty one, thirty four, fifty five, and fifty five plus thirty four is eighty nine. So w ten is eighty nine. Eighty nine ways, without listing a single one! Puzzle solved. See how fast that was?

5:39Example 2: length-8 binary strings, no two 1s together

Now a slightly harder one. So, a binary string is a row of zeros and ones, like zero, one, one, zero. How many binary strings of length eight have no two consecutive ones, that is, no two ones side by side? Pause and try. Hint: look at how the string ends. Done? Okay, let's check. Let b n be the number of good strings of length n; b for binary. Good means no two ones side by side. With me? Now, how can a good string end? Two cases. Case one: it ends in zero. Then the first n minus one places can be any good string. That gives b n minus one. Okay? Case two: it ends in one. Same thing again: the first n minus one places are any good string, so b n minus one again, right? Oh no, careful! This is the trap. If the last digit is one, the digit before it cannot be one. It must be zero. So the string really ends in zero one, and the first n minus two places are any good string. That gives b n minus two, not b n minus one. Got it? So the rule is exactly the staircase rule. But are the start values the same too? No! Length one: zero, or one. Both are fine, so b one is two. Length two: zero zero, zero one, and one zero. One one is not allowed. So b two is three. So, b n equals b n minus one, plus b n minus two, with b one equal to two and b two equal to three. Right? Now build upward. Two, three, five, eight, thirteen, twenty one, thirty four, fifty five. That is eight values, for lengths one to eight. So b eight is fifty five. Very good! Same rule as the staircase, new start values.

7:30Quick revision: matches, 0-1 matrices and recurrences

So, quick revision. League: one match is just one pair of teams. Knockout: one match for every team that goes out. Read the question carefully: in each row, or in total, changes the whole method. And recurrences: split on the last move, check the start values, and build upward. Now go and try the practice problems on this page. One of them is about binary strings again, so you are ready. All the best!