[MUSIC] Hi and welcome back to Introduction to Enumerative Combinatorics. This is our last lecture and it is entitled q-Binomial Coefficients. Today we will discuss combinatorial problems that have already appeared in the previous lectures. And we will look at their quantum or q or Gaussian counterparts. Well, we will begin with the following question that we have already discussed in the first lecture. Suppose we have- A town- Formed by m blocks from north to south and- N blocks from west to east. A driver wants to get from the southwest corner to the northeast corner. He's allowed to drive only east and north. In how many ways can he do this? Okay, well his path might look like- This, okay. We have already discussed in our first lecture that his path should be fold by m plus n segments, it should drive m plus n blocks. So, the question is- How many ways are there to get from the southwest corner to the- Northeast corner? Okay, so his path is formed by n plus n segments. So, he should arrive in m+n blocks. And out of these m+n blocks, he should arrive exactly m blocks north, and n blocks east. So, he needs to pick m. Possibilities out of m plus n. He should pick m different blocks. He wants to drive north. Otherwise, he should pick n blocks so that he goes east. Okay, so each such path gives us a sequence of letters and then e an instruction how to drive this corner to this one. Well say for this path around here I think, this will be like as follows first here east, then east, then north, east, then north, then east, then north again, east, north, east. So, in this case we have sequence of ten blocks, one, two, three, four, five, six, seven, eight, nine, ten. And out of them we have exactly four n's. One, two, three, four. So, the answer is well in this case, the total number of such sequences would be 10 choose 4. And in the general case, It will be m+n choose m or Which is the same m+n choose n. So, this is the answer to our problem. Okay, and what's the relation between this problem and our previous lecture? In our previous lecture, we have this cost and on diagrams. And note that each such path actually corresponds to a young diagram, which is situated to the north of this path. So, let me highlight this young diver. And each sectional diagram fits inside the rectangle of size m times n with n rows and m columns. So, paths correspond, To young drivers. The Lambda which fit inside the rectangle size m times n. Okay, and this so this problem allows us to enumerate young diagrams with several conditions. What are these conditions? Well first of all they should have at most m parts in the corresponding partition. So, they have at most m rules to fit the rectangle. And they should have at most n boxes in each row. So, we have and well such young diagrams bijectively correspond to graphs, so the number of young diagrams fitting inside this rectangle is also m+n choose m. For example, if, n=m=2 There are 4 twos 2, that is 6, Young diagrams fitting inside the square two by two. With at most two rows and at most two columns. And let me draw all these diagrams here. So, first I have the empty on diagram, Which corresponds to the following path. We drive two blocks north and then two blocks east. And then there is a square, And this is the followed path. North, east, north, east. Then we have two more diagrams formed by two boxes. This one and this one. So, these two dominoes correspond to The following two paths. Up, right, right, up. And right, up, up, right. Okay, then, The following shape, Which corresponds to this path with a east, north, east, north. And then we have the whole two by two square. And in this case our robber goes first two blocks east and then two blocks north. Okay, so we have 6 young diagrams. And out of these 6 diagrams, There is only 1 diagram of 0 boxes, 1 box, 3 boxes, and 4 boxes. And 2 diagrams formed by 2 boxes. Okay, so again let us introduce a generating function for such diagrams. So, we will to each diagram we'll assign it's weight which will be just the number of boxes. And we sum up our variable q to the power equal to the weight of each diagram. Namely, to the square we assign q to the power of 4. To this L shaped diagram we'll assign q to the power of 3. These two correspond to q squared, this will be q, and this will be 1. So, now we sum up these 6 monomials. And get the following thing, 1 + q + 2q squared + q cubed + q to the power of 4. And this will be called the q binomial coefficient. 4 choose 2 sub q. We'll give the formal definition in the next one. [MUSIC]
