A problem I have had on my mind recently has been a compact way to compute the size of an $N$-Dimensional Polynomial basis of some order $p$, where a linear basis is $p=1$. I have attempted searching for such a formula online but haven't been able to stumble upon one.
I have to believe a formula for this computation exists, though, because this should be a question that statisticians or others who build higher dimensional models ask when figuring out what polynomial basis order to use, based on the size of their data sets, when they want to build a model using polynomials.
What I would like to know is, is there any compact formula for this question that I have not been able to find via my search online?
Another related question is, is there a clever algorithmic way to represent and compute individual $N$-Dimensional polynomial basis terms such that one could target a specific basis function in the set using a single index? Because then one could do a simple loop through all the basis functions to do any necessary computations.
Note that I am fine with someone mentioning these answers don't really need to be answered explicitly due to some reasoning. It's just that, as far as my experience has shown, these questions seem important to answer to tackle certain modeling problems based on polynomials.
Like how do I estimate what polynomial order to use to model a data set to avoid overfitting (without explicit regularization)? Do people just avoid answering this question by using something like K-fold Cross Validation to find the appropriate polynomial order?
And then, how can I compactly program software that can represent an $N$-D order $p$ polynomial basis in a way that could simply be looped through without needing to store data for each polynomial term?
These are the underlying questions of this post I am trying to get answered.