[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.
[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]
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]
