$\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$?


1 Answer 1


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"

mai <- par("mai")
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]))))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.