Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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