[SOUND] >> So if we have an analog of binomial coefficients, we should have an analog of the Pascal triangle. Let us write it down. So we begin with, 0 choose 0. This is 1. So anything choose 0 is 1. So, well, the first row is formed by 1 and 1. So what about the second row? This is 1, 1+q, 1. So this item here is, 2 times 1. And this is 2 choose 0. And this is, 2 choose 2, okay. So in the third row, we'll have 1, which is 3 choose 0. 1 + q + q squared. And this is 3 choose 1. 3 choose 2 is symmetric to this one. So it is 1 + q + q squared again. And 3 choose 3 is 1. Okay, fourth row. 1, 1. This is 4 choose 0. 1 + q + q squared + q to the 3rd. And this is 4 choose 1. Here, we have the q binomial coefficient for our 2 times 2 to the square. We have already seen it in our very first example. So this is 1 + q + q squared + twice q squared + q to the 3rd + q to the 4th. And this is 4 choose 2. So this guy = this one. This is 1 + q + q squared + q to the 3rd. And this thing = 1. Okay, so we see that our usual rule of forming the Pascal triangle does not hold. The sum of two entries above a given entry is not equal to it. So it's not true anymore that 1 + 1 + q = 1 + q squared. So there is some other rule, which is maybe somewhat more complicated. Okay, but if we look closely to this table, we can guess what is this rule. So you see that, of course, 1 + 1 + q is not equal to 1 + q + q squared. But if we multiply this entry by q, And sum it up with this one multiplied by 1, we get exactly 1 + q + q squared. Again, if, We take this guy and multiply it by 1, And sum it up with this 1 here, multiply it by q squared, we get exactly 1 + q + q squared again. And the same rule holds for, The subsequent rows. Namely, say, this guy + this guy times q = 1 + q + q squared + q to the 3rd, and, This guy here + this guy multiplied by q squared is 1 + q + q squared + q squared times this one. So + q squared + q to the 3rd + q to the 4th. So this is exactly the q binomial coefficient for choose 2. And here, if we sum 3 choose 2 with, This 1 multiplied by q to the 3rd, We get 1 + q + q squared + q to the 3rd. So this gives us our conjectural rule for inductive construction of q binomial coefficients. Let us take this rule, Proposition, m + n choose m = m + n- 1 choose m- 1, + q to the power of m, times m + n- 1 choose m. Okay, let us prove it. So before we prove it, let us emulate this equality at q = 1. In this case, we get, For remark, for q = 1, we get our standard rule for usual binomial coefficients. m + n choose m = m + n- 1 choose m- 1, + m + n- 1 choose m. Usual binomial coefficient = the sum of two binomial coefficients which are above it in the Pascal triangle. Okay, so let us prove this proposition. Consider the rectangle of size m times n, with m rows, And n columns. Okay, so each Young diagram corresponds to a path from this corner to this corner. Let us look at the first segment of this path. It can be either horizontal, going to east, or vertical, going north. So suppose vertical. This means that the remaining part of this path, Forms a Young diagram inside, A smaller rectangle, Of size m- 1 times n. And each, Path with the first segment going north corresponds to a Young diagram inside this rectangle. And these Young diagrams, Have the generating function = m + n- 1 choose m- 1. So the, Height + the width of this rectangle is m + n- 1. And the number of rows is equal to m- 1. Okay, this is the first alternative. And here is the second one. What if the first segment of our path goes east? So if the first segment goes east, Then our Young diagram has the first column of height m. So this is also m. And the remaining part of, This path forms, A Young diagram inside a small rectangle, which has height m, again. But its width = n- 1. Okay, [COUGH] if we take this smaller rectangle, the generating function for Young diagrams inside it is given by, m + n- 1 choose m. But we have a bigger Young diagram, which is obtained from this one, By adding a column. And this column has exactly m boxes. So the width of each such bigger Young diagram = the width of the smaller Young diagram + m. So the generating function is multiplied by q to the power m. So all our Young diagrams inside this rectangle are split into two parts. The red ones, with the first segment going up, and the yellow ones, with the first segment going right. The Young diagrams in the first part have the generating function = m + n- 1 choose m- 1. And the yellow Young diagrams have the generating function = q to the power m times m + n- 1 choose m. So these two generating functions sum up to the generating function of the Young diagrams inside the whole rectangle. So they sum up to give m + n choose m. The proposition is proved. [SOUND]
