How many integer r-tuples are there such that sum of the absolute values of their entries is less than or equal to n.

Question

How many r-tuples are there such that sum of absolute values of entries is less than or equal to $n$?

That is, what is the cardinality of the set $ \{(x_1,...,x_r): x_i \in Z \text{ and }\mid x_1\mid+ ... + \mid x_r \mid \leq n\}$?

This should give me the growth function of the group $Z^r$ under the generating set $S=\{e_1,...,e_r\}$ where $ e_i=\{0, ...,0, 1,0,...,0\}$ with $1$ in the $i$-th position. It's known that the answer to this question is: $\sum_{k=0}^{r}2^k {r \choose k}{n \choose k}$. I'm trying to figure it out for myself.

---

Attempt: I have been able to figure out that the cardinality of $ \{(x_1,...,x_r): x_i \in Z^+ \text{ and }x_1+ ... + x_r \leq n\}$ is $n \choose k$.

Also I calculated cardinality of $ \{(x_1,...,x_k): x_i \in Z^+ \text{ and } x_1+ ... + x_k = n\}$ to be $n-1 \choose k-1$ via the stars and bars method.

However, I am a little stuck on combining these results (or otherwise) to figure out the question with the absolute values.

Answer 1

Start from your result that the number of ways to sum $k$ positive numbers to $n$ or less is $n \choose k$.

To get the number of ways to sum $k$ positive numbers and $r-k$ zeros to get $n$ or less you choose the positions of the zeros in $r \choose k$ ways then choose the positive numbers in $n \choose k$ ways, so the number of ways to sum $k$ positives and $r-k$ zeros to $n$ or less is ${r \choose k}{n \choose k}$.

Because of your absolute values we can choose the sign of the nonzero numbers in $2^k$ ways, so the number of ways to sum the absolute values of $k$ nonzero numbers and $r-k$ zeros is $2^k{r \choose k}{n \choose k}$.

Now we just sum over $k$ from $0$ to $r$, getting the desired result $$\sum_{k=0}^r2^k{r \choose k}{n \choose k}$$

Added: Alpha gives a closed form using a hypergometric function $$_2F_1(-n,-r;1;2)$$