in this book: https://issuu.com/yilongzhang/docs/piotr_w._nowak__guoliang_yu-large_s in the Example 3.1.9. it is said that for group ($Z^k$,+) we have:
$|B(0,n)|=\frac{(2n)^k}{k!}+\frac{(2n)^{k-1}}{(k-1)!}+$ lower order terms,
where we consider $Z^k$ with word metric and standard generating set, B(0,n) is centred ball.
I don't see why is it true.
Could you help me solving this problem?
My attempts:
We want to know what is the number of integer solutions of inequality: $|x_1|+|x_2|+...+|x_k| \le n$, so maybe first find the number of integer solutions of $|x_1|+|x_2|+...+|x_k|=n$. Then we have possibilities:
If $x_i\neq0$ then there are $2^k\binom{n-1}{k-1}$ possibilities, if $x_i=0$ for only one i, then there are $2^{k-1}\binom{k}{1}\binom{n-1}{k-2}$ possibilities and so on. So $|S(0,n)|=2^k\binom{n-1}{k-1}+2^{k-1}\binom{k}{1}\binom{n-1}{k-2}+...+2^{1}\binom{k}{k-1}\binom{n-1}{0}$. But how to sum this? Or maybe there is another, more tricky solution?
You are on the right path, but there are a few tricks to employ:
The number of sums of positive integers whose sum is at most $n$, i.e., sums $$ y_1+\cdots+y_k\leq n $$ where $y_i\geq 1$ is the same as the number of sums of $k+1$ positive integers whose sum is $n+1$, i.e., $$ y_1+\cdots+y_k+z=n+1. $$ Using stars and bars, the number of such integers is $\binom{n}{k}$. This can be written out as $$ \binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}=\frac{n^k}{k!}+\cdots $$ Here, the $\cdots$ represents lower powers of $n$. Since all the $y_i$'s are positive, and we can look at the positive or negative version of each $y_i$ ($y_i=|x_i|$, so $x_i=\pm y_i$), this gives $2^k$ different possibilities for the $x_i$'s given the $y_i$'s. This results in $$ \frac{(2n)^k}{k!} $$ for the leading term. If you write out the coefficient of $n^{k-1}$ from this expression and add in the terms where exactly one of the $y_i$'s is $0$ (using a similar argument), you will get the next term.
More precisely, for the next term, we consider the coefficient of $n^{k-1}$ in the numerator. The coefficient of this term will be $\sum_{i=0}^{k-1}-i=-\frac{k(k-1)}{2}$, resulting in $$ -\frac{k(k-1)}{2}\frac{2^kn^{k-1}}{k!}=-(k-1)\frac{(2n)^{k-1}}{(k-1)!}. $$ Using the same argument as above, but with exactly one of the $x_i$'s equal to $0$, the leading term is $$ \frac{(2n)^{k-1}}{(k-1)!}. $$ Then, since there are $k$ possible $x_i$'s to equal $0$, the entire expression becomes $$ -(k-1)\frac{(2n)^{k-1}}{(k-1)!}+k\frac{(2n)^{k-1}}{(k-1)!}=\frac{(2n)^{k-1}}{(k-1)!}, $$ as desired.
If you're interested, this is related to the number of monomials of total degree at most $n$. The additional $z$ is essentially a homogenization.