1
$\begingroup$

How many elements are in the set:

$\{(x,y,z) \mid x+y+z = k \text{ and } x,y,z \in \{0,\dotsc,n\}\}$

I can see that when $k \le n$, it's $\binom{k+2}{2}$. And, by symmetry, the value for $k$ is the same as that for $3n-k$. So, I've figured out the two pyramids, and I'm just missing the octahedron in the middle.

  • 0
    In the cases you've figured out, the points form an equilateral triangle. When $n < k < 2n$, you can think of the arrangement as an truncated equilateral triangle; that should let you count the number of points.2010-11-24
  • 0
    @Rahul: Right, I see that now. So, the solution will be of the form (A choose 2) - 3 (B choose 2)?2010-11-24
  • 0
    ... or maybe $\binom{A}{2} - 3\binom{B}{2} - 3\binom{C}{2}$2010-11-24
  • 0
    Oh, I didn't see your response when I was writing my answer. Well, there it is for you now.2010-11-24

1 Answers 1

3

When $n < k < 2n$, the number of points for which $x,y,z \in \mathbb N$ is $\binom{k+2}{2}$. Of these, $\binom{k-n+1}{2}$ have $x > n$ (as you can see by letting $x = x'+n+1$), and similarly for $y$ and $z$. These are the only exceptions, because when $k < 2n$, more than one of the variables cannot exceed $n$. So the number of points with $x,y,z \le n$ is $\binom{k+2}{2} - 3\binom{k-n+1}{2}$. This looks somewhat asymmetrical, but it's actually equal to $(k-n)(2n-k) + \binom{n+2}{2}$. I like writing it in this form because then it's obvious that it satisfies the "boundary conditions".