3 ms·
There’s a bit of hand-waving in the jump to 2n choose n solution, which I suppose is fine, and my ex–math teacher brain really wants to have a proper proof or a
by dhosek 4mo ago
There’s a bit of hand-waving in the jump to 2n choose n solution, which I suppose is fine, and my ex–math teacher brain really wants to have a proper proof or at least solid reasoning rather than “it follows the pattern” based on three observations.
But I am reminded of how during my engagement 24 years ago, my future father-in-law raised an issue of being able to determine whether they were getting the full amount of sandpaper on large rolls that they were paying for. I was able to simplify the question a bit to one that treated the rolls as if they were simple concentric rolls of a specified thickness and from there could turn it into the good old Gaussian sum formula times 2π to get the length. The engineers working for the company came up with the same solution, but instead of using n(n-1)/2 they did the summation with multiple rows in excel.
- shenberg 4mo agoYou always either go left or down so total 40 steps, choose 20 to be down (or 20 to be right)
- dhosek 4mo agoWhich suggests another approach to the solution; you have 20Ls and 20Rs which can appear in any order so it’s a permutation with repetition problem and thus 40!/(20!20!) That approach has the advantage that it’s easily adapted to non square rectangular grids (n+m)!/(n!m!)
- gobdovan 4mo agoYou can go down or right at any point. To go in bottom-right corner, you need n down steps and n right steps. In how many ways can you arrange n things on type A and n things of type B? In C(2n, n). The problem is about modeling, once you model it correctly, you get the definition of combinations.
- dhosek 4mo agoC(2n, n) isn’t about permutations, but choosing subsets of a set without order, but as I’ve thought about it, the model here is that there are 2n moves to be made and you need to choose n of them to be down (or right, depending on your preference).