Name: Shapes and Hook Numbers - Numberphile
Uploaded: 2020-03-27T18:05:00.000Z
Duration: 9 min 4 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Present continuous

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.

Another shape that's kind of interesting, it turns out, for my purposes,

is where I have two rows of the same length.

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,"

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.

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.

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—

is 9!—it's this very large number—because

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.

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.

—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.

You can see, for example, here. Every cell had a 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,

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.

Actually, so the main result now is that for any shape—the kinds of shapes I was telling