# Variation of the Ball and Urn Problem

Fix an integer $n \geq 1$ and $k \in \mathbb{Z}$, $k$ not necessarily nonnegative. How many distinct $n$-tuples $(x_{1}, x_{2}, \ldots, x_{n})$ are there such that $x_{1} + x_{2} + \cdots + x_{n} = k$ with $x_{i} \in \{-1, 0, 1\}$? By distinct I mean that the number of 0s, 1s, and -1s of two solutions must be different.

-

This would be easier with everything non-negative, so let $y_i=x_i+1$ take values in $\{0,1,2\}$ with a target sum of $k+n$.

You are asking for the number of partitions of $k+n$ into up to $n$ parts each no more than $2$. For $-n \le k \le 0$ this is $\left\lfloor \frac{n+k}{2} +1\right\rfloor$ while for $0 \le k \le n$ this is $\left\lfloor \frac{n-k}{2}+1\right\rfloor$ so combined $\left\lfloor \tfrac{n-|k|+2}{2}\right\rfloor$.

-
Hmm...I don't exactly see how the last sentence follows. – ADF Apr 7 '12 at 20:37
@ADF: It is "obvious" to me, the first expression by considering how many $2$s are possible (from $0$ to no more than $\frac{n+k}{2}$) and the second how many $0$s (from $0$ to no more than $\frac{n-k}{2}$). Brian M. Scott has given a full explanation. – Henry Apr 7 '12 at 21:17

This is an expansion of Henry’s answer, done because it took me a while to justify the formula that he obtained. I’m making the same shift to non-negative variables and counting partitions of $k+n$ into at most $n$ parts each of size at most $2$.

Say there are $m$ parts of size $2$; then there must be $n+k-2m$ parts of size $1$, and any remaining parts must be of size $0$, so the partition is completely determined by $m$. Clearly $m$ can be at most $\left\lfloor\frac{n+k}2\right\rfloor$. On the other hand, $m$ must be large enough so that $$n+k-2m\le n-m\;,$$ or there won’t be enough parts left to make up the total of $k+n$. Thus, we must have $k\le m$, and hence $$k\le m\le\left\lfloor\frac{n+k}2\right\rfloor\;.\tag{1}$$ Thus, if $k\ge 0$ there are $$\left\lfloor\frac{n+k}2\right\rfloor-k+1=\left\lfloor\frac{n+k}2-k\right\rfloor+1=\left\lfloor\frac{n-k}2\right\rfloor+1\tag{2}$$ partitions.

If $k<0$, $(1)$ must be replaced by $$0\le m\le\left\lfloor\frac{n+k}2\right\rfloor\;,$$ and there are $$\left\lfloor\frac{n+k}2\right\rfloor+1=\left\lfloor\frac{n-|k|}2\right\rfloor+1\tag{3}$$ partitions. Combining $(2)$ and $(3)$ now yields the desired result: there are $$\left\lfloor\frac{n-|k|}2\right\rfloor+1$$ partitions, where of course we must have $|k|\le n$.

-