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.

  • $\begingroup$ 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. $\endgroup$ – EuxhenH Jan 10 '19 at 19:46
  • $\begingroup$ @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. $\endgroup$ – Mike Jan 10 '19 at 19:55
  • $\begingroup$ @coffeemath lol, it is stars and bars, I edited it. $\endgroup$ – Mike Jan 10 '19 at 20:15
  • $\begingroup$ @RossMillikan Thanks for the catch, I converted everything to $k$'s $\endgroup$ – 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)$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.