Rewriting the triangle with selection counts, so any row is reachable directly

0:00You want the twelfth power of a two-term bracket. The array of coefficients will give it to you, and it comes with the price attached. To write the row for index twelve you need the row for index eleven, and to have that you need the row for index ten, and so on all the way down to the single one at the top. Thirteen rows, and ninety-one numbers written out, of which you wanted thirteen.

0:28And the array will not let you skip. Ask it for the row for index twelve with nothing above it and there is simply nothing there to add up. That is not laziness on the array's part. It is the shape of the rule: every entry is defined as two entries from the row above, so the row above has to exist first. So you want a fix, and it is worth being precise about what kind of fix would count.

0:59A faster climb is not one. However quickly you write those thirteen rows, you are still writing thirteen rows, and the row for index fifty would cost you fifty-one. What is wanted is a rule of a different shape. It should take the row number and the position along the row, and hand back the entry, having looked at nothing else at all. Give a rule like that an empty shelf and it does not care.

1:28That is the whole of the rewriting, and the surprising part is not that such a rule exists. It is that the rule already exists under a different name, counting something that has nothing obviously to do with brackets. Here is the rule. The entry at position k of the row for index n is the descending product of n, divided by the descending product of k times the descending product of n minus k.

2:02The descending product of a number is that number times everything below it, down to one. One, one, two, six, twenty-four, one hundred and twenty, seven hundred and twenty. Three of those: one on top, and two underneath. And the rule arrives with two conditions attached to it. The position runs from nothing up to the row number, and the row number is a whole number that is not negative.

2:30Those look like small print. They are not small print, they are the rule refusing. Ask for position eight in the row for index seven, and the bottom of the fraction wants the descending product of minus one, and there is no such product. Ask the selections instead and you get a different kind of answer: there are no ways at all of choosing eight brackets out of seven, which is nought rather than nonsense.

3:01Now put position nought into that formula and watch what happens. On top, the descending product of n. Underneath, the descending product of nothing, times the descending product of n. The descending product of nothing has no factors in it at all, so there is nothing to multiply, and it is taken to be one. That is a convention, and it is doing real work here. With it in place the whole fraction cancels down to one, and the last position of the row does exactly the same thing in a mirror.

3:39So the first entry and the last entry of every row from index nought to index twelve come out as one, and that is what puts a one down both slanting sides of the array. Withdraw the convention, refuse to call an empty product one, and twenty-five of the ninety-one entries down to index twelve stop being computable at all. Every single one of those twenty-five is at an end of its row.

4:11So there are two descriptions of the same array now, and they are worth setting down side by side. Six rows, index nought to index five, twenty-one entries between them. Write every entry twice over: the selection count above, its value underneath. One. One, one. One, two, one. One, three, three, one. One, four, six, four, one. One, five, ten, ten, five, one. The largest number anywhere in those six rows is ten, and it sits twice in the last of them.

4:47For this video I built those rows three separate ways: by multiplying the bracket in one factor at a time, by writing the selections out and counting them, and by the formula. Out to index eight, across all forty-five entries, the three of them never once disagree. Forty-five entries agreeing is a good sign, and it is not a reason. Here is why the difference matters. Take a rule that divides out nothing at all: the descending product of the row number over the descending product of what is left, with no dividing by the position.

5:30Score that on the twenty-one entries of those six rows and it gets eleven of them right. Take the other half of the formula, dividing out the position and not what is left, and it also gets eleven. There are four entries where all three rules agree, and if the array had stopped at the row for index one you would have had no way of telling any of them apart.

5:56The first rival goes wrong at the last entry of the row for index two. The second goes wrong at the first entry of that same row. A rule that matches your table on the rows you happen to have written is not the same thing as the right rule. The only thing that settles it is a reason. So here is the reason, and it is the part most people never get told.

6:23A bracket raised to the seventh power is seven copies of that bracket, multiplied together. Multiply them out and collect nothing at all. Every term of that product is made in exactly one way: you walk along the seven brackets and take one of the two letters out of each. Two choices, seven times over, so one hundred and twenty-eight words, every one of them seven letters long. Now look at where a single term of the finished answer comes from.

6:56A term carrying three copies of the second letter comes from every word that has the second letter in exactly three of its seven places. And a word like that is nothing more than a choice of which three of the seven brackets supplied it. So count them. Words with three second letters in them: thirty-five. Ways of choosing three brackets out of seven: also thirty-five. And they are not merely equal in number, they are the same list read two ways.

7:31Every word points at the brackets that gave the second letter, and every choice of brackets points back at exactly one word. So the coefficient of that term is not a number you look up. It is a count of selections, because the term arises once for every selection. Do that at all eight places of the seventh power and the counts come out one, seven, twenty-one, thirty-five, thirty-five, twenty-one, seven, one.

8:01Which is precisely the row the formula writes. The agreement between the two tables has stopped being a coincidence. Once that is seen, the rule the array was built on turns into a remark. Take eight brackets, and single one of them out. Any selection of three of the eight either names that bracket or it does not. If it does name it, the other two came from the remaining seven, and there are twenty-one selections like that.

8:33If it does not, all three came from the remaining seven, and there are thirty-five of those. Nothing lands in both families and nothing is left out, so the count for three from eight is twenty-one plus thirty-five, which is fifty-six. And twenty-one and thirty-five are exactly the two entries standing above it. That is the addition rule, and it has stopped being a pattern somebody spotted in a table.

9:03It is what happens when you split a set of choices by one question. The other regularity goes the same way. Naming which three of seven brackets supply the second letter is naming which four supply the first. It is one act, described from either end of itself. Choose brackets one, three and four out of the seven, and you have chosen nought, two, five and six just as surely.

9:32So the number of ways of choosing three is the number of ways of choosing four, and every row of the array has to read the same in both directions. Out to index twelve, not one row fails to. That symmetry used to be a thing you noticed. It is now something you could have predicted before writing a single row down. So cash it in. The row for index seven, with nothing whatever above it.

10:03Eight entries, positions nought to seven, each one a descending product over two descending products. One, seven, twenty-one, thirty-five, thirty-five, twenty-one, seven, one. No earlier row was written to get them. And the seventh power of a two-term bracket falls straight out: eight terms, the first index falling from seven to nought, the second rising the other way, the two of them adding to seven in every term, and those eight numbers standing in front.

10:38The row for index twelve, which cost thirteen rows and ninety-one numbers at the start of this video, is now thirteen evaluations and an empty shelf. One, twelve, sixty-six, two hundred and twenty, four hundred and ninety-five, seven hundred and ninety-two, nine hundred and twenty-four, and then back down the other side. Be careful about what has just happened, because it is easy to overclaim it. Two descriptions of the same numbers have been matched against each other, entry by entry, out to index eight.

11:17And a counting argument has been given for why they have to match. What has not happened is a proof of the expansion itself. Nothing above shows that the seventh power of a bracket really is that sum of eight terms, for every value the two letters could take. It shows where the numbers come from if it is. That is a real gap, and it gets closed by induction, which is the next thing to do.

11:46What you have gained here is the shape of the rule. The array asks you for everything above. The count asks you for two numbers, and nothing else at all.