[proofplan] The proof identifies the homogeneous degree-$d$ component with the span of exactly those monomials whose exponent vectors have total degree $d$. The usual uniqueness of polynomial expansion shows that these monomials are linearly independent and span $k[x_1,\ldots,x_n]_d$. It remains only to count exponent vectors $(a_1,\ldots,a_n)$ of non-negative integers satisfying $a_1+\cdots+a_n=d$, which is the standard stars-and-bars count. [/proofplan]

[step:Identify the degree-$d$ monomials inside the homogeneous component] Let \begin{align*} A_d := \{(a_1,\ldots,a_n) \in (\mathbb{N} \cup \{0\})^n : a_1+\cdots+a_n=d\}. \end{align*} For each $a=(a_1,\ldots,a_n) \in A_d$, define the monomial \begin{align*} x^a := x_1^{a_1}\cdots x_n^{a_n} \in k[x_1,\ldots,x_n]. \end{align*} By definition, each $x^a$ with $a \in A_d$ is homogeneous of degree $d$, so \begin{align*} \operatorname{span}_k\{x^a : a \in A_d\} \subseteq k[x_1,\ldots,x_n]_d. \end{align*} Conversely, let $f \in k[x_1,\ldots,x_n]_d$. Since every polynomial in $k[x_1,\ldots,x_n]$ has a unique finite monomial expansion, there are unique coefficients $c_b \in k$, indexed by finitely many exponent vectors $b=(b_1,\ldots,b_n) \in (\mathbb{N} \cup \{0\})^n$, such that \begin{align*} f = \sum_b c_b x_1^{b_1}\cdots x_n^{b_n}. \end{align*} Because $f$ is homogeneous of degree $d$, every monomial appearing with nonzero coefficient has total degree $d$. Hence $c_b=0$ whenever $b_1+\cdots+b_n \ne d$, and therefore \begin{align*} f \in \operatorname{span}_k\{x^a : a \in A_d\}. \end{align*} Thus \begin{align*} k[x_1,\ldots,x_n]_d = \operatorname{span}_k\{x^a : a \in A_d\}. \end{align*} [/step]

[step:Use uniqueness of monomial expansion to obtain a basis] We now show that the spanning set from the previous step is linearly independent. Suppose that a finite family of coefficients $(\lambda_a)_{a \in A_d}$ in $k$ satisfies \begin{align*} \sum_{a \in A_d} \lambda_a x^a = 0 \end{align*} in $k[x_1,\ldots,x_n]$. The monomial expansion of the zero polynomial has every coefficient equal to $0$. By uniqueness of monomial expansion in the [polynomial ring](/page/Polynomial%20Ring), $\lambda_a=0$ for every $a \in A_d$. Hence $\{x^a : a \in A_d\}$ is a $k$-basis of $k[x_1,\ldots,x_n]_d$, and consequently \begin{align*} \dim_k k[x_1,\ldots,x_n]_d = |A_d|. \end{align*} [/step]

[step:Count exponent vectors by inserting separators among stars]It remains to compute $|A_d|$. Let \begin{align*} S_{n,d} := \{(s_1,\ldots,s_{n-1}) \in \mathbb{N}^{n-1} : 1 \le s_1 < \cdots < s_{n-1} \le d+n-1\}. \end{align*} When $n=1$, this is the singleton set consisting of the empty tuple. Define a map \begin{align*} \Phi: A_d &\to S_{n,d} \end{align*} as follows. For $a=(a_1,\ldots,a_n) \in A_d$ and $1 \le i \le n-1$, set \begin{align*} s_i := a_1+\cdots+a_i+i. \end{align*} Since each $a_j$ is non-negative, we have $s_{i+1}-s_i=a_{i+1}+1>0$, so the entries are strictly increasing. Also $s_1 \ge 1$ and \begin{align*} s_{n-1}=a_1+\cdots+a_{n-1}+n-1=d-a_n+n-1 \le d+n-1. \end{align*} Thus $\Phi$ is well-defined. Conversely, define a map \begin{align*} \Psi: S_{n,d} &\to A_d \end{align*} by sending $s=(s_1,\ldots,s_{n-1})$ to $a=(a_1,\ldots,a_n)$, where \begin{align*} a_1 := s_1-1, \end{align*} \begin{align*} a_i := s_i-s_{i-1}-1 \quad \text{for } 2 \le i \le n-1, \end{align*} and \begin{align*} a_n := d+n-1-s_{n-1}. \end{align*} The strict inequalities defining $S_{n,d}$ imply that all $a_i$ are non-negative. Adding the displayed formulas gives \begin{align*} a_1+\cdots+a_n=d. \end{align*} Hence $\Psi$ is well-defined. Direct substitution gives $\Psi(\Phi(a))=a$ for every $a \in A_d$ and $\Phi(\Psi(s))=s$ for every $s \in S_{n,d}$. Therefore $\Phi$ is a bijection. Therefore \begin{align*} |A_d|=\binom{d+n-1}{n-1}. \end{align*} Using the [symmetry of binomial coefficients](/theorems/7727), \begin{align*} \binom{d+n-1}{n-1}=\binom{d+n-1}{d}. \end{align*} Combining this with the basis computation gives \begin{align*} \dim_k k[x_1,\ldots,x_n]_d=\binom{n+d-1}{d}. \end{align*} This proves the theorem.[/step]

[guided]The counting problem is to distribute $d$ indistinguishable units of total degree among $n$ variables. An exponent vector \begin{align*} a=(a_1,\ldots,a_n) \in A_d \end{align*} records that $x_i$ receives exponent $a_i$, and the condition $a_1+\cdots+a_n=d$ says that all degree has been distributed. We encode such a vector by a row of $d$ stars and $n-1$ separators. The separator after the first $a_1$ stars has position \begin{align*} s_1=a_1+1. \end{align*} The separator after the first $a_1+a_2$ stars has position \begin{align*} s_2=a_1+a_2+2. \end{align*} In general, for $1 \le i \le n-1$, define \begin{align*} s_i=a_1+\cdots+a_i+i. \end{align*} These positions lie in the ordered set $\{1,\ldots,d+n-1\}$ because there are $d$ stars and $n-1$ separators in total. They are strictly increasing since \begin{align*} s_{i+1}-s_i=a_{i+1}+1>0. \end{align*} Thus each exponent vector produces an $(n-1)$-element subset of $\{1,\ldots,d+n-1\}$. Conversely, suppose we choose separator positions \begin{align*} 1 \le s_1 < \cdots < s_{n-1} \le d+n-1. \end{align*} The number of stars before the first separator is \begin{align*} a_1=s_1-1. \end{align*} For $2 \le i \le n-1$, the number of stars between the previous separator and the next separator is \begin{align*} a_i=s_i-s_{i-1}-1. \end{align*} The number of stars after the last separator is \begin{align*} a_n=d+n-1-s_{n-1}. \end{align*} Each $a_i$ is non-negative because the separator positions are strictly increasing and remain inside $\{1,\ldots,d+n-1\}$. The total number of stars is exactly \begin{align*} a_1+\cdots+a_n=d. \end{align*} Therefore the construction recovers an element of $A_d$. The two constructions undo each other, so exponent vectors in $A_d$ are in bijection with choices of $n-1$ separator positions among $d+n-1$ total positions.[/guided]