Number of n-tuples in $\{0, 1, 2\}$ with sum less than or equal to $d$.

Question

I would like to know if there is an expression for the number of n-tuples of $\mathbb{Z}$, where each component is an integer between $0$ and $2$, and the sum of the components is less than or equal to some number $d \in [0,2n]$.

I am also interested if this expression could be generalised for integer n-tuples with components between $0$ and $q$, with the sum of the components being less than or equal to some given number $d \in [0, (q-1)n]$, but would appreciate an answer for just the case $q=3$.

I know from (a slight alteration of) this post that the number of n-tuples of non-negative integers with the sum of components less than or equal to $d$ is equal to $d+n \choose n$. But I'm not sure if this information helps.

Answer 1

The answer can be found with the principle of inclusion exclusion, by taking all $\binom{n+d}{n}$ vectors, then subtracting for each coordinate the $\binom{n+d-q}{n}$ vectors where the coordinate is too large, then adding back in the doubly subtracted vectors, etc. The result is $$ \bbox[5px, #fbfbfb, border: solid black 2px]{\sum_{k=0}^n (-1)^k\binom{n}{k}\binom{n+d-qk}{n}.} $$

Answer 2

For the case of $\{0,1,2\}$, an alternate view is to let $a,b,c$ be the number of $0, 1,2$ respectively. Then we have $b + 2c \le d$ and so the answer is:

$$\sum_{b,c} {n! \over (n-b-c)! b! c!}$$

where the summation is over all $(b,c)$ s.t. $b\ge 0, c\ge 0, b+2c \le d$. For this $q=3$ case this can be easily done with a double (nested) summation, one on each variable.

I think this is less efficient to calculate than the I-E based answer by @MikeEarnest but at least this is an alternate method. I wouldn't try this for large $q$ though as the number of summations is $q-1$.