字幕列表 影片播放 列印英文字幕 We're talking about a problem involving putting numbers into boxes and other shapes. And the shape is an arrangement of boxes that looks something like this. And I've got a certain number of boxes in the first row, so I have four boxes in the first row, and two in the second row, and one in the third row. And the rule is that these numbers must be decreasing. And the second rule is that the boxes are left-justified. And that's it! That's the rule. A simple example would be this, here's a square. Three boxes in the first row, three in the second row, and three in the third row. The number of boxes in two rows can be the same. Another example of a shape would be something like this. This is something we call a staircase. Four, and three, and two, and one. Another shape that's kind of interesting, it turns out, for my purposes, is where I have two rows of the same length. This would be the shape (6,6). Why don't we put numbers in them? And so maybe I can even do it with these shapes and show you exactly what we do. So, in this first shape, we have seven boxes altogether, so I take the numbers 1–7. The rules are that the numbers must be increasing along rows and increasing down columns. So, 1-3-6 is increasing, 2-5 is increasing, and so forth. Those are the rules. This is called a Standard Young Tableau. Young is a person. Yes, that's right. While I'm at it, the word "tableau" just simply means "an arrangement of numbers in a shape," with no rules satisfying them. For example, I can just do an example of a tableau that's not a Standard Young Tableau. I'll just put the 1 here, and the 2 here, and the 3 here, and the 4 here, and the 5 and the 6 and the 7... So, these numbers are not increasing along rows and increasing down columns. So that's just called a tableau. And we're gonna talk today about Standard Young Tableaux. Here, I'll make a Standard Tableau and actually, while I make it, it's sort of important to understand what I'm doing while I'm making it, because I have to put a 1 in the upper-left-hand corner, there's no choice about that. And then 2 has to go either here or here, I'll put it there. 3 has to go either here or here at that point, I'll put it down here. Maybe 4 here, 5 here. And if I stop before I'm finished, you can see that what's happening is that I'm building the shape. The shape is the 3x3 square, but I'm building it up cell by cell. In terms of what I'm getting, it's a sequence of subshapes. So right now, what I've done, I've created a tableau of this shape. But I'll finish it up now, so 4, 5, 6, 7, 8, 9. So that's a Standard Tableau of that shape. I'll do one here quickly. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. And here, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. It's easy to do it because you just sort of build your way from the upper-left-hand corner down to the bottom right hand corner in this case. —Are these hard to make? Are there lots of them? Are they rare? Are Standard Young Tableaux common? —Well, that's a good question, because what I really want to talk about is how many there are. The problem of computing the number of Standard Tableaux. What's kind of amazing is that we know very exact and precise answers to that question. So, I'll tell you, for example, let's take this shape. The number of Standard Young Tableaux—I'll abbreviate it as SYT—is 42. So, I could systematically write down all 42 tableaux, and I could convince myself that was correct, but there's a formula for it, and the formula goes like this, and I'll show you how you do it. It's equal to, let's see, there's nine cells in this shape. So it's 9×8×7×6×5×4×3×2×1, divided by—that's 9!—and by the way, that's the number of ways of just filling this shape with the numbers in any manner whatsoever. So the total number of fillings of this shape— which is what we've called a tableau— is 9!—it's this very large number—because there's 9 choices for what to put here, and 8 for what to put there once you've decided on the first one, and 7 for what you put here once you've decided on these two, etc. So you get 9! quite easily. But if you require the rules to be satisfied, then the number has to be reduced by something, and I'm gonna tell you what exactly it has to be reduced by. First of all, you take this shape, and we fill it up with a bunch of other numbers, and the numbers are constructed this way: I put a 1 here, and then a 2, and then a 3, and then I go up, 4, and then 5, and then I go down, 4 and then 3, and then down, 2, and then up, 3, and I divide this by the product of all those numbers. And the ratio of these two numbers is the number of Standard Young Tableaux of this shape. Now let's just compute it. So these cancel... I've canceled everything and I see 3×2×7, which is 42. So that's how I got 42. —Now I guess the million-dollar question is what on earth are these numbers? —That's the question, the big question! Well, there are two questions. One, where did these numbers come from? They just came out of the blue! What's going on? And secondly, why is it true? And why is it true generally? So what's gonna happen is that not only have I shown you a formula for computing Standard Tableaux of shapes like this, but it's gonna work for any shape. So I have to tell you what these numbers are. These numbers are called the hook numbers. Hook numbers are the following: you have a shape—I'll do it sort of schematically first. Every cell has a hook number. You can see, for example, here. Every cell had a hook number. How did I get this hook number? The answer is that I first of all computed the hook associated with that cell. And the hook is everything that you get by going down from it, and to the right, and the square itself. So you get this sort of inverted-L-shaped thing, which we call a hook. So that's the hook associated with that cell. And so, for example, we can take this cell here. What's its hook number? Well, its hook consists of everything to the right and everything below, and so there are three cells altogether, so the hook number is 3. This has hook number 4, because I have one, two, three, four. This has hook number 5, so I have one, two, three, four, five, etc. So that's what I was doing when I went through that crazy process of filling the square up with numbers. I was computing the hook numbers. Actually, so the main result now is that for any shape—the kinds of shapes I was telling you about before, not just these special square shapes—the formula is exactly this. You take n!, where n is the number of cells, and divide it by the product of all the hook numbers. All right, so let's do one more example. Here's the shape. That's a (4,2,1) shape. Yes, exactly. Well first of all, n is 7. So the number of Standard Young Tableaux is going to be 7×6×5×4×3×2×1 divided by the product of the hook lengths. So, what are they? I'm going to start putting the hook lengths in each cell. This is what we call a corner cell. Maybe I should use that term now, because it's going to come up again. It's a cell with hook length 1. Its hook number is 1. And that's a corner cell, and that's also a corner cell. This one has hook number 2, because the hook only goes to the right. There's two cells in it. This has hook number 4. This has hook number 3. This has hook number—what is it?—6. One, two, three, four, five, six. And so the formula says that I should take 7! and divide by 6×4×2×1×3×1×1. So let's do that computation. Cancel the 3's... Cancel the 4's, cancel the 2's, cancel the 6's. And it looks like we get 7×5, or 35. The number of Standard Young Tableaux of this shape is 35. —I'm always surprised by how high these numbers are for such simple shapes. —You asked a good question before. If you fix the number of cells, which ones are the biggest? Which ones give you the largest number? That's an interesting and rather difficult question that people do know the answer to, but it's too complicated to talk about today. —This video was filmed at the Mathematical Sciences Research Institute, in that room there actually, but the interview didn't stop here. If you'd like to go deeper into the world of tableaux and hook numbers, including some details about how to prove all this, the interview continues over at our second channel, Numberphile2.