The 2n choose n solution isn't at all intuitive to me but thinking about it in terms of 40 steps, 20 of them rightward and 20 of them downward an then looking at all distinct permutations of these 40 steps as (40!) / ((20!)^2) is intuitive to me. Then it becomes obvious that since 20 is half of 40, k and n - k are the same number (20), which coincides with the binomial coefficient n! / k!(n - k)!. But this seems like a lucky coincidence in 2 dimensions and if you extended the problem into 3D you'd do better thinking about permutations.

▲

emil-lp 2 days ago | parent [-]

2n choose n is just: you must move East 20 times and South 20 times. Hence any solution looks like a permutation of 20 Es and 20 Ss. Now, only look at the indices for the Es. There are 20 of them. Out of 40.

40 indices, pick 20. Those are East moves, the rest are South moves.

▲

grumbelbart2 2 days ago | parent [-]

This interpretation also generalizes nicely to 3d. You have 60 moves, 20 of which will be up (60 choose 20), then 20 are east (40 choose 20), then 20 are south (20 choose 20).

	▲	C-x_C-f 2 days ago \| parent [-]
		That's a nice way to put it. FWIW the generalization of binomial coefficient which allows you to express an n-dimensional solution is called a multinomial coefficient [0]. So in a 3d 20x20x20 box we would have (60 multichoose 20, 20, 20) paths. Also, the wiki article doesn't mention this but the growth rate of (n multichoose k1, k2, ..., km) as we increase n but fix the ratios p1 = k1 / n, ..., pm = km / n is precisely the Shannon entropy of the categorical distribution with probabilities p1, ..., pm . The wiki article for entropy [1] states the result for the binomial coefficient, which can be written as (n choose k) = (n multichoose k, (n - k)) . Actually a lot of basic information-theoretic results about entropy and related quantities (e.g. the properties of the Boltzmann distribution/softmax function) can be derived from similar discrete counting problems after taking a large-n limit. I don't have links at the ready but I might edit this comment if I remember places which explain this stuff. [0] https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_... [1] https://en.wikipedia.org/wiki/Entropy_(information_theory)#A...