First, I want to say that I assume this problem has been looked at as it seems like a natural question to ask after being introduced to the boardwalk metric; however, I wouldn't know what to look up for information on this, and this is a personal project (meaning I don't want to just look up answers anyway).
Context: I was attempting to count the number of efficient (no left or down movement) paths from the bottom vertex of an n*m grid to the top-right vertex. I made some rules that would give this:
- (n,m)=(m,n)
- (n,0)=1
- (n,m)=(n,m-1)+(n-1,m)
However, this grows to a ridiculous amount of calculations, so I was able to make a calculator for this. By doing so, I found that (at least up to n=6) that there exists a polynomial of the nth degree which will calculate these out much quicker. The poly's I have thus far are: $$f_1(x)=x+1$$ $$f_2(x)=\cfrac{1}{2}x^2+\cfrac{3}{2}x+1$$ $$f_3(x)=\cfrac{1}{6}x^3+x^2+\cfrac{11}{6}x+1$$ $$f_4(x)=\cfrac{1}{24}x^4+\cfrac{5}{12}x^3+\cfrac{35}{24}x^2+\cfrac{24}{12}x+1$$ $$f_5(x)=\cfrac{1}{120}x^5+\cfrac{1}{8}x^4+\cfrac{17}{24}x^3+\cfrac{15}{8}x^2+\cfrac{137}{60)}+1$$ $$f_6(x)=\cfrac{1}{720}x^6+\cfrac{7}{240}x^5+\cfrac{35}{144}x^4+\cfrac{49}{48}x^3+\cfrac{203}{90}x^2+\cfrac{49}{20}x+1$$
Observations: I see that the first coefficient will probably be $\cfrac{1}{n!}$ and the constant will be 1. Because of this, I assume it is possible for any n there exists a polynomial $\sum_{i=0}^n \frac{c(n,i)}{n!}x^i$ that produces the number of paths in a grid. I've attempted to give every coefficient a form $\cfrac{c}{n!}$ to see if I could find any patterns in that, but to no avail thus far.
Tl;dr: I'm wanting to know if there exist methods where I could find this c(n,i) for any integer value n (producing as few of the functions as possible). I'm currently enrolled in a Real Analysis II course, so I would really like methods or texts to be within my paygrade; however, I would definitely be open to reading materials that are normally taught shortly after this course.
I would also like to apologize for the lack of tags; however, I'm not sure what area of math this topic, or the methods I could use to solve this problem, would be. Also, I would want to discuss a lot more about my "attempt at solutions," but I've been working on this problem for a week and the post would get cluttered quite quickly.
The count is known to be $\binom{n+m}{n}=\binom{n+m}{m}$. You can check that this formula satisfies your recurrence relations, or you can derive it combinatorially by noting that each such path takes $n+m$ steps and is completely determined by which steps are horizontal.