Counting the dimension

Question

Let $A_d^m:=\{\alpha\in \mathbb{N}^d: |\alpha|\leq m\}$, then the cardinality of $A_d^m$ is $\frac{(m+d)!}{m!d!}$.

How is it true? I understand we have to choose $m$ such tuples but how are we choosing them from $m+d$ numbers?

Answer 1

You want to count the number of solutions to the inequality $$ \alpha_1+\alpha_2+\dots+\alpha_d\le m, \qquad \alpha_i \ge 0 $$ Introducing a dummy variable $b$ equal to $m-\alpha_1-\dots-\alpha_2$, this is equivalent to solving $$ \alpha_1+\dots+\alpha_d+b=m,\qquad\alpha_i\ge0,b\ge0 $$ This is equivalent to counting the number of ways to put $m$ identical balls in $d+1$ distinct bins, which can be solved using stars and bars to be the claimed answer.