The following exercise provides a combinatorial proof for a summation formula we have seen in four earlier results: (1) Exercise 22 in Section 1.4; (2) Example 4.4; (3) Exercise 3 in Section 4.1; and (4) Exercise 19 in Section 4.2.
Let A = {a, b, c}, B = {1, 2, 3, . . . , n, n + 1}, and S = {/: A ->- B(a) (a) If S1 = {f: A †’ B| f ˆˆ 5 and f(c) = 2}, what is |S1|?
(b) If S2 - {f: A †’ B | f ˆˆ S and f(c) = 3}, what is |S2|?
(c) For 1 (d) Let T1 = { f : A †’ B | f ˆˆ S and f(a) = f(b)}. Explain Why T1, I = (n+12).
(e) LetT2 = {f : A †’ B | f ˆˆ Sand | (a) f(b)}. Explain why | T2| = (n+12)
(f) What can we conclude about the sets
S1 ˆª S2 ˆª S3 ˆª ......... ˆª Sn and T1 ˆª T2 ˆª T3?
(g) Use the results from parts (c), (d), (e), and (f) to verify that

12-n(n + 1 ) (2n + 1)