+0

# counting problems

0
120
1

Let n be a positive integer.  Let k be a positive integer.

(a) Using a counting argument, show that C(n - 1, k - 1) + C(n - 1, k) = C(n,k).

(b) Using a counting argument, show that C(n,0) + C(n,1) + C(n,2) + ... + C(n,n) = 2^n.

(c) Using a counting argument, show that C(n,0) + C(n + 1,1) + C(n + 2,2) + C(n + 3,3) + ... + C(n + k,k) = C(n + k + 1,k)

(d) Using a counting argument, show that C(m,0) C(n,r) + C(m,1) C(n,r - 1) + ... + C(m,r) C(n,0) = C(m + n,r).

(e) 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 + 1)^2 - 2n - 1

(f) 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 + 1)^3 - 3n^2 - 3n - 1

Dec 7, 2022

#1
0

Here is a solution to part (f):

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

Dec 7, 2022