$k-$ degree polynomial regression

$$\phi: \mathbb{R}^d \to \mathbb{R}^m$$ is the feature mapping for performing $$k-$$ degree polynomial regression on a $$d-$$ dimensional input. for example when $$k=3$$ and $$d=2$$ then, $$\phi([x_1, x_2 ]) = [1, x_1, x_2, x_1^2, x_2^2, x_1^3, x_2^3, x_1x_2, x_1^2x_2, x_1x_2^2]$$

For any arbitrary $$d$$ and $$k$$, how to write $$m$$ as a function of $$d$$ and $$k$$?

You ask for the number of distinct monomials in $$d$$ variables $$x_1,x_2,\ldots,x_d$$ of total degree less than or equal to $$k.$$ These are the monomials of the form

$$x_1^{e_1}\,x_2^{e_2}\,\cdots x_d^{e_d}$$

where the $$e_1$$ are non-negative integers whose sum (the total degree) does not exceed $$k.$$

One simple way to count them is to consider the sequence of natural numbers

$$\left(f_0, f_1, \ldots, f_d\right) = \left(k-e_1-\cdots-e_d+1, e_1+1, e_2+1, \ldots, e_d+1\right)$$

These sum to $$k+d+1.$$ For $$i=1,\ldots, d,$$ their partial sums

$$s_i = f_0 + f_1 + \cdots + f_{i-1}$$

form a sequence of $$d$$ distinct, increasing integers in the range $$\{1,2,\ldots, k+d\}$$ (with $$s_{d+1}=k+d+1$$ always) and thereby correspond to a subset of those integers of size $$d.$$ Conversely, any such subset when ordered gives a sequence of such $$s_i$$ from which the powers $$e_i$$ can be recovered from the successive differences

$$s_i - s_{i-1} - 1 = e_i,\ i=1,2,\ldots, d.$$

Consequently the number of such monomials is the same as the number of such subsets, given by

$$\binom{k+d}{d} = \frac{(k+d)!}{k!\,d!}.$$

For instance, with $$k=3$$ and $$d=2$$ the value is $$(3+2)!/(3!\,2!) = 10.$$

It may be instructive to examine the correspondence explicitly in a small example like this. Here is a table of the monomials and the corresponding sequences.

$$\begin{array}{lcr} \text{Monomial} & \text{Sequence} & \text{Subset} \\ \hline 1 & (4,1,1) & \{4,5\}\\ x_1 & (3,2,1) & \{3,5\}\\ x_2 & (3,1,2) & \{3,4\}\\ x_1^2 & (2,3,1) & \{2,5\}\\ x_1x_2 & (2,2,2) & \{2,4\}\\ x_2^2 & (2,1,3) & \{2,3\}\\ x_1^3 & (1,4,1) & \{1,5\}\\ x_1^2x_2 & (1,3,2) & \{1,4\}\\ x_1x_2^2 & (1,2,3) & \{1,3\}\\ x_2^3 & (1,1,4) & \{1,2\} \end{array}$$

Finally -- again as an illustration -- the following R code uses combn to produce an array of subsets and converts that into a representation of the monomials. Here is the output for $$k=d=3;$$ that is, a list of the monomials in three variables up to degree $$3:$$

monomials <- function(k, d, varname="x") {
vars <- paste0(varname, "[", 1:d, "]")
s <- function(e) ifelse(e > 1, paste0(vars, "^", e, sep=""), ifelse(e==1, vars, ""))
mult <- function(a) paste(a[a > ""], collapse="*")
a <- apply(apply(apply(rbind(combn(k+d, d), k+d+1), 2, diff) - 1, 2, s), 2, mult)
a[a==""] <- "1"
rev(a)
}

mai <- par("mai")
par(mai=rep(0,4))
a <- monomials(3,3)
plot(c(1, length(a)), 0:1, type="n", xaxt="n", yaxt="n", xlab="", ylab="", bty="n")
invisible(sapply(seq_along(a), function(i) text(i, 1/2, parse(text=a[i]))))
par(mai=mai)