What exactly is monomial basis? Consider a vector of $n$ dimension. How can I write all monomials up-to a order say $k$ of this vector?
If I manged to write the monomials of the vector up-to order $k$, is it a monomial basis?
I feel I am missing something very basic, an someone please help.
I have an example given a vector $[x_1,x_2]$ the monomial expansion upto order 2 is $[1,x_1,x_2,x_1^2,x_1,x_2,x_2^2]$. But still I do not understand how to expand further? For example how many terms will be there in the monomial expansion for vector of length 38 and monomial order 3?
The answer to the above question is given as 10660 in the link below https://www.cc.gatech.edu/~hic/CS7616/Papers/Campbell-et-al-2006.pdf
But I still cannot understand how they got the number 10660.
Firstly, the paper has a typo you seem to have reproduced, which may be part of your confusion. Ignoring the transposes in the paper, when the input is $[x_1,x_2]$, the output list of all monomials up to and including degree $2$ would be $[1,x_1,x_2,x_1^2,x_1x_2,x_2^2]$, with the monomial $x_1x_2$ that was missing in the paper/your question, instead of repeats of the monomials $x_1$ and $x_2$ earlier in the list. Make sure you understand what a monomial (with coefficient $1$) is, so you can understand what it is we're calculating here.
Now, to calculate the number of monomials using $m$ variables of degree up to and including degree $K$, we can use a variant of stars and bars technique. I claim that it's the same as the number of sequences of $m$ indistinguishable stars and $K$ indistinguishable bars. A bar after $n$ stars can signify a factor of $x_n$ (and a bar at the beginning doesn't do anything). For example, with $K$ equal to $4$, $\mid\,\star\star \mid \star \mid \mid \star\cdots $ corresponds to $x_2x_3^2$ and $\star\mid\mid\mid\mid\star\cdots$ corresponds to $x_1^4$, etc.
But the number of sequences of $m$ stars and $K$ bars is the same as the number of ways to choose $K$ spots out of the total $m+K$ spots to be the bars (the rest are all stars). This number is the combination $\binom{m+K}{K}$, which you may also have seen written as $\vphantom{C}_{(m+K)}C_K$.
In the particular case you asked about, $m=38$ and $K=3$. So we have $$\binom{m+K}{K}=\dfrac{41*40*39}{3!}=41*20*13=20*533=10660\text{.}$$