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

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.

• Look at the alternative problem: In how many ways can you divide $n$ $1$'s with $r-1$ separators? Then do it for $1, 2, .., n$. And don't forget about negative numbers. – EuxhenH Jan 10 '19 at 19:46
• @coffeemath you're right, in that case, which is my first step in my attempt, there should be the restriction that the $x_i$ are positive integers. I will reflect that. – Mike Jan 10 '19 at 19:55
• @coffeemath lol, it is stars and bars, I edited it. – Mike Jan 10 '19 at 20:15
• @RossMillikan Thanks for the catch, I converted everything to $k$'s – Mike Jan 10 '19 at 20:16

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)$$