Let n be a positive integer.
(a) There are n^2 ordered pairs (a, b) of positive integers, where \(1 \le a, b \le n.\) Using a counting argument, show that this number is also equal to
\(n + 2 \binom{n}{2}.\)
(b) There are n^3 ordered triples (a, b, c) of positive integers, where \(1 \le a, b, c \le n\) Using a counting argument, show that this number is also equal to
\(n + 3n(n - 1) + 6 \binom{n}{3}\)
(a) Just expand both sides.
(b) Let's call (a,b,c) a smiley face if b is less than a and b is less than c, because when we plot the graph, we get a happy face! And if b is greater than a and b is greater than c, that's a frowny face, because we get a frowny face when we turn a smiely face up-side-down.
There are other kinds of faces like smirks (like a is less than b and b is less than c) and neutral faces (like when a is equal to b and b is equal to c). If the face is neutral, then a equals b and b equals c, so when we choose a, b, and c are also chosen, and there are n choices for a, so there are n neutral faces.
Now we count the number of smirks. There are n ways to choose a, and there are n - 1 ways to choose b. We also multiply by 3, because the value that we chose for a could have also been the value of b, or the value of c. So there are 3n(n - 1) smirks.
Now we count the number of smiley faces. There are n ways to choose a, then n - 1 ways to choose b, then n - 2 ways to choose c. So there are n(n - 1)(n - 2) = 3C(n,3) smiley faces. By symmetry, there are 3C(n,3) frowny faces.
Therefore, the total number of faces is n^3 = n + 3n(n - 1) + 6C(n,3).
Other facial expressions include neutral expressions and smirks (like an is less than b and b is less than c) (like when a is equal to b and b is equal to c). When an is picked, b and c are also chosen if the face is neutral since an equals b and c equals b when the face is neutral. Since there are n possible options for a, there are n neutral faces.
