me@localhost:~> bc
  d=1; for(i=21; i < 41; i++){d *= i;}; print d; print "\n";
  335367096786357081410764800000
  n = 1; for(i = 1; i < 21; i++){n *= i;}; print n; print "\n";
  2432902008176640000
  d/n;
  137846528820

I couldn't start Python for some reason, so I went 1337 and used BC, which comes preinstalled in every Unix-like OS. BC has a surprising advantage here since 40!/20! cannot be represented as a 64-bit integer since its value exceeds 2^64. That said, BC's stdlib does not provide the factorial function* - so I had to resort to for-loops instead.

* - What it does contain is sine, cosine, exponential, log, arctan, and Bessel J (?!?!?!?!)

  let ans = 1
  for (let i=1; i<21; ++i) {
    ans *= (41 - i)
    ans /= i
  }

An intuitive motivation for the solution in the article (2n choose n). For an n*n grid you have to you will take 2n steps, n "over" and n "down". All that matters is the order of the steps. So if you think of there being 2n "slots", you have to pick n to be "over", and the rest are forced to be "down". So it's n choose 2n indeed.

You can also think of it another way, without using the formula combinations, and only the fact that there are n! permutations of n objects. We can think of this a permutation of 2n items, made up of two groups of n identical items each. Using (2n!) will overcount, due to the fact that each of the "over" steps are identical, and similarly for the "down" group. We have cut down our answer by dividing out all of the repeated sequences. There will be n! redundancies for all the ways we can permute the "over" group and, the same for the "down" group. So this results in (2n!) / (n! * n!), which is exactly equal to 2n choose n. See [1] which explains permutations with repetion this in general. [Note: We pretty much re-derived the formula for combinations!]

[1] https://brilliant.org/wiki/permutations-with-repetition/

Ha. When I found that problem I draw the grids and paths from the example, left for a coffee and when came back I just look at the drawings at an angle and thought "well this is just Pascal's triangle". And the solution was obvious.

Tbh your student reasoning is still dangerous... the patterns could have not generalized nicely. see moser's circle problem

needed to justify viewing this as "arranging down vs right movements" as another comment outlines

Noticing a pattern and just extending it without proving why it works is not really a solution. You can prove it without really "understanding" it using induction, but that still would be proof, same as just counting on a computer.

I think one of the saddest thing is that the kind of person who would recognize, "we can solve this seemingly complicated problem by just applying this formula", would often have trouble even getting recognized in many corporate environments.

I managed a guy like that. He was capable of very complex thinking, but he wasn't in love with complexity, he was in love with simplicity. His solutions tended to be of the form, "we can ignore all these things, and just focus on X, and it will provide all the value." He'd notice something and simplify it and the benefit to the company would be measured in multiples of his salary.

Every manager who'd ever directly managed him knew what a treasure he was, but it was often hard for us to convince others of the value of his solutions because they were so simple, and people were convinced that hard problems must have complex solutions. (or else they would have solved them, right?)

He eventually got bored. He retired and joined a seminary.

Even if you don’t know or remember the basics of combinatorics you can solve the problem with basic dynamic programming : start with the unit grid and then expend it.

The more i think about math these days, the more i see it as a muscle one must constantly train to achieve its potential.

Give it too long a rest and you have to go back at full blast for weeks on end to hope to ever achieve past performance.

I am very bad at math and have always been in awe of those who can do it well.

Heh, this grid image is all too familiar to me right now.

I’m building a grid based game and engine, and I have a game replay format which is not video.

I hit a massive wall with compression, trying to compress unit pathing and was trying to solve a similar solution.

Given an NxN grid, and the 4 cardinal directions (NSEW) you can move in, plus an extra action that makes you move 2 cells instead of 1, and considering you can move 4 cells per second…

What’s the smallest worst-case raw compression artefact you can output for 1 player for a 1 minute game?

It’s an extremely fun problem to solve. I tried:

- encoding changes into bits eg using 2 bits for direction

- movement pattern batching (ie batching 2 moves into 3 bits)

- crowd patterns and movement prediction

- treating movement as a “projectile” and deriving intermediate states

And all sorts of other wild crap that I will write up about on game launch